N皇后问题——Python解决（超详细注释）

• N皇后问题
• • 1、问题
  • 2、思路
  • • • 1）棋盘表示
      • 2）不攻击检查
      • 3）dfs搜索实现
  • 3、代码总体实现
  • 4、结果展示

N皇后问题

前一段时间老师让我们做一道N后的算法题，对于刚学算法的我来说确实有亿点点困难，于是就开始查看力扣和csdn上大佬们的代码，下面是我对这道题的理解，希望可以对在这道题上有疑问的同学们有所帮助。（代码我参考了其他大佬们的，便于理解进行了一些些改动，如有侵权，可联系解决）

1、问题

n 后问题研究的是如果将 n 个皇后放置在一个 n×n 的棋盘上，使皇后彼此之间不能相互攻击（已知在同一行、同一列或者同一条斜线上，皇后之间都会相互攻击）。

2、思路

1）棋盘表示

我们用一个一维列表来表示棋盘，列表长度表示总行数，对应的数值表示皇后所在的是第几列。
比如 li = [1, 3, 0, 2] 即表示：棋盘是4行 * 4列，在第 1 行的第 2 个位置上 (因为[0] = 1) 存在一个皇后，同理，在第 2 行的第 4 个位置上 (因为li[1] = 3) 存在一个皇后，在第 3 行的第 1 个位置上 (因为li[2] = 0) 存在一个皇后，在第 4 行的第 3 个位置上 (因为li[3] = 2) 存在一个皇后。

2）不攻击检查

1. 是否处于同一列中
2. 是否在左斜线上：（行 + 列）的值不可相等
3. 是否在右斜线上：（列 – 行）的值不可相等

# 参数：当前列  位置总结果  当前行
def check(col, res, row):

    # 遍历已经放好皇后的所有行（不用判断是否在同一行，因为一行有值后，会进行到下一个 dfs）
    for i in range(row):

        # 1、是否在同一列中    2、左斜线：（行 + 列）的值相等    3、右斜线：（列 - 行）的值相等
        if res[i] == col or res[i] + i == row + col or res[i] - i == col - row:
            return False
    return True

3）dfs搜索实现

1. 结束条件：当前行数 = 皇后总数，即最后一行已经成功放入皇后
2. 循环一行中的每一个位置，若不发生攻击事件，可将皇后放入该位置，即将该位置的值赋成列数
3. 继续下一行的搜索，即传入的参数为当前行数 + 1

# 参数：皇后总数  位置总结果  当前放置第几行
def dfs(num, res, row):

    # 如果当前行数 = 皇后总数，结束跳出
    if row == num:
        print(res)
        return

    # 遍历 row 行中的每一列，判断是否可行
    for col in range(num):
        # 若可行
        if check(col, res, row):

            # 将该 row 行的数值改成列数 col
            res[row] = col

            # 进行下一行的搜索
            dfs(num, res, row + 1)

            # 若进行到这一步说明，上一步走后，后续无法再放置皇后，需要回溯
            # 也可以不回溯，因为进入下一个循环（将该 row 行的数值改成列数 col + 1）后，会重新对 res[row] 赋值
            res[row] = 0

3、代码总体实现

def dfs(num, res, row):
    if row == num:
        print(res)
        return
    for col in range(num):
        if check(col, res, row):
            res[row] = col
            dfs(num, res, row + 1)
            res[row] = 0


def check(col, res, row):
    for i in range(row):
        if res[i] == col or res[i] + i == row + col or res[i] - i == col - row:
            return False
    return True


if __name__ == '__main__':

    # num: 皇后的数量
    num = int(input('请输入皇后的数量：'))

    # 最终皇后的位置 （下标：第几行 数值：第几列）
    res = [0 for _ in range(num)]

    # 从第一行开始
    row = 0

    # 参数：皇后总数  位置结果  当前放置第几行
    dfs(num, res, row)

4、结果展示

棋盘及皇后位置：


最后，相信大家也看出来了，这两种情况就是将棋盘翻转了以下，位置都是差不多的。