P1219 [USACO1.5] 八皇后 Checker Challenge

题目链接

P1219 [USACO1.5] 八皇后 Checker Challenge

思路

深搜的导入

实际上，本题是一个搜索可行路径的题，假如标记了已放置的皇后的行、列、正对角线(从左上到右下的对角线)、副对角线(从左下到右上的对角线)，则接下来的皇后只需要放在棋盘中未被标记的位置，如果放够了题目要求的数量 $n$ ，则让结果加一。

对于搜索可行路径的题，有一种算法——深度优先搜索，学名 $dfs(DepthFirstSearch)$ 。该算法的思想是一条路走到尽头，然后回头走别的路。可见该算法是一种暴力枚举，即将所有可能的值都枚举一遍，然后对其进行操作，算法复杂度可见一斑。故需要在搜索时进行剪枝，即满足某个条件就中断对某条路的搜索，这样会减少深度优先搜索的无效搜索。

使用深度优先搜索搜索一个二叉树时，对于单个节点会有两次访问，第一次是递归的时候访问，第二次是回溯的时候访问，递归时会对状态数组(如果访问过，则值不为零；否则为零)进行操作，为了防止回溯时受到先前操作的影响，应该在回溯前恢复操作以前的状态数组。

剪枝

如果不进行剪枝，我们可以将所有的结果枚举出来，如何判断结果是否为可行解，时间复杂度为 $O(n^2)$ ，显然不是个好的算法。

故需要进行剪枝，使用状态数组来记录能否放置皇后，只有能放置皇后时，才进行放置，然后再放置下一个皇后，这样可以减少很多无效解。

错误思想

最简单的思想是用一个二维数组记录不能放置皇后的位置和能放置皇后的位置，分别用$1$和$0$表示；然后思考该怎样标记行、列、正副对角线，这也十分简单，对于标记行和列，直接使用 $for$ 循环遍历即可，对于正副对角线，给四个方向(左上、右上、左下、右下)遍历，直到碰到边界为止；最后考虑如何在回溯之前撤销标记，按标记的顺序撤销就可以了吗？显然是不行的，因为撤销标记时可能会撤销上一个皇后的标记，故需要用别的方法来进行标记。

正确思想

状态数组

深入思考，发现可以用四个数组分别来存储行、列、正对角线、副对角线的状态，分别定义为 $a[],b[],c[],d[]$ 。

$a[i]$ 表示第 $i$ 行放置了第 $i$ 个皇后，而 $a[i]$ 的值是该皇后的列数；$b[i]=1$ 表示第 $i$ 列放置了皇后；$c[i+j]=1$ 表示第 $i+j$ 条正对角线放置了皇后；$d[i?j+n]=1$ 表示第 $i?j+n$ 条副对角线放置了皇后。

如果 $b[i]$ 为 $1$ ，则说明第 $i$ 列不能放皇后；如果 $c[i]$ 为 $1$ ，则说明第 $i$ 条正对角线不能放皇后；如果 $d[i]$ 为 $1$ ，则说明第 $i$ 条副对角线不能放皇后。

放置皇后

对于 $n$ 个皇后，如果在第 $num$ 行的第 $i$ 列放置了一个皇后，则应先记录 $a[num]=i$ ，然后再标记 $b[i]=c[num+i]=d[num?i+n]=1$ ，接着放置下一个皇后，最后撤销标记 $b[i]=c[num+i]=d[num?i+n]=0$ ，直到放置完 $n$ 个皇后为止。

代码

#include <iostream>
using std::cin, std::cout;
/*
    n表示n * n棋盘的行数与列数
    total表示共有多少种放置方式
    cnt_print表示打印了多少种放置方式
*/
int n, total, cnt_print;
const int Size = 105;						// 数组的大小
/*
    a[i]表示第i行的a[i]位置放置了皇后
    b[i]表示第i列有没有放置皇后
    c[i]表示第i条正对角线有没有放置皇后(从左下到右上的对角线)
    d[i]表示第i条副对角线有没有放置皇后(从左上到右下的对角线)
*/
int a[Size], b[Size], c[Size], d[Size];
// 该函数用于放置第num个皇后，第num个皇后在第num行
void placeQueen(int num) {
    if (num > n) {							// 如果放置的皇后数大于n个
        if (cnt_print++ < 3) {				// 如果记录的打印位置的次数小于3次
            for (int i = 1; i <= n; i++) {	// 则打印n个皇后的位置
                cout << a[i] << " ";
            }
            cout << '\n';
        }
        total++;							// 摆放的方式+1
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0 && c[num + i] == 0 && d[num - i + n] == 0) {
            a[num] = i;						// 第num行的第a[num]列放置了皇后
            
            // 标记第i列、第num + i条正对角线、第num - i + n条副对角线
            b[i] = c[num + i] = d[num - i + n] = 1;

            placeQueen(num + 1);			// 放置下一个皇后

            // 回溯时撤销上面的标记
            b[i] = c[num + i] = d[num - i + n] = 0;
        }
    }
}
int main() {
    cin >> n;
    placeQueen(1);							// 放置第一个皇后
    cout << total;
    return 0;
}