【计算机算法设计与分析】n皇后问题（C++_回溯法）

题目描述

在nxn格的棋盘上放置彼此不受攻击的n格皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

当n=6时，一个如下的 6×6 的跳棋棋盘：

上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子。这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。并把它们以上面的序列方法输出，解按字典顺序排列。请输出前三个解。最后一行是解的总个数。

测试样例

输入：

6

输出：

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

算法原理

       使用回溯法对解空间进行深度优先搜索遍历，同时要满足规则（任何两个皇后不放在同一行或同一列或同一斜线上），为节省时间我创建了四个数组：x[1000], y[1000], zr[1000], zl[1000]，分别存储横轴、纵轴、左对角线、右对角线上是否已被占用的信息。其中，x[i]=j表示在第i行第j个位置放置一个皇后（方便输出结果）；y[j]=1表示第j列已被占用；zr[i - j + n]=1表示这条从左上到右下的对角线已被占用（所有处于同一条左上到右下对角线上元素的横坐标减纵坐标都相同，为了让索引为正，所以加n）；zl[i+j]=1表示这条从右上到左下的对角线已被占用（所有处于同一条右上到左下对角线上元素的横坐标加纵坐标都相同）。

算法实现

#include<bits/stdc++.h>
using namespace std;int n, num = 0;
int x[1000], y[1000], zr[1000], zl[1000];
void print()
{if (num < 3){for (int i = 1; i <= n; i++)cout << x[i] << " ";cout << endl;}num++;
}
void dfs(int i)
{if (i > n){print();return;}else{for (int j = 1; j <= n; j++){if ((!y[j]) && (!zr[i - j + n]) && (!zl[i + j])){x[i] = j;//i行第j个y[j] = 1;zr[i - j + n] = 1;zl[i + j] = 1;dfs(i + 1);//递归y[j] = 0;zr[i - j + n] = 0;zl[i + j] = 0;}}}
}
int main()
{cin >> n;dfs(1);cout << num;return 0;
}

参考资料

回溯法之n皇后问题总结_用回溯法求解n皇后问题的思路