經典演算法實作：C# 解決八皇后問題（回溯法完整註解版）

問題定義

在 8×8 棋盤上放置 8 個皇后，使任意兩個皇后不同行、不同列、不同對角線。總排列數 8! = 40,320，實際解數 92 組。此為回溯法教科書級範例。

核心邏輯：逐行試探 + 剪枝

• Queen[y] = x 表示第 y 行皇后放在第 x 列。
• 對第 y 行，從 Queen[y]+1 開始嘗試每一列 x。
• 檢查與前 y-1 行皇后是否衝突：同列 j==x、主對角線 j==x-d、副對角線 j==x+d（d = y-i）。
• 若無衝突，確定位置進入下一行；若試盡 0-7 仍無解，回溯至上一行繼續嘗試下一列。

完整可執行程式碼

using System;

namespace EightQueens
{
    class QueenSolver
    {
        public void Solve(int size = 8)
        {
            int[] queen = new int[size];
            int y = 0, x, i, j, d, solutionCount = 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 // 8 行皆放置完畢，輸出一組解
                    {
                        Console.WriteLine($"\n{++solutionCount}:");
                        for (i = 0; i < size; i++)
                        {
                            for (j = 0; j < size; j++)
                                Console.Write(queen[i] == j ? 'Q' : '*');
                            Console.WriteLine();
                        }
                        y = size - 1; // 繼續回溯尋找下一組解
                    }
                }
            }
        }
    }

    class Program
    {
        static void Main()
        {
            new QueenSolver().Solve();
            Console.ReadKey();
        }
    }
}

執行結果片段

1:
Q*******
*****Q**
***Q****
*******Q
**Q*****
*******Q -> (實際輸出 92 組，此處略)
...
Over

延伸思考

• 位元遮罩優化：用 int 位元分別表示列、主對角線、副對角線佔用，O(1) 判斷衝突，速度提升數量級。
• N 皇后通用化：將 size 參數化，支援任意 N（N≥4 有解）。
• 並行化：將第一行的 8 種起始位置分派給 8 執行緒，各自獨立回溯，最後合併結果。