——以“八皇后”为例
题目描述
一个如下的 \(6 × 6\) 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5 来描述，第 ii 个数字表示在第 ii 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 nn，表示棋盘是 \(n × n\) 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
题目分析
深搜经典题，深搜思路大致是按列遍历，从第一行往下开始走
比方说我们在第一行第一列放置一枚棋子，进入第二行，显然第二行的第一列和第二列都不符合，那就放到第三列，以此类推。
那么也就是说，本题的核心其实是写出一个check函数用以判断在当前位置放置一个棋子是否合法。由于不能在同一行同一列同一对角线。
同一行与同一列的去重其实好办，难度就是在对角线的判断，我这里使用了两个数组进行暴力处理，也就是记录这一条对角线是否有放置，粗暴但有效
Accepted Code
/*
* @Author: Gehrychiang
* @Date: 2019-12-12 22:19:26
* @LastEditors : Please set LastEditors
* @LastEditTime : 2020-01-31 12:21:40
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt=0;//记录情况总数
int table[14][14] = {0};//保存皇后地图
int zuoxie[28] = {0};//记录左斜方向
int youxie[28] = {0};//记录右斜方向
bool check(int x, int y)//检查在当前位置填充是否合法
{
//列
for (int i = 0; i < x; i++)
{
if (table[i][y] == 1)
return false;
}
//斜
if (zuoxie[x + y] != 0 || youxie[x - y + n - 1] != 0)
return false;
return true;
}
//深搜思路是在第x行遍历 列的1到n 能放进就进入下一行
void dfs(int x) //x行
{
if (x == n)//一种情况已经结束，此时将结果输出，并返回上一层
{
if (cnt < 3)
{
for (int u = 0; u < n; u++)
{
for (int v = 0; v < n; v++)
{
if (table[u][v] == 1)
cout << v + 1 << " ";
}
}
cout << endl;
}
++cnt;
return;
}
for (int y = 0; y < n; y++)
{
if (check(x, y))
{
//情况改变，去重并记录
++zuoxie[x + y];
++youxie[x - y + n - 1];
table[x][y] = 1;
dfs(x + 1);
//回到当前节点，回溯
--zuoxie[x + y];
--youxie[x - y + n - 1];
table[x][y] = 0;
}
}
return;
}
int main()
{
cin >> n;
dfs(0);
cout << cnt << endl;
return 0;
}