【回溯法】八皇后问题

2023-05-16

问题描述

在国际象棋棋盘 ( 8 × 8 ) (8\times8) (8×8)上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。
皇后可以攻击处于同一行、同一列和同一对角线上的棋子。

思路分析

八皇后问题可以使用搜索(DFS)的方法来解决，下面的解题思路摘自百度百科

八皇后问题如果用穷举法需要尝试 8 8 = 16 , 777 , 216 8^8=16,777,216 88=16,777,216种情况。每一列放一个皇后，可以放在第 1 1 1 行，第 2 2 2 行，……，直到第 8 8 8行。穷举的时候从所有皇后都放在第 1 1 1行的方案开始，检验皇后之间是否会相互攻击。如果会，把列H的皇后挪一格，验证下一个方案。移到底了就“进位”到列G的皇后挪一格，列H的皇后重新试过全部的 8 8 8行。这种方法是非常低效率的，因为它并不是哪里有冲突就调整哪里，而是盲目地按既定顺序枚举所有的可能方案。
回溯算法优于穷举法。将列A的皇后放在第一行以后，列B的皇后放在第一行已经发生冲突。这时候不必继续放列C的皇后，而是调整列B的皇后到第二行，继续冲突放第三行，不冲突了才开始进入列C。如此可依次放下列A至E的皇后，如图2所示。将每个皇后往右边横向、斜向攻击的点位用叉标记，发现列F的皇后无处安身。这时回溯到列E的皇后，将其位置由第4行调整为第8行，进入列F，发现皇后依然无处安身，再次回溯列E。此时列E已经枚举完所有情况，回溯至列D，将其由第2行移至第7行，再进入列E继续。按此算法流程最终找到如图3所示的解，成功在棋盘里放下了8个“和平共处”的皇后。继续找完全部的解共 92 92 92个。
回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。为了加快有无冲突的判断速度，可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志，回溯时挪动一个旧皇后清除标志。

思路概述

既然是用回溯(DFS)的方法来解决，那么我们首先要找到搜索的边界条件以及搜索的范围。
显然如果我们已经找到了八个互相不能攻击的皇后的位置我们就可以将该种情况输出并返回。

那么使用回溯法怎么避免产生重复的结果呢？
我们就要看搜索函数的具体实现方法。
如果是对整个棋盘范围使用一个二重遍历对【每个方块】进行搜索的话，最终肯定会产生大量重复的解。
但我们需要注意到一个关键的地方，由于棋盘的长度和宽度都是8，而一共只有8个皇后需要放置，每一行和每一列不能有重复的皇后，因此一行和一列上最多只能有一个皇后！
所以我们可以根据皇后的【行】或者【列】来进行搜索，当在这一行/这一列上找到合法的皇后位置后，我们就可以进入下一行/下一列进行搜索，如果不满足，就返回这一层，若满足，继续往下搜索直至搜索完全部八行/列。

以行为例说明

我们以行为例进行说明（列的情况同理）

我们需要明确，我们是从上一行进入到这一行的函数空间的，因此我们可以使用一个循环对【列】进行遍历，寻找这一行的哪一列是不与之前所摆放的皇后冲突的，找到合适的安放位置后就对下一行进行搜索。

通常我们写回溯法需要一个标记数组来避免重复搜索，但在这个问题中若应用不当会引起意想不到的问题，请看下面

因此我们需要一个记录答案（皇后摆放位置）的数组和一个标记由前面已摆放的皇后的攻击范围的数组，（它们都是二维的,8*8大小即可），注意第二个数组也可以不用，后面会说由它带来的问题，我们只需判断摆放位置是否合法即可，因此我们可以向前寻找该格子的行、列、对角线（之前)是否有已经放置答案的格子。

给这个满足条件的位置打上标记（答案数组），然后去标记它的行，列以及对角线上的元素。
当函数返回到这一空间时，我们要复原标记。此时就会搜索该行的下一个列直至搜索完成返回，这样一层层返回直到第一行搜索完毕。

在搜索的过程中如果搜索完了第八行说明已经找到了一个解，我们将答案数组输出即可。

思考：如果需要统计解的个数怎么做？
答案：可使用一个全局变量，若输出解，计数器加一

履行过程中的细节

我们再来看看一些细节问题：
如果给已经放置皇后的攻击范围的格子打上标记？
我们还是以行为例

我们只需要给判断已经合法的格子的下面、左下和右下方向的格子打上标记即可，并不需要再按照题意给格子右边（同一行）的格子打上标记，因为我们是按照行来进行搜索的，不会产生多解问题。

首先我们将棋盘上的方块视为点。因为每一个方块的位置都可以用 ( x , y ) (x,y) (x,y)坐标表示，所以说可以将其视作平面直角坐标系 x o y xoy xoy中的一个点。

原始棋盘
new chessboard
假定我们选取点 ( 0 , 0 ) (0,0) (0,0)作为一个放置皇后的位置，（当然在选点之前要检查是否合法）
我们要标记和它同一列的点，即直线 x = x 0 x=x_0 x=x0上的点（ x 0 x_0 x0是该点的行数）
0,0 col
对于对角线（注意有两条对角线）上的点，我们可以求出它们的方程
y = x + b y=x+b y=x+b
y = x − b y=x-b y=x−b
代入已知点 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)可求出 b b b
从而给直线上的点打上标记
在这里插入图片描述

在这里我们知道点 ( r o w , i ) (row,i) (row,i)的位置
可以求得方程为
y = − x + r o w + i y=-x+row+i y=−x+row+i
y = x + i − r o w y=x+i-row y=x+i−row

使用for循环来对棋盘中的每行（ x x x）对应的方程中的列数（ y y y）打上标记

代码实现

八皇后问题属于思路比较容易，但在写代码的时候可能遇到各种各样的问题，如果没有加以独立思考，在下次遇到这个问题也很可能写不出能正常运行的代码出来。

请看下面这个代码，你能找到它的错误吗？

void dfs(int row)
{
    if (row == 8)
    {
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
                cout << bd[i][j] << " ";
            cout << endl;
        }
        return;
    }
    for (int i = 0; i < 8; i++)
    {
        if (vis[row][i]) //若该点处于之前放置皇后攻击范围则跳过
            continue;
        bd[row][i] = true; //记录该点位置（已经在此放置皇后）
        //给它的攻击范围打上标记（只用打该店行数之后的标记就可以了）
        for (int j = row + 1; j < 8; j++)
            vis[j][i] = true;
        // 45 degree
        for (int j = row + 1; j < 8; j++)
            if (row + i - j >= 0 && row + i - j < 8)
                vis[j][row + i - j] = true;
        // 135 degree
        for (int j = row + 1; j < 8; j++)
            if (i - row + j >= 0 && i - row + j < 8)
                vis[j][i - row + j] = true;
        dfs(row + 1);
        //复原之前打过的标记（注意：这里有问题）
        bd[row][i] = false;
        // 45 degree
        for (int j = row + 1; j < 8; j++)
            if (row + i - j >= 0 && row + i - j < 8)
                vis[j][row + i - j] = false;
        // 135 degree
        for (int j = row + 1; j < 8; j++)
            if (i - row + j >= 0 && i - row + j < 8)
                vis[j][i - row + j] = false;
	}
}

上面的代码是完全按照正确的思路编写的，但是却产生了非常多的解并且很多解是不合法的！

原因在于：
每当函数从dfs函数返回到当前函数空间时，接着执行标记数组的“复原”过程，于是之前我们把该皇后位置所能覆盖的攻击范围的点全部还原成了false，可是这无意之中改变了标记数组vis中的值，因为在还原过程中有一些点在进入dfs函数前的标记过程前已经是true，还原的时候也应该将其置为true

这一疏忽造成了前面已经放置皇后的行所产生的攻击范围被错误地覆盖掉了，产生了错误的解。请看图
错误产生的原因
之所以会覆盖之前打过的标记，是因为当标记列元素和标记对角线元素的直线的方程产生了交点（他们来自不同的皇后），而这个交点被错误的删除了！

解决方法：使用三个分开的标记数组 c o l col col d i a 1 dia1 dia1 d i a 2 dia2 dia2来分别标记同一列和同一条对角线上的元素

另外还应该注意到在标记对角线时候可能会出现越界问题，请留心

一种正确的代码

void dfs(int row)
{
    if (row == 8)
    {
        cout << "No." << ++cnt << endl;
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
                cout << bd[i][j] << " ";
            cout << endl;
        }
        return;
    }
    for (int i = 0; i < 8; i++)
    {
        if (vis[row][i])
            continue;
        bd[row][i] = true;
        bool backup[8][8];
        memcpy(backup, vis, sizeof(vis));
        for (int j = row + 1; j < 8; j++)
            vis[j][i] = true;
        // 45 degree
        for (int j = row + 1; j < 8; j++)
            if (row + i - j >= 0 && row + i - j < 8)
                vis[j][row + i - j] = true;
        // 135 degree
        for (int j = row + 1; j < 8; j++)
            if (i - row + j >= 0 && i - row + j < 8)
                vis[j][i - row + j] = true;

        dfs(row + 1);
        bd[row][i] = false;
        memcpy(vis, backup, sizeof(vis));
	}
}

在上面的这一种改正方法中，使用了一个临时数组来保存刚进入函数时标记数组的值，最后将标记数组复原成原始数组。

但是这种方法增加了我们时间开销：我们要将至少该点前面行数的标记数组的值全部复制，这与不用标记数组直接回去检查答案数组的时间复杂度相当。

请你想一下如何在不花费额外时间的情况下复原标记数组（只有一个）,欢迎在评论区留言~

典型例题

YBT1213：八皇后问题

【题目描述】

在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

【输入】

(无)

【输出】

按给定顺序和格式输出所有八皇后问题的解（见样例）。

【输入样例】

（无）

【输出样例】

1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
No. 2
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
...以下省略

题解

观察样例给出的输出顺序猜测是按照以列进行搜索的，只需改动一下标记时坐标点顺序即可。
另外用一个全局变量来记录编号

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
#define endl '\n'
#define PY puts("Yes")
#define PN puts("No")
bool vis[8][8];
bool bd[8][8];
int cnt;
void dfs(int col)
{
    if (col == 8)
    {
        cout << "No. " << ++cnt << endl;
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
                cout << bd[i][j] << " ";
            cout << endl;
        }
        return;
    }
    for (int i = 0; i < 8; i++)
    {
        if (vis[i][col])
            continue;
        bd[i][col] = true;
        bool backup[8][8];
        memcpy(backup, vis, sizeof(vis));
        for (int j = col + 1; j < 8; j++)
            vis[i][j] = true;
        // 45 degree
        for (int j = col + 1; j < 8; j++)
            if (col + i - j >= 0 && col + i - j < 8)
                vis[col + i - j][j] = true;
        // 135 degree
        for (int j = col + 1; j < 8; j++)
            if (i - col + j >= 0 && i - col + j < 8)
                vis[i - col + j][j] = true;

        dfs(col + 1);
        bd[i][col] = false;
        memcpy(vis, backup, sizeof(vis));
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    dfs(0);
    return 0;
}

Luogu P1219 [USACO1.5]八皇后 Checker Challenge

题目描述

一个如下的 6 × 6 6 \times 6 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5 来描述，第 i i i 个数字表示在第 i i i 行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6 1\ 2\ 3\ 4\ 5\ 6 1 2 3 4 5 6

列号 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 3 3 个解。最后一行是解的总个数。

输入格式

一行一个正整数 n n n，表示棋盘是 n × n n \times n n×n 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

样例 #1

样例输入 #1

样例输出 #1

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

提示

【数据范围】
对于 100 % 100\% 100% 的数据， 6 ≤ n ≤ 13 6 \le n \le 13 6≤n≤13。

题目翻译来自NOCOW。

USACO Training Section 1.5

题解

这是一个n皇后问题
与前面的题目类似，同样可以按照行来进行搜索。
但是这里改用三个分开的标记数组（一维）来避免冲突
同时只用在行答案数组中记录列数就可

#include<iostream>
using namespace std;
int n;
int pos[14];
bool col[14],dia1[28],dia2[28];
int t;
void dfs(int x)
{
    if (x>n)
    {
        if (t<3)
        {
            for (int i=1;i<=n;i++)
                cout<<pos[i]<<" ";
            cout<<endl;
        }
        t++;
        return ;
    }
    for (int i=1;i<=n;i++)
    {
        if (col[i]||dia1[i+x]||dia2[i-x+n])
            continue;
        pos[x]=i;
        col[i]=true;
        dia1[i+x]=true;
        dia2[i-x+n]=true;
        dfs(x+1);
        col[i]=false;
        dia1[i+x]=false;
        dia2[i-x+n]=false;
    }
}
int main()
{
    cin>>n;
    t=0;
    dfs(1);
    cout<<t;
    return 0;
}

在上面的代码中将坐标进行了一个加 n n n的操作来防止下标小于 0 0 0的情况，省去了条件判断的代码

拓展练习

LeetCode51. N 皇后

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)