描述

在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）

分析

递归求解。 在k个皇后已经摆好位置的情况下，找出第k+1个皇后可以放的位置。

如果尝试到的第k+1个皇后的位置与前k个皇后所在的位置不重复，并且第k+1个皇后所在的位置，与之前每一个皇后所在位置的行间距不等于列间距，那么我们就找到了第k+1个皇后的位置。

代码

#include <iostream> #include <cstring> #include <cmath> using namespace std; void queen(int k); int queenPos[20]; int N; int main() { cin >> N; queen(0); return 0; } void queen(int k) { if(k == N) { for(int i = 0; i < N; i++) { cout << queenPos[i] + 1 << " "; } cout << endl; return; } for(int i = 0; i < N; i++) { int j; for(j = 0; j < k; j++) { if(queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j)) break; } if(j == k) { queenPos[k] = i; queen(k + 1); } } }