改自課本p152. 八皇后問題
題目要求已經被我改得有點不一樣 大家可以看看這個code和課本上的code有何不同
題目: 在一個8*8的棋盤上 是否有一個方法可以放入八個皇后
並且皇后與皇后之間不會互相攻擊到
如果有解 則把這個解的每一排(每一個row)的皇后位置印出來
執行結果:
1 5 8 6 3 7 2 4
=========================== Code =============================================
#include<stdio.h>
int find(int i,int queen[]) // 嘗試在第i個row的各個coloumn放入皇后
{
int j,k;
if(i==8) // 終端條件 如果前8個row的皇后位置都已經猜完
// 並且猜測結果之間沒有互相衝突
{
for(j=0;j<8;j++) printf("%d ",queen[j]+1);
printf("\n");
return 1;
}
for(j=0;j<8;j++) // 把皇后放在第 i 個row的coloumn 0~7 看看是否有解
{
for(k=0;k<i;k++) // 檢查是否跟之前的某個皇后互相可以攻擊到
if(queen[k]==j ||
queen[k]+(i-k)==j ||
queen[k]-(i-k)==j
)
break;
if(k==i) // 如果與之前的皇后皆沒有衝突 則去問"下一層"是否有解
// 如果有衝突則在目前狀況下皇后不可能被放在(i,j)這格
{
queen[i]=j;
if(find(i+1,queen)==1) return 1;
// 如果下一層找到一個解 則"很高興地"說 "我找到解了!!"
}
}
return 0; // 怎麼樣都找不到解 莫可奈何只好自認倒楣說目前的情況沒有解
}
int main()
{
int queen[8]={0};
find(0,queen); // 從第0個row開始猜每個皇后的位置
scanf(" ");
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.132
※ 編輯: pp5438 來自: 140.112.30.132 (11/18 20:11)