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]

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

[jyhdashuaibi]

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

[krahets]

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

[jyhdashuaibi]

感谢解答

[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

[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]

谢谢指正！

[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啊？

[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.，主次对角线说反了。

[krahets]

Hi，可以具体说明一下为什么反了嘛？

[nfrjyrymccan]

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