你一定會的 N-Queen Problems

contributed by < YLowy >

1. N-Queen Problems

剛好在 q4 的第四題有提到這個問題，其實還挺有趣的所以就整理成一篇。

首先釐清題目敘述 :

西洋棋中的 "皇后" 可以在線性距離吃掉任何旗子，以圖為例當 Q 下在 (4,3) 位置上時，'X' 為可以攻擊的位置，而我們目標為給定一個正整數 N ，而在此 N * N 棋盤中擺放 N 個皇后棋，且彼此不能互相攻擊。

2. 分析

2.1 窮舉 / Backtracking Algorithm

最直觀想法為列舉全全部的可能放置位置，再逐一判斷該放置位置是否皇后彼此不會受到影響。缺點為非常慢，必須改善此點。

2.2 判斷該擺放位置是否會受到影響

首先我們可以觀察擺放皇后時棋盤受到的影響，首先最容易觀察到的點為皇后棋都每行每列都只存在一個。

我們再擺放位置時候我們會從第一行開始擺放，故我們判斷方式可以從第二行開始，逐一往上檢查當我放置下個皇后該攻擊路上是否有已經擺放的皇后棋

1. 擺放第一個點:

由於每行必第會有一個皇后，所以遞迴判斷可以從每行每個點擺放開始逐步向下考慮

第一個點不需要考慮前面有沒有被攻擊到的皇后

2. 擺放第二個點:

第二個皇后棋開始就必須檢查攻擊路徑上有沒有先前放置的皇后

第二個皇后 (0,2) 其判斷往上的攻擊路徑
因為每一行只有自己本身，所以我們只需要檢查 3 個方向

1. 垂直向上
2. 左上路徑
3. 右上路徑

我們可以發現 (0,0) 路徑上已經放置原先放置的皇后，所以代表這個放置是錯誤的，我們也可以不用考慮皇后放置在 (0,1) 的所有可能。

這個方法稱為 回溯演算法 Backtracking Algorithm ，也就是一言不合就回頭。

接下來考慮將第二個皇后棋放置在 (1,1)

會發現其實路徑上還是有第一個皇后棋，所以之後的放置也不用考慮。

再來考慮放置在 (3,1)，並且觀察其攻擊路徑

會發現若把第二個皇后放置在這裡其攻擊路徑上不會有先前放置的皇后

所以到這邊我們可以以已知前兩個皇后擺放位置繼續往下考慮。

擺放第三個點 :

重複考量以上步驟，可以知道第三個點可以擺放的第一個位置為

3. C語言實作

可以參考最簡單的實作 N-Queens_1

3.1 檢查加入的點是否適當

我們考量到擺放第三個點時候的檢查，以擺放在 (3,2) 的皇后棋為例檢查攻擊路徑。
欲放置皇后棋 ( 3, 2 )

檢查該點 (3,2) 攻擊路徑 :

我們要檢查的路徑分為

1. 左上 (1,0) (2.1)
2. 直行 (3,0) (3,1)
3. 右上 (5,0) (4,1)

觀察規則我們可以發現檢查判斷非常簡單 :

INPUT:

1. (X,Y)欲加入的點並且檢查 -> int x ,int y
   y 同時代表的層數
2. table[8][8]

bool checkqueen(int x, int y, char **table,int n)
{
    for (int i = 0; i < y; i++)
        if (table[i][x] )
            return false;
	
	for(int i=x-1,j=y-1; i>=0&&j>=0 ; i--,j--)
		if (table[j][i] )
            return false;
	
    for (int i = x+1, j = y-1; j >= 0 && i < n; i++, j--)
        if (table[j][i] )
            return false;
    return true;
}

3.2 nqueen() 遞迴函式 :

以上我們得到判斷加入皇后棋的方法

我們會再 main() 中呼叫 nqueen(0,n);

第一個參數 0 為我們從棋盤中的第 0 行開始放置皇后棋，也是欲加入皇后棋的 y 座標
第二個參數 n 為 n-queen 的 'n' ，也就是 n * n 棋盤或者放置 n 個皇后

void nqueen(int line, int n,char**Table)
{
    int list;
	for (list=0; list<n; list++) {
        if (checkqueen(list, line,Table,n)) { 
            Table[line][list]='Q';
            if(line == n-1){
            	
            	Counts++;
            	printf("(%d)\n",Counts);
    			printTable(Table,n);
				Table[line][list]=0x00;
            	return;
			}
            nqueen(line+1,n,Table);
			Table[line][list]=0x00;
        }
    }
}

N-Queen_1 可以計算出當 n 等於任何正整數時候，皇后有多少種排法。

(91)

. . . . . . . Q 
. . Q . . . . . 
Q . . . . . . . 
. . . . . Q . . 
. Q . . . . . . 
. . . . Q . . . 
. . . . . . Q . 
. . . Q . . . . 

(92)

. . . . . . . Q 
. . . Q . . . . 
Q . . . . . . . 
. . Q . . . . . 
. . . . . Q . . 
. Q . . . . . . 
. . . . . . Q . 
. . . . Q . . . 

Count = 92

 ----- 1-queen -----
Count = 1
 ----- 2-queen -----
Count = 0
 ----- 3-queen -----
Count = 0
 ----- 4-queen -----
Count = 2
 ----- 5-queen -----
Count = 10
 ----- 6-queen -----
Count = 4
 ----- 7-queen -----
Count = 40
 ----- 8-queen -----
Count = 92
 ----- 9-queen -----
Count = 352
 ----- 10-queen -----
Count = 724
 ----- 11-queen -----
Count = 2680
 ----- 12-queen -----
Count = 14200
 ----- 13-queen -----
Count = 73712
 ----- 14-queen -----
Count = 365596
 ----- 15-queen -----
Count = 2279184

Leetcode 繳交

題目特別附註 :

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 
 char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){

}

returnSize 為個別結果矩陣的數量，不過關於結果矩陣 (上面我們跑1~15的結果) 並沒有公式解，所以這邊用個比較快且偷吃的方法 : 直接寫在矩陣中

int Arraysize[16]={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184};

稍微更改程式碼使其可以通過 LeetCode 版本 N-Queens Problem
每個陣列空間改成 n+1 為了對應LeetCode 資策環境

4. 空間以及效能改進