題目連結: https://zerojudge.tw/ShowProblem?problemid=d324
# 內容
在西洋棋得棋盤中你可以放置 8 個皇后而且彼此都不衝突（就是都不能吃到對方）。給你某一個皇后的位置，請你寫一個程式來輸出所有這樣可能的安排。
# 解題思路
一維陣列 queen [8]，陣列索引為皇后的 col，值為皇后的 row
將所有可能都走一遍，運用回溯法探索吧～～
# 程式碼
#include<bits/stdc++.h> | |
using namespace std; | |
int queen[9]; | |
int ans; | |
void walk(int); | |
int main(){ | |
int n; cin>>n; | |
while(n--){ | |
int x,y; ans=0; | |
cin>>x>>y; | |
memset(queen,-1,sizeof(queen)); | |
queen[y]=x; | |
cout<<"SOLN COLUMN\n # 1 2 3 4 5 6 7 8\n\n"; | |
walk(1); | |
} | |
} | |
bool check(int floor){ | |
for(int i=1;i<floor;i++){ | |
if(queen[i]==queen[floor])return false; | |
if(queen[floor]-queen[i]==floor-i)return false; | |
if(queen[floor]-queen[i]==i-floor)return false; | |
} | |
return true; | |
} | |
void walk(int floor){ | |
if(floor==9){ | |
printf("%2d ",++ans); | |
for(int i=1;i<=8;i++) | |
cout<<queen[i]<<" "; | |
cout<<endl; return; | |
} | |
if(queen[floor]>0) { | |
if(check(floor)) walk(floor+1); | |
} | |
else{ | |
for(int i=1;i<=8;i++){ | |
queen[floor]=i; | |
if(check(floor)) walk(floor+1); | |
queen[floor]=-1; | |
} | |
} | |
} |
