C語言編程問題
10
【問題描述】8個皇後在一個8*8的棋盤上下棋，一個皇後放入一個棋子後，另一個皇後所放的棋子不能與前一個皇後所放的棋子在同一行、同一列（在每一橫列豎列斜列只有一個皇後），將所有可能的棋子放法求出來。
【要 求】采用如下方式之一輸出棋盤：（1）以數組的形式輸出棋盤；（2）以圖形方式輸出棋盤。
最佳回答：
#include <stdlib.h>
#include <stdio.h>
int m[8][8] = {0};//表示棋盤，初始為0，表示未放置皇後
int num = 0;//解數目
//對於棋盤前row-1行已放置好皇後
//檢查在第row行、第column列放置一枚皇後是否可行
bool check(int row,int column) // 1,1 2,1 2,2 2,3
{
if(row==1) return true;
int i,j;
//縱向只能有一枚皇後
for(i=0;i<=row-2;i++)
{
if(m[i][column-1]==1) return false;
}
//左上至右下只能有一枚皇後
// i = row-2;
// j = i-(row-column);
// row - 2 - row + column
i = row - 2;
j = column - 2;
while(i>=0&&j>=0)
{
if(m[i][j]==1) return false;
i--;
j--;
}
//右上至左下只能有一枚皇後
i = row-2;
// j = row+column-i-2;
j = column;
while(i>=0&&j<=7)
{
if(m[i][j]==1) return false;
i--;
j++;
//當已放置8枚皇後，為
}
return true;
}
//可行解時，輸出棋盤
void output()
{
int i,j;
num++;
printf("answer %d:\n",num);
for(i=0;i<8;i++)
{
for(j=0;j<8;j++) printf("%d ",m[i][j]);
printf("\n");
}
}
//采用遞歸函數實現八皇後回溯算法
//該函數求解當棋盤前row-1行已放置好皇後，在第row行放置皇後
void solve(int row)
{
int j;
//考慮在第row行的各列放置皇後
for (j=0;j<8;j++)
{
//在其中一列放置皇後
m[row-1][j] = 1; // 1,0
//檢查在該列放置皇後是否可行
if (check(row,j+1)==true)
{
//若該列可放置皇後，且該列為最後一列，則找到一可行解，輸出
if(row==8) output();
//若該列可放置皇後，則向下一行，繼續搜索、求解
else solve(row+1);
}
//取出該列的皇後，進行回溯，在其他列放置皇後
m[row-1][j] = 0;
}
}
//主函數
int main()
{
//求解八皇後問題
solve(1);
return 0;
}
/* 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0
*/
