N皇后问题

N皇后问题

输入一个正整数N，则程序输出N皇后问题的全部摆法。

输出结果里的每一行都代表一种摆法，行里的第i个数字如果是n，就代表第i行的皇后应该放在第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)//函数调用的前提是0~k-1行的皇后已经摆好 {//使用递归其实已经不用考虑行的情况了，让一行摆一个，只需要考虑列以及斜线是否冲突即可！ 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); } } }