N皇后问题:在 n * n 的棋盘上要摆 n 个皇后,要求:任何两个皇后不同行,不同列也不在同一条斜线上,求给一个整数 n ,返回 n 皇后的摆法数。
#include <iostream> #include <math.h> #define N 8 using namespace std; int q[N + 1]; //q[i]表示第i个皇后在第i行上的第q[i]列 int check(int j) { //检查N皇后摆放的位置是否合法 for (int i = 1; i < j; i++) { if (q[i] == q[j] || abs(i-j)==abs(q[i]-q[j])) { //判断是否在同一列或同一斜线上 return 0; } } return 1; } void queen() { for (int i = 1; i <= N; i++) { q[i] = 0;//初始化 } int answer = 0;//方案数 int j = 1; //表示正在摆放第j个皇后 while (j >= 1) { q[j]++; //让第j个皇后向后一列摆放 while (q[j]<=N && !check(j)) {//判断第j个皇后的位置是否合法 q[j] = q[j]++; //不合法就往后一个位置摆放 } if (q[j] <= N) { //表示第j个皇后找到一个合法的摆放位置 if (j == N) {//找到了N皇后的一组解 answer++; cout << "方案" << answer << ":"; for (int i = 1; i <= N; i++) { cout << q[i] << " "; } cout << endl; } else { j++;//继续摆放下一个皇后 } } else {//表示第j个皇后找不到一个合法的摆放位置 q[j] = 0;//还原第j个皇后的位置 j--;//回溯 } } } int main() { queen(); system("pause"); return 0; }