輸入一個正整數(shù)N，則程序輸出N皇后問題的全部擺法。
輸出結(jié)果里的每一行都代表一種擺法，行里的第i個數(shù)字如果是n，就代表第i行的皇后應(yīng)該放在第n列。 皇后的行和列編號都是從1開始！
4
2 4 1 3
3 1 4 2
#include <iostream>#include <cmath>using namespace std;int N;int queenPos[100];void NQueen(int k);//最左上角為(0, 0)int main(){ cin >> N; NQueen(0);//從第0行開始擺放 return 0;}void NQueen(int k)//函數(shù)調(diào)用的前提是0~k-1行的皇后已經(jīng)擺好{//使用遞歸其實已經(jīng)不用考慮行的情況了，讓一行擺一個，只需要考慮列以及斜線是否沖突即可！ if(k == N)//全部擺好直接輸出即可 { for(int i=0; i<N; i++)//輸出N行的皇后位置 cout << queenPos[i]+1 << " "; cout << endl; return; } //沒有全部擺好 for(int i=0; i<N; i++) //第k個皇后的擺法，也即是在第k行的擺法。遍歷此行的所有列！ { int j; for(j=0; j<k; j++)//判斷和第0~k-1行的皇后是否沖突 { if(queenPos[j]==i || abs(queenPos[j]-i)==abs(k-j)) {//判斷斜對角線線是否沖突的方法 行之差和列之差的絕對值是否相等 break; } } if(k==j)//沒有沖突 { queenPos[k] = i; NQueen(k+1); } }}新聞熱點
疑難解答
