【演算】八皇后問題 - Eight Queens Puzzle

　　我想有不少人玩過西洋棋(chess)這種棋奕遊戲。其中，有一種棋子 - 后(Queen)除了可以直走、橫走，還可以往斜直線的方向走。而八皇后問題(Eight Queens Puzzle)就是在一個 8 × 8 的西洋棋盤上，使八個皇后全部放在棋盤上，而不能被其他皇后吃掉。

　　這個問題還能夠加以衍伸，變成「在一個 n × n 的西洋棋盤上，使 n 個皇后全部放在棋盤上，而不能被其他皇后吃掉」的 n 皇后問題。


　　若是只需要輸出其中一種排法，我們可以使用遞迴求解。嘗試每一種棋子擺放的方式，再找出符合條件(皇后間無法互相攻擊)的擺法。上述的狀態空間樹(state space tree)如下圖(為簡化作圖，這裡的 n = 4)：



　　[i, j] 代表第 i 行的皇后擺在第 j 列上。這棵樹的葉節點(leaf nodes)，即為此問題所有可能解的集合。而上圖的狀態空間樹，總共有 256 (4⁴) 個葉節點。


　　不過，這種方式還是相當沒效率，所以我們必須想辦法減少遞迴的次數。

　　首先我們知道，因為皇后可以橫向、直向與斜向移動，所以我們可以在遞迴前先判斷：現在這個皇后放置的位置，是否會與其他皇后衝突。上述的狀態空間樹如下圖所示：



　　跟前一張圖比較，節點 [1, 1] 之下的 [2, 1] 與 [2, 2] 因為會與 [1, 1] 衝突，所以遞迴時不會走訪這個節點。同理，節點 [2, 3] 之下的所有節點，因為會與 [1, 1] 或 [2, 3] 衝突，所以遞迴時也不會走訪這個節點。

　　如此就可以有效的減少遞迴的次數。這種方式就稱之為修剪(pruning)。


　　至於要如何判斷某位置是否會與其他皇后衝突呢？我的方式是使用分別作列、左斜與右斜的陣列。每放置一個皇后，就標記其相對應的三個變數值。


　　完整的虛擬碼大致如下：

void queens(Index x)
{
    Index i;

    for (i = 1 to n)
    {
        Index j = i - x + n;
        Index k = x + i + 1;

        if (column[i] and right[j] and left[k])
        {
            column[i] = right[j] = left[k] = false;

            queen(x + 1);

            column[i] = right[j] = left[k] = true;
        }
    }
}

　　以下是使用 C 語言的實現：

#include <stdio.h>
#include <stdlib.h>

void queens(int x);
void print(void);

unsigned int n, num;
char** checkerboard;
int* column;
int* right;
int* left;

int main(void)
{
    int i, j;

    printf("請輸入 n 的大小: ");
    scanf("%d", &n);

    // 動態分配記憶體
    column = malloc(sizeof(int) * n);
    right = malloc(sizeof(int) * (2 * n - 1));
    left = malloc(sizeof(int) * (2 * n - 1));
    checkerboard = malloc(sizeof(char*) * n);

    // 變數初始化
    num = 0;
    for (i = 0; i < n; i++)
    {
        column[i] = 1;

        checkerboard[i] = malloc(sizeof(char) * n);
        for (j = 0; j < n; j++)
        {
            checkerboard[i][j] = 'x';
        }
    }

    for (i = 0; i < 2 * n - 1; i++)
    {
        right[i] = left[i] = 1;
    }

    queens(0);

    printf("\n總共有 %d 種排法\n\n", num);

    // 釋放記憶體空間
    for (i = 0; i < n; i++)
    {
        free(checkerboard[i]);
    }

    free(checkerboard);
    free(column);
    free(right);
    free(left);

    system("pause");
}

void queens(int x)
{
    if (x < n)
    {
        int i;
        for (i = 0; i < n; i++)
        {
            int j = i - x + n - 1;
            int k = i + x;

            if (column[i] && right[j] && left[k])
            {
                // 標記皇后位置, 並遞迴放置下一個
                column[i] = right[j] = left[k] = 0;
                checkerboard[x][i] = 'Q';

                queens(x + 1);

                column[i] = right[j] = left[k] = 1;
                checkerboard[x][i] = 'x';
            }
        }
    }
    else
    {
        // 輸出棋盤
        print();
        num++;
    }
}

void print(void)
{
    int i, j;

    printf("\n");
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("%c", checkerboard[i][j]);
        }

        printf("\n");
    }
}