Problem 750 8 Queens Chess Problem，八個皇后的西洋棋問題

八個皇后的問題是演算法中最常見的問題，經常出現在回溯法(Backtracking)的範例中。在我們先前的ACM解題中，就出現過兩次，一次是在Problem 167 The Sultan's Successors，權位的繼承者，另一次就是前一個ACM解題：Problem 291 The House Of Santa Claus，聖誕老公公的房子。
回溯的一個重點使用遞迴呼叫，在C語言主程式中，使用

for (j=0;j<8;j++)
{
    column[0]=j;
    queens(0);
}

表示執行八次的queens(0)，這八次的執行都是從零開始，這裡的零代表著第一個皇后，這八次不一樣的地方在擺棋的方式，以column[0]=j;來表示第一列的皇后位置，八次，每次的第一列，皇后的位置都不一樣。所以這個題目的重點在以column[i]來代表第i列的皇后的位置，如果column[3]==5，表示第三列(row)的皇后放在第五行的位置。
在void queens(int i)的C語言函數中，只有下列簡單的內容

if (isPromising(i))
{
    if (i==7)
    {
        /* 這裡是排完八個皇后之後，要處理列印的地方 */
    }
    else
    {
        /* 這裡表示皇后沒放完，要繼續放 */
        for (j=0;j<7;j++)
        {
            column[i+1] = j;
            queens(i+1);
        }
    }
}

上面的C語言程式重點在promising(i)這個地方，因為如果這個皇后下下去之後，與其它皇后有所衝突，就表示 no promise了，也就是這一步下錯了，不用繼續向下處理，回頭吧。
這個題目要判斷是否promise有四個條件，任一條件成立都是 no promise
1. column[i]==column[k]，表示不同列的皇后在同一行。
2. abs(column[i]-column[k])==i-k ，表示兩個皇后在同一個斜線格上。
3. i==x-1&&column[i]!=y-1，表示與指定位置擺放的皇后，位置同列。
4. i!=x-1&&column[i]==y-1，表示與指定位置擺放的皇后，位置同行。

另外，我中了許多WA(Wrong answer)，因為題目的輸出要每個case都要有個兩行標頭，我以為全部就一個標頭即可，題目這裡倒是沒說的很清楚。
以下是輸入 4 7 後的答案

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      3 1 7 5 8 2 4 6
 2      3 5 2 8 1 7 4 6
 3      3 7 2 8 5 1 4 6
 4      5 3 1 6 8 2 4 7
 5      5 7 1 3 8 6 4 2
 6      5 7 2 6 3 1 4 8
 7      6 3 1 8 5 2 4 7
 8      8 2 5 3 1 7 4 6

p750題目連結
回ACM題庫目錄
回首頁