chapter_backtracking/n_queens_problem/

[giscus[bot]]

chapter_backtracking/n_queens_problem/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_backtracking/n_queens_problem/

[mathidot]

牛啊 解法写的清晰易懂

[aabighead]

K神您好！相较于网上其他的解题思路，您的代码简单高效。
但是我在运行上面的代码的时候，发现结果不正确。
我觉得剪枝的时候应该是且的关系，即同一列、同主对角线、副对角线均未被Q占据。能否改成下述代码：
if(!cols[col] && !diags1[diag1] && !diags2[diag2])
感谢解答！

[krahets]

Hi 谢谢，可以分享下结果不正确的测试样例吗？

if(!cols[col] && !diags1[diag1] && !diags2[diag2]) 和 !(cols[col] || diags1[diag1] || diags2[diag2]) 是等价的，后者也只有在三者都为 false 时输出 true

不过我觉得有必要改写成你的写法，我原先的写法有些绕了

[aabighead]

抱歉，是我没有看清楚！的括号数量，感谢解答

[krahets]

没事啊，欢迎讨论与提问！

[aabighead]

您好，感谢解答！ 我使用N=4，正确的排列结果应该是2种，但是程序输出165种。 改为if(!cols[col] && !diags1[diag1] && !diags2[diag2])后，输出为2种。后续我测试了N=5、6、7，结果分别是10种、4种、40种。 附件中是我的测试样例。 祝好！

…

------------------ 原始邮件 ------------------ 发件人: "krahets/hello-algo" ***@***.***>; 发送时间: 2023年6月20日(星期二) 中午1:58 ***@***.***>; ***@***.******@***.******@***.***>; 主题: Re: [krahets/hello-algo] chapter_backtracking/n_queens_problem/ (Discussion #484) Hi 可以分享下结果不正确的测试样例吗？ if(!cols[col] && !diags1[diag1] && !diags2[diag2]) 和 !(cols[col] || diags1[diag1] || diags2[diag2]) 是等价的，后者也只有在三者都为 false 时输出 true — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***>

[krahets]

请问你运行的是哪个语言？我本地运行是正确的

[aabighead]

我使用的是C++。 抱歉，是我没有看清楚！后面括号包含三个关系。我的测试样例中if后面有问题。 感谢您的解答！

[zhuasdfg]

实在是泰裤辣！逻辑清晰，代码也通俗易懂，注释也详细，k神yyds！

[WhiteRhinos]

这个对角线判断就简单了,我之前都是直接遍历

 public static void main(String[] args)
    {
        int len = 8;
        int[][] chess = new int[len][len];
        // put(chess,1,1);
        putChess(chess, 0);

    }

    public static int solution = 0;

    public static void putChess(int[][] chess, int time)
    {
        // 扫描了所有行就结束
        if (time == chess.length)
        {
            solution++;
            System.out.println("第" + solution + "种解法");
            for (int[] ints : chess)
            {
                for (int i = 0; i < ints.length; i++)
                {
                    if (ints[i] == 1)
                    {
                        System.out.print(i+" ");
                        break;
                    }
                }
            }
            System.out.println();
            return ;
        }

        for (int i = 0; i < chess[time].length; i++)
        {
            // 如果是0表示可以放棋,1表示已经放置棋子
            if (chess[time][i] == 0)
            {
                //缓存落子之前的状态用于恢复
                int[][] temp = tempArr(chess);
                // 标记无法放置棋子的区域,和放置棋子的位置
                put(chess, time, i);
                // 一层只能放一个
                putChess(chess, time+1);
                //恢复上一次落子
                chess = temp;
            }
        }

    }

    /**
     * 落子
     * @param chess 棋盘
     * @param cI 落子位置
     * @param cJ 落子位置
     */
    public static void put(int[][] chess, int cI, int cJ)
    {
        int tj1 = cJ;
        int tj = cJ;
        //每层只放一个棋子,所以只需要关注列和斜线
        for (int i = cI; i < chess.length; i++)
        {
            chess[i][cJ] = 2;

            if (tj + 1 < chess[i].length && i + 1 < chess.length)
            {
                chess[i + 1][++tj] = 2;
            }
            if (tj1 - 1 >= 0 && i + 1 < chess.length)
            {
                chess[i + 1][--tj1] = 2;
            }
        }

        // 1表示放置了棋子
        chess[cI][cJ] = 1;
    }

    /**
     * 暂存棋盘
     * @param arr 棋盘
     */
    public static int[][] tempArr(int[][] arr)
    {
        int[][] temp = new int[arr.length][];
        for (int i = 0; i < arr.length; i++)
        {
            temp[i] = Arrays.copyOf(arr[i],arr[i].length);
        }
        return temp;
    }

[hellomawen]

看不懂原文判断对角线的方法，于是参照着写了一版:joy:

def valid(state: list[list[bool]], row: int, col: int):
    n = len(state)

    for i in range(row):
        _row = state[i]

        # 对角线
        if i != row:
            offset = abs(row - i)

            if col - offset > -1 and _row[col - offset]:
                return False

            if col + offset < n and _row[col + offset]:
                return False

        for j in range(n if i < row else col):
            # 行
            if i == row and _row[j]:
                return False

            # 列
            if j == col and _row[j]:
                return False

    return True


def backtrack(
        state: list[list[bool]],
        row: int,
        col: int,
        count: int,
        res: list[list[list[bool]]]
):
    n = len(state)

    if count == n:
        res.append([i[:] for i in state])
        return

    for i in range(row, n):
        for j in range(col, n):
            if not valid(state, i, j):
                continue

            count += 1
            state[i][j] = True

            # 本行已放子，尝试下一行
            backtrack(state, i + 1, 0, count, res)

            count -= 1
            state[i][j] = False

        # 回到第一列
        col = 0


def nQueen(n: int):
    res = []

    # 棋盘状态
    state = [[False for _ in range(n)] for _ in range(n)]

    backtrack(state, 0, 0, 0, res)

    return res

[WhiteRhinos]

你二维数组你当作坐标系看就好了,在同一直线的点肯定满足y=k*x+b

[Syl-Ying]

diags2: list[bool], 后面多打了一个逗号哈哈哈

[krahets]

Python 代码使用 black 进行标准格式化。

最后一行保留逗号比较方便，因为添加一行就不用再专门添加末尾句号了。

[ogjqn112]

K神您好！想请问一下为什么在记录解时将代码res.append([list(row) for row in state])改为res.append(state)会导致无法输出正确的结果呢？

[krahets]

Hi ，state 指向一个列表对象，如果我们 res.append(state) ，则是将这个 state 对象加入到 res 中，之后 state 发生变化时，添加进 res 中的对象也会发生变化（因为实际上从始至终只有一个 state 对象）。

然而，res.append([list(row) for row in state]) 这是在将 state 进行拷贝后再加入 res ，这样做之后，state 的变化将不会影响 res 中记录的状态了。

[ogjqn112]

明白啦！感谢k神解答！

[YuhangGuan]

谢谢K神，我有同样的疑问。我换成 res.append(list(state))为什么也不行？13.3的code为什么就可以？

[krahets]

@YuhangGuan 棋盘是一个二维列表，res.append(list(state)) 只拷贝了外面的一维，内部每一行的列表没有进行拷贝。你可以试试深拷贝 res.append(copy.deepcopy(state)) ，别忘了 import copy

[zeinsshiri]

/ 计算该格子对应的主对角线和副对角线
int diag1 = row - col + n - 1;
为什么要+n-1呢？

[krahets]

row - col 的取值范围是 [-n, n] ，加 n-1 后才能映射到数组索引范围 [0, 2n-1] 。

[newcakes]

简单说索引不为负数

[iiamdone]

关于这个问题
row 和 col在矩阵索引的取值范围是 [0,n - 1]，于是 row - col 的数值范围是 [-n+1,n-1]；
对于主对角线diags1数组的数组长度为 2n-1，既 n×n 矩阵中的N皇后问题上主对角线上有 2n-1 个信息，对应是索引值为 [0,2n-2];
所以在[-n+1,n-1]+n-1后映射到主对角线 2n-1 个信息构成的数组diags的索引值 [0,2n-2] 上;

我认为这里需要区分的是row col的数值取值范围（1,2,...,n）和row col在矩阵索引值的取值范围（0,1,2,...,n-1）的区别。不知道我这样理解对不对

[Sail38]

主要是因为目的是要用 diag[index] 去标记一条对角线是否已经被使用了， 所以这个是index， 也就是楼上说的

简单说索引不为负数

[newcakes]

写的太好了，尤其是图画的好，学起来好轻松！

[KinoHui]

想问下这个row+col的范围为什么是[0,2n-2],不是[2,2n]

[krahets]

Hi，因为长度为 $n$ 的数组最大索引是 $n-1$

[KinoHui]

感谢解答

[Excelsiorl]

hi，我对这里的空间复杂度有一些困惑：
在递归调用时，不需要在每个栈帧空间内都存储一个state矩阵吗？

[krahets]

不需要，状态 state 在搜索时不断变化，所有递归函数共享同一个 state 。你看我们在递归函数里也没有新建 state 呀

[Excelsiorl]

好的 感谢你的回答 我明白了

[Codec-k]

数组 diag1 和 diag2 的长度都为 2n-1，这里应该是diags1和diags2吧?

[clearwater753]

you are right

[krahets]

谢谢指正！

[SoftwareEngineerPalace]

要我说 本来就应该用 diag1 而不是 diags1，diag 的意思是表格，只有一个表格，没必要加 s 表复数

表格可以用 diag 或 grid
一个格子可以用 grid 或 cell

[likz1994]

每次看都觉得不可思议。老实说，我就很好奇，生活中究竟是多优秀的人，才能写出这样代码

[krahets]

"Hard work beats talent when talent doesn't work hard." --Tim Notke

[syutengu]

天道酬勤

[jmjfjjd]

state[i][n]不是溢出了吗，假如是4X4棋盘，n=4=Maxsize,最大的数组不是[1][3]吗？

[coder-yangxin]

看源码有以下定义：

#define MAX_SIZE 100

[Bratrindersteak]

求教一个问题：解集res的个数与n无关，但res[i]与res[i][i]的个数都为n，那么res占用的空间是不是O(n^2)呢？

[EndlessCheng]

时间复杂度的分析有些问题，递归到 base case row == n 时，需要用 O(n^2) 的时间生成一个二维棋盘加入 res，所以总的复杂度应该是 O(n^2 * n!)

[krahets]

谢谢指正！

[clfeng]

请教一下，目前不是很理解为什么是O(n^2 * n!)；对棋盘的复制并不是每次迭代都会进行而是只有在得到解的时候才会进行的，因此时间复杂度应该是 O(n! + n * n^2)吧？

[xlyyddy]

我也有这样的疑惑，n!*n^2不就是意味着有n！次需要生成一个二维棋盘加入res吗，但显然不可能啊

[Tianwangm]

K神，您好！我想请问一下为什么将记录解的代码改成res.add(new ArrayList<>(state)；之后的结果出错了呢？

[krahets]

Hi，因为 state 是个二维列表，你的写法只拷贝了外面一层列表。（两个维度的列表都需要拷贝，即深拷贝）

[YuhangGuan]

K神，有个问题想请教，为什么 diag1 = row - col + n - 1, 而不是 diag1 = col - row + n - 1？

当遍历到（row=1, col=2) 时(第一个queen已经放在第一行第一列)，尝试将queen放在这个位置，随后diags1[diag1]=T，使得diags1=[FFTTFFF]，但是以图13-18为例，queen放在第二行第三列，diags1应该是[FFFTTFF]。

我哪里的理解出了问题？

[krahets]

可以再推推，row 是行号（垂直的 Y 轴），col 是列号（水平的 X 轴）

[YuhangGuan]

K神，请问图13-18里的diags的index是从左下到右上为0到6还是从右上到左下为0到6啊？

[1394225561]

我理解的是两种都可以，索引0从哪边开始并不影响判断主对角线是否存在皇后，同一条主对角线上的row - col是一个恒定值

[ruihao-yan]

应该是右上角到左下角

[macj2010]

按照之前的逻辑写下来，比较顺畅

# 回溯方法，n皇后问题 state列表记录每一行纵坐标 如[0,2,1]-> 第一个皇后坐标(0,0)，第二个(1,2)
# state: 表示每一行皇后的纵坐标，取值0~n，n: 表示n皇后问题，res：结果列表
# 皇后的坐标为(x, y)，x代表棋盘的横坐标，y代表棋盘的纵坐标
def trackback_queen(state: list[int], n: int, res: list[list[int]]):
    if len(state) == n:
        res.append(list(state))
        return
    # 新插入的皇后坐标 (i, len(state))
    for i in range(n):
        flg = True
        # 遍历state中的皇后坐标 (state[j], j)
        for j in range(len(state)):
            # 横坐标相等 或者 纵坐标相等(纵坐标必不相等，跳过检查) 或者 横纵坐标的差相等（绝对值）
            if state[j] == i or abs(i - state[j]) == abs(j - len(state)):
                flg = False
                break

        if flg is True:
            state.append(i)
            trackback_queen(state, n, res)
            state.pop()

# 入口函数
def trackback_queen_fn(n: int) -> list[list[int]]:
    res = []
    trackback_queen([], n, res)
    return res 

[leeyiding]

hello，关于go语言版本，我有些小疑惑
在条件判断部分

if !(*cols)[col] && !(*diags1)[diag1] && !(*diags2)[diag2] {

感觉三个条件的顺序并不会影响判断结果，但是经过测试，当把!(*cols)[col]这个条件排在后边时，如

if !(*diags1)[diag1] && !(*diags2)[diag2] && !(*cols)[col] {

会出现索引越界的错误panic: runtime error: index out of range [7] with length 7
在条件判断前一行通过打印fmt.Println(row, col, diag1, diag2)

0 0 3 0
1 0 4 1
1 1 3 2
1 2 2 3
2 0 5 2
2 1 4 3
2 2 3 4
2 3 2 5
1 3 1 4
2 0 5 2
2 1 4 3
3 0 6 3
3 1 5 4
3 2 4 5
3 3 3 6
2 2 3 4
2 3 2 5
0 1 2 1
1 0 4 1
1 1 3 2
1 2 2 3
1 3 1 4
2 0 5 2
3 0 6 3
3 1 5 4
3 2 4 5
4 0 7 4

发现会出现row==n的情况下，又继续执行循环了。
之后我又测试了python版本的代码，替换条件的顺序并不会影响结果。
对于上述现象非常疑惑，希望各位能帮忙解惑
go version go1.22.0 linux/amd64

[leeyiding]

仔细想了一会，好像大概明白了，在!(*cols)[col]判断中，条件已经为false了，所以后面的判断直接就跳过了，不会触发索引越界。
Python版本之所以更改后也不会影响，是因为在记录解后，直接return了，不会进入判断这一步了。
其他语言的解法都有return，唯独Golang版本没有写return，所以不能随意变更判断条件顺序。

[2419174660]

图示中两个对角线的数组名称是不是标反了

[hfrangon]

我感觉也是 浅蓝色的diags1才是行列合相同的吧

[krahets]

在主对角线（diags1）上，从左上角到右下角，行列索引同时增加，因此行列索引的“和”在增加，行列索引的“差”恒定。

[juvenn]

对于棋盘，我们可以用一个一维的 int 数组来表示。每个元素表示第 i 排的皇后所在的 j 列。比如state[0] = 1 ，就表示第 0 排的皇后在第 1 列。这样我们就可以将空间复杂度缩小到 O(2N) 。

大致的算法如下

func backtrackNQueens2(state []int, N int, occupiedCols []bool,
  occupiedDiag1 []bool, occupiedDig2 []bool, ret *[][]int) {
    if len(state) == N {
      board := append([]int{}, state...)
      *ret = append(*ret, board)
      return
    }
    row := len(state)
    for j := 0; j < N; j++ {
      if occupiedCols[j] || occupiedDiag1[row+j] || occupiedDig2[row-j+N-1] {
        continue
      }
      state = append(state, j)
      occupiedCols[j] = true
      occupiedDiag1[row+j] = true
      occupiedDig2[row-j+N-1] = true
      backtrackNQueens2(state, N, occupiedCols, occupiedDiag1, occupiedDig2, ret)
      state = state[:len(state)-1]
      occupiedCols[j] = false
      occupiedDiag1[row+j] = false
      occupiedDig2[row-j+N-1] = false
    }
}

[nors1993]

图13-18.，主次对角线说反了。

[nfrjyrymccan]

没有反, 矩阵的主次对角线就是这样

[chy1984]

图没有反，主、次对角线的规律 / 公式反了。【主对角线上所有格子的 row- col 为恒定值，row1 - col1 = row2 - col2；次对角线上的所有格子的 row + col 是恒定值】应该是说反了

[chy1984]

忽略，图和规律/公式都是对的。

[krahets]

矩阵的起始点是“左上角单元格”，矩阵的行索引是“从上至下”依次增加的，列索引是“从左至右”依次增加的。

相对地，数学中的坐标系的原点一般在左下角，这与矩阵起始点的习惯不同。

[zhengComing]

主对角线是从左上到右下，diags1容易误解

[syutengu]

学习感想：

1. ”棋盘每行都允许且只允许放置一个皇后“。
   n个皇后必须均匀分布在n行，每一行的皇后数不是0或2,3...，必须是1。
   这是逐行填充以提前剪枝的思想起点。

2. ”主对角线上所有格子的 row-col 为恒定值“，"次对角线上的所有格子的 row+col 是恒定值"。
   这里n-1不加也能用（至少js），只是主对角线数组的索引值变成[-n+1,n-1]了。

const diag1 = row - col + n - 1;
const diag2 = row + col;

自己写的代码没有这两个优化，要慢很多。非常受启发。

[BK-Go-Python]

大佬我没想明白，判断对角线不应该把之前放过的皇后都判断一遍，为啥代码只判断上一个就行，不用判断上一个之前的皇后吗

[zzzMaple]

对角线和次对角线上所有的 diag1 和 diag2 是恒定值

[Mrstarer]

补充，时间复杂度，个人认为for循环无论在哪一层都应该操作n次，故不考虑其他的原来操作次数是n+n*n+n^3+n^4+……+n^n，故为n^n，但是能进入到下一层的递归函数会逐渐锐减，原来每个i都能进入下一层递归函数，从而执行n循环操作，现在有些路直接断了，怎么办呢？第一层显然仍为n，往下传的节点数量为n，第二层路径开始截断但是每个i仍有完整for循环，n^2,其截出来的路径每个i保底少于n-1，故往下传的节点数量小于n(n-1),第三层每个节点for循环故小于n(n-1)*n，往下传的节点数量小于n(n-1)(n-2),…………第n层循环小于n！*n，上一层传下来的节点数量小于n！，故对于深拷贝复制的时间复杂度至多就有O(n!*n^2)了(可当成上界函数了，虽然放缩的太远了），再来计算每一层的for循环小于O(n+n^2+……+n！*n),故最终时间复杂度取n！*n，小于O(n!*n^2)。而这还没考虑回退操作总体，但其实其根本改变不了整体时间复杂度了，因为太大了目前。这只是最离谱的情况，事实上真正能走到底的路径很少，中途能连上的很少，所以for循环操作次数和深拷贝的解个数都远小于n+n^2+……+n！*n)和n!