八皇后问题

　　国际象棋中皇后的吃子能力最强，皇后所处格子的纵、横、和对角线方向上的子都可以被皇后吃掉。国际象棋棋盘有8 x 8共64个格子，如何在上面放八个皇后而互相吃不着，这就是著名的八皇后问题。以下是我用C++编写的求解递归程序。

//The N-queen problem, see how concisely Xijiang has programmed
#include ＜iostream＞
using namespace std;
const int N=8;　　//Number of Queens or dimensions

void check(int* x, int n){
　if(n==Nx[0]==N) return;　//solution found, or exhausted
　　if(x[n]==N){　　　　 　//dead end, try the previous column
　　　x[n--]=0;　　　　　　//clear this column
　　　x[n]++;　　　　　　　//next element of previous column
　　　check(x,n);　　　　　//check it
　}
　int i,j,k,m;
　for(i=n-1, j=x[n], k=x[n]-1, m=x[n]+1; i＞=0; i--, k--, m++)
　if((j==x[i])(k==x[i])(m==x[i]))break;　//try this column
　if(i＜0) n++;　　　　　　　 //this column is OK, check next
　else　　x[n]++;　　　　　　//keep trying this column
　check(x,n);
}

int main(void){
　static int queen[N], c=1;　//ith element stores Queen's row position
　for(;;){　　　　　　　 //first check must start from 2nd row
　　check(queen, (c==1)?1:(N-1));　// rests start from last row
　　if(queen[0]==N)　　　break;　//exhausted, or a solution below
　　for(int i=0;i＜N;i++) cout＜＜' '＜＜(queen[i]+1);
　　cout＜＜'\t'＜＜c++＜＜endl;　//c: counter
　　queen[N-1]++;
　}
　return 0;
}

　　当棋盘路数和皇后数N = 8时，倘若将对称重复也计算在内，该问题共有92个解。根据抽屉原理，要保证有解，皇后数目不能超过棋盘路数，否则必定至少有两个皇后处在同一行或者列上。用以上程序可以求解N!＝8的情况。下表列出了解数目的情况。

　　Ｎ　４　　５　６　　７　　８　　　９　　１０　　　１１
　　解　２　１０　４　４０　９２　３５２　７２４　２６８０
　　Ｎ　　　　１２　　１３　　１４　１５
　　解　１４２００　３９１　４２４　　１

　　当N＜＝12时，解的数目似乎是可靠的；当N＞12时，程序异常中断，因而只算出了最先几个解，或者根本算不出解。由此也可以看出，精巧的构思与稳健的实现尚有不少距离。


后记：利用editbin (editbin queen.exe /stacks: 100000000) 修改堆栈大小，可以获得更大N的解。例如N = 13，73,712；N = 14，365,596；N = 15，2,279,184；N = 16，14,772,512 (16，14，12，15，4，8，3，5，2，11，1，10，13，6，9，7)。最后一个结果在我的PIV 2.4G笔记本上算了半个小时。另外在Linux系统上堆栈似乎比Windows系统中的默认堆栈大得多。