八皇后要求一个8×8格的棋盘上放置8个皇后使得她们不能相吃。按照国际象棋的规则一个皇后可以吃掉与她处于同一行、同一列、同一对角线上的任何棋子因此每一行只能摆放一个皇后。八皇后等价于要求在一个8×8格的棋盘上放置8个皇后使得任何2个皇后不能放在同一行或同一列或同一对角线上。 853121=769 图1 解空间树中一条随机路径所对应的棋盘状态 输入数据 8 输出数据 2算法分析 对于n后问题皇

#include #include //用到绝对值函数

using namespace std;

bool check(int* x, int k) { //判断第k个皇后是否安全 for (int i = 1; i < k; i++) { if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k])) { //同一列或同一对角线 return false; } } return true; }

void queen(int* x, int n, int& count) { //n为皇后数量，count为方案数的引用 if (n == 0) { //递归边界，找到了一组方案 count++; return; } for (int i = 1; i <= 8; i++) { //枚举第n个皇后的位置 x[n] = i; if (check(x, n)) { //若安全，则继续递归下一个皇后 queen(x, n - 1, count); } } }

int main() { int x[9] = {0}; //用一维数组存放皇后位置，x[1]~x[8]分别表示第1~8行的皇后位置 int count = 0; //方案数 queen(x, 8, count); cout << count << endl; return 0;