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

前言

八皇后問題是電腦科學中經典的回溯演算法範例。目標是在 8×8 棋盤上放置八個皇后，使其互不攻擊（不在同一行、同一列、同一對角線）。本文提供一個使用 C# 實作的非遞迴回溯解法，並附上完整程式碼與執行結果說明。

核心演算法邏輯

程式採用迴圈與陣列模擬遞迴回溯流程：

• Queen[y] 記錄第 y 列皇后所在的行位置（0~7）。
• 從第 0 列開始，嘗試將皇后放置於下一個可用行（x = Queen[y] + 1）。
• 檢查新位置是否與前面已放置的皇后衝突：同行（j == x）、主對角線（j == x - d）、副對角線（j == x + d）。
• 若找到安全位置，前進至下一列（y++）；若該列無合法位置，回溯（y--）並重置當前列為 -1。
• 當 y == SIZE 時，表示 8 個皇后皆已放置完成，輸出一組解並繼續回溯尋找下一組。

完整 C# 程式碼

using System;

class Queen
{
    const int SIZE = 8;

    public static void Main()
    {
        int[] Queen = new int[SIZE];
        int y, x, i, j, d, t = 0;

        y = 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("Done");
                    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; // 繼續回溯尋找下一解
                }
            }
        }
    }
}

執行結果與討論

程式會依序列印出全部 92 組解。每組解以棋盤形式顯示，'Q' 代表皇后，'.' 代表空格。

原文討論中提到 foreach 與 for 的差異：在需精確控制索引與回溯步驟的演算法中，for 迴圈更具確定性與可預測性，較適合此類場景。雖然 foreach 可透過自訂 Enumerator 實現類似行為，但對於基礎資料結構遍歷，for 仍是更直觀、高效的選擇。

優化建議

輸出棋盤時，可使用三元運算子簡化：
Console.Write(Queen[i] == j ? 'Q' : '.');