八皇後問題 ：假設 將八個皇後放到國際象棋盤上，使其兩兩之間無法相互攻擊。共有幾種擺法？ 基礎知識： 國際象棋里，棋盤為8X8格。 皇後每步可以沿直線、斜線 走任意格。 思路： 1.想把8個皇後放進去，肯定最終每行只有一個皇後，每列只有一個皇後。 2.設個二維數組chess [ i ] [ j ] ...
八皇後問題 ：假設 將八個皇後放到國際象棋盤上，使其兩兩之間無法相互攻擊。共有幾種擺法？
基礎知識：
國際象棋里，棋盤為8X8格。
皇後每步可以沿直線、斜線 走任意格。
思路：
1.想把8個皇後放進去，肯定最終每行只有一個皇後，每列只有一個皇後。
2.設個二維數組chess [ i ] [ j ] 模擬棋盤，cas存放擺法。i j 是表示i行j列：
寫一個用於遞歸的函數，思路如下
3.從上往下一行行的放皇後，放下一行時從最左邊（第0列）放起，如果不能放就往右挪一格再試。註意判斷右邊有沒有越界出棋盤。
4.寫一個函數專門判斷當前位置能不能放，只需要判斷該位置的橫、豎、兩對角線，這四條線上有沒有其他皇後即可。命名為check。
5.如果把最後一行放完了，那就統計上這個擺法，cas++。擺完最後一行不能繼續判斷下一行了。
6.放完一種情況，還要探究其他情況，可以把現在放好的皇後“拿走”，然後再試探 之前沒試探過的棋盤格。
7.拿走皇後操作可以和不能放皇後的操作用同樣的代碼實現：
如果這個位置不能放，要把它置零，表示沒有皇後。
如果這位置能放，那就放皇後（置1）。等一種情況討論完，還得把它拿開，“拿開”也是置零的操作。
所以應該想辦法排列上述代碼，保證已經把擺出的情況記錄下來，之後執行“拿開皇後”代碼。
下麵是遞歸函數部分：
void queen(int i,int j){
if(j>=line){ //如果右側越界
return ;
}
if(check(i,j)==1){//如果能放
chess[i][j]=1;//放皇後
if(i==line-1){//如果是最後一行，記錄情況
cas++;
}
else{
queen(i+1,0);//不是最後一行就分析下一行
}
}
//下麵這兩句是最精彩的chess[i][j]=0;//如果此位置不能放，就置空（0），判斷旁邊的格子。//如果此位置能放，走到這裡就意味著上面的代碼全部執行了，把皇後拿走（置零），再討論其他情況，拿旁邊位置試探。
queen(i,j+1);
}
然後開始寫判斷函數check。需要判斷的是8個方向，把它看成4條直線考慮。對於所在的橫行，豎列，直接用for迴圈判斷。接下來考慮對角線（紅色）。
這樣可以看出來，要判斷的對角線是每個象限的平分線，每次 i ，j 的變化量是相等的，只是符號有差異。橫縱坐標變化量的範圍是-8~8，當對角線走到邊框時停止判斷。
為什麼是-8到8呢？因為咱們沒必要確定對角線的精確範圍，上圖是最理想的對角線，但是因為目標位置不同，對角線範圍也不同，每次計算兩端點是不可取的。
直接按最長對角線劃：
核心代碼：
for(k=-line;k<=line;k++){//兩對角線
if(i+k>=0&&i+k<line&&j+k>=0&&j+k<line)//從左上到右下對角線，如果在棋盤格裡
if(chess[i+k][j+k]==1) return 0;
if(i-k>=0&&i-k<line&&j+k>=0&&j+k<line)//從左下到右上對角線，如果在棋盤格裡
if(chess[i-k][j+k]==1) return 0;
}
這個判斷函數不重要，你寫的函數達到目的就行。
註意一點，此函數只能設計成判斷功能，不可以改變棋盤格的填充。
我剛開始覺得，當放置完上一個皇後，直接把這皇後所在的橫縱斜方向全部填充一個數字，列為‘‘禁地’’，下一皇後放置時只要看待放入位置是否是“禁地”即可。但這麼做是錯的，因為不是把棋盤格填好一次就ok了，擺好一次後還需要把最後放的棋子拿開，探討其他情況。如果劃分禁地後，拿走皇後還得把禁地複原了，很麻煩的說。。而且代碼量也不節省，就這麼判斷就行。
代碼塊的思路講完，下麵是完整代碼。運行結果：92.
你寫的程式也要保證這個結果。
#include<stdio.h>
#define line 8
void queen(int i,int j);
int check(int i,int j);
int queennumber=8;
int chess[line][line];
int cas=0;
int main(){
queen(0,0);
printf("%d\n",cas);
return 0;
}
void queen(int i,int j){
if(j>=line){
return ;
}
if(check(i,j)==1){//如果能放
chess[i][j]=1;//放皇後
if(i==line-1){//如果是最後一行，記錄情況
cas++;
}
else{
queen(i+1,0);//不是最後一行就分析下一行
}
}
chess[i][j]=0;//如果此位置不能放，就置空（0），判斷旁邊的格子。
//如果此位置能放，走到這裡就意味著上面的代碼全部執行了，把皇後拿走（置零），再討論其他情況，拿旁邊位置試探。
queen(i,j+1);
}
int check(int i,int j){
int k;
for(k=0;k<line;k++){
if(chess[i][k]==1) return 0;//0=不能放
}
for(k=0;k<line;k++){
if(chess[k][j]==1) return 0;
}
for(k=-line;k<=line;k++){//兩對角線
if(i+k>=0&&i+k<line&&j+k>=0&&j+k<line)//從左上到右下對角線
if(chess[i+k][j+k]==1) return 0;
if(i-k>=0&&i-k<line&&j+k>=0&&j+k<line)//從左下到右上對角線
if(chess[i-k][j+k]==1) return 0;
}
return 1;
}
