經典演算法 C# 實作：八皇后問題回溯法完整解碼 (92 解)

問題描述

8×8 棋盤放置 8 個皇后，任兩個不同行、列、對角線。8! = 40320 種排列中僅 92 組解。

回溯法核心程式碼

using System;
namespace ExQueen
{
    class Queen
    {
        public void QueenArithmetic(int size)
        {
            int[] Queen = new int[size]; // 每列皇后行索引
            int y = 0, x, i, j, d, t = 0;
            Queen[0] = -1;

            while (true)
            {
                // 尋找當前列可放置位置
                for (x = Queen[y] + 1; x < size; x++)
                {
                    for (i = 0; i < y; i++)
                    {
                        j = Queen[i];
                        d = y - i;
                        // 檢查衝突：同行、同主對角、同副對角
                        if (j == x || j == x - d || j == x + d) break;
                    }
                    if (i >= y) break; // 找到合法位置
                }

                if (x == size) // 當前列無解，回溯
                {
                    if (y == 0) { Console.WriteLine("Over"); break; }
                    Queen[y] = -1; y--;
                }
                else
                {
                    Queen[y] = x; y++;
                    if (y < size) Queen[y] = -1;
                    else // 找到一組解
                    {
                        Console.WriteLine("\n" + ++t + ":");
                        for (i = 0; i < size; i++)
                        {
                            for (j = 0; j < size; j++)
                                Console.Write(Queen[i] == j ? 'Q' : '*');
                            Console.WriteLine();
                        }
                        y = size - 1; // 繼續回溯找下一組
                    }
                }
            }
        }
        public static void Main() { new Queen().QueenArithmetic(8); }
    }
}

演算法關鍵點

• Queen[y] 記錄第 y 列皇后所在行，-1 表示未放置。
• 衝突檢查：j == x (同行)、j == x-d (主對角)、j == x+d (副對角)。
• 回溯：當列無合法位置，重置該列並退回上一列 (y--) 繼續搜尋。
• 找到完整解後列印棋盤並繼續回溯尋找下一解。