剪枝:经过分析,如果当前路没必要走下去了,那么直接回头看下一条路。
方法一(逐行遍历)
从第一行的第一个方格开始看,当该方格所在的列、对角线、反对角线都没有其他方格时,放置一个 queen,然后从第二行第一个格子开始看。如果有,那么看第二个格子。
一列有无其他方格:bool col[N]
一条对角线有无其他方格:bool dg[N],每一条对角线用它在纵轴的截距来表示。即 b = u - i,为了防止出现负数,对正对角线统一加个偏移量 n,即 b = u - i + n,那么正对角线从右到左依次是:1,2,3,…
一条反对角线有无其他方格:bool udg[N],同理 b = u + i
正反对角线条数都是 2*n - 1 条,数组按这个上界开。
// 时间复杂度:n*n!
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u)
{
if(u == n)
{
// 下标最好从 0 开始,从 1 开始会有很多问题
for(int i = 0; i < n; i ++) puts(g[i]);
puts("");
// puts 函数用于输出以空字符结尾的字符串
return;
}
for(int i = 0; i < n; i ++)
{
if(!col[i] && !dg[u - i + n] && !udg[u + i])
{
g[u][i] = 'Q';
col[i] = dg[u - i + n] = udg[u + i] = true;
dfs(u + 1);
col[i] = dg[u - i + n] = udg[u + i] = false;
g[u][i] = '.'; // 这里就不能省略了,如果省略会影响下次
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
g[i][j] = '.';
dfs(0);
return 0;
}
方法二
这个虽然说的是逐个枚举,但其实还是做了一点点剪枝:枚举每个格子放不放 Q,如果要放,先检查是否满足条件(行,列,正反对角线),满足再放 Q。
// 时间复杂度:2^n^2
// 方法二:枚举每个格子放还是不放
#include <iostream>
using namespace std;
const int N = 20; // 以对角线个数的上界开的
char g[N][N];
bool col[N], row[N], dg[N], adg[N];
int n;
void dfs(int x, int y, int s)
{
// if(s > n) return;
if(y == n) x += 1, y = 0;
if(x == n)
{
if(s == n)
{
for(int i = 0; i < n; i++) puts(g[i]);
puts("");
}
return;
}
// 不放皇后
dfs(x, y + 1, s);
// 放皇后(每一行、列、对角线、反对角线上至多出现一次)
// 用对角线在纵轴的截距作为各对角线在数组中的索引
// 参数 y + x 与 y - x + n 何来?很简单,对角线方程:y = x + b, 反解出 b = y - x,
// 参数作为数组索引又不能为负数,因此加一个偏移量 n。另一个参数同理。
// 仔细想,dg 与 adg 其实一样,故可以颠倒里面的参数
// 再仔细想,x 与 y 其实也一样,故也可以颠倒
if(!col[x] && !row[y] && !dg[y - x + n] && !adg[y + x])
{
col[x] = row[y] = dg[y - x + n] = adg[y + x] = true;
g[x][y] = 'Q';
dfs(x, y + 1, s + 1);
// 恢复现场
col[x] = row[y] = dg[y - x + n] = adg[y + x] = false;
g[x][y] = '.';
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = '.';
dfs(0, 0, 0);
return 0;
}