【计算机算法设计与分析】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皇后问题的思路