八皇後問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。計算機發明後，有多種方法可以解決此問題。
維基百科中的解釋:
八皇後問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇後，使得任何一個皇後都無法直接吃掉其他的皇後？為了達到此目的，任兩個皇後都不能處於同一條橫行、縱行或斜線上。八皇後問題可以推廣為更一般的n皇後擺放問題：這時棋盤的大小變為n×n，而皇後個數也變成n。當且僅當 n = 1 或 n ≥ 4 時問題有解。
基本要求就是這樣:同行,同列,同對角線不能有棋子就OK了. 我的數據結構課本上給的提示是用遞歸的方法做.所以我就把我的代碼寫一下.順便做下注釋.如果大家有更好的解法,可以給我說哦. 我發現我的代碼量有點多,由於我不太懂那些用一維數組的方法,所以我的方法顯得有點笨,但是好歹可以做出來.
#include<stdio.h>
int queen[8][8]; //定義一個二維數組,存放棋盤
int m=1; //定義解法個數
int check(int i,int j)
//檢查函數,結果用k返回,如果k=0,則所有的檢查位置都符合條件,可以放棋子
{ int k=0;int a,b;
for(a=0;a<i;a++)//檢查同列是否有棋子
if(queen[a][j]==1)
k++;
for(a=i-1,b=j-1;a>=0&&b>=0;a--,b--)//檢查左對角線元素
if(queen[a][b]==1)
k++;
for(a=i-1,b=j+1;a>=0&&b<8;a--,b++)//檢查右對角線元素
if(queen[a][b]==1)
k++;
return k;
}
void put(int i) //遞歸函數,放棋子
{ int j;
if(i>=8) //當i大於等於8時,輸出已經放好的棋子,i從0開始
{
printf("第%d種解法:\n",m++);
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
if (queen[i][j]==1 )
printf("%d ",j);
else printf("- ");
printf("\n");
}
printf("\n");
}
else //遞歸放棋子
for(j=0;j<8;j++)
{ queen[i][j]=1;
if(check(i,j)==0)
put(i+1);
queen[i][j]=0;
}
}
int main() //主函數
{put(0);
return 0;
} 輸出格式為: "第X種解法: 棋盤布局;"
