[回溯算法]python解决N皇后问题(20行代码)

如果读者对于回溯算法思路解法还不是很了解，可以先点击链接查阅我之前的一篇博文《算法之【回溯算法】详解》，很详细的介绍了回溯算法求解思路及方法，有利于你更好的学习回溯算法。

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

注：下图为 8 皇后问题的一种解法。

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

N皇后问题.png

示例1

输入：4 输出：
解法 1： [".Q..", "...Q", "Q...", "..Q."],

解法 2：["..Q.", "Q...", "...Q", ".Q.."]
解释: 4 皇后问题存在两个不同的解法。

问题分析

直接套用《算法之【回溯算法】详解》中的回溯算法基本步骤以及回溯算法的通用框架模板。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(board, row):
            if row >= n:
                # 此处是将每一行转换为题目要求的字符串形式,如"..Q."代表一行
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)  #保存结果
                return
            for i in range(n):
                if isValid(row, i, board): #isValid用于判断该位置是否合法，能够放置皇后
                    board[row][i] = 'Q'  #放置皇后
                    backtrack(board, row+1) # row+1进入下一行
                    board[row][i] = '.'  #回溯
        res = []
        board = [['.'] * n for _ in range(n)] # 初始化棋盘
        backtrack(board, 0) # row从0开始
        return res

1. 状态变量为行：row,每次在当前行选择完一个可以放置的皇后位置后进入下一行row+1;

2. 递归结束条件:当row>=n时，row从0开始，表示前n-1所有行的皇后均已放置完成，将结果添加到res中。

if row >= n:
    # 此处是将每一行转换为题目要求的字符串形式,如"..Q."代表一行
    cur_res = [''.join(row) for row in board]
    res.append(cur_res)
    return

3. 可选择的列表：每一行能够选择的位置为0到n-1，但是该位置是否能够被选择，需要满足皇后彼此不能相互攻击的条件。

此处判断是否能够相互攻击即判断当前位置(row, col)所在的列，右斜线方向即左斜线方向是否已经有皇后存在，如果有的话，则当前位置不能再放皇后。

判断是否有冲突的方式有两种：

方法一：直接通过循环判断

def isVaild(board,row, col):
    #判断同一列是否冲突
    for i in range(len(board)):
        if board[i][col] == 'Q':
            return False
    # 判断左上角是否冲突
    i = row -1
    j = col -1
    while i>=0 and j>=0:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j -= 1
    # 判断右斜线方向是否冲突
    i = row - 1
    j = col + 1
    while i>=0 and j < len(board):
        if board[i][j] == 'Q':
            return False
        i -= 1
        j += 1
    return True

方法二: 左斜线:同一斜线每个点row-col恒定; 右斜线：同一斜线每个点row+col恒定

左斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)和 (3,3)在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

左斜.png

右斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

右斜.png

下面我们主要使用第二种方法来进行判断所放置的位置是否合法。

def isValid(row, col):
            # 判断所放置的位置是否合法
            for i in range(row):
                for j in range(n):
                    # 注：左斜对角线上，同一条斜线上的每个位置满足行下标与列下标之差相等
                    # 注：右斜对角线上，同一条斜线上的每个位置满足行下标与列下标之和相等
                    if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
                        return False
            return True

最终代码

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def isValid(row, col):
            # 判断所放置的位置是否合法
            for i in range(row):
                for j in range(n):
                    if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
                        return False
            return True
        def backtrack(board, row):
            if row >= n:
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)
                return
            for i in range(n):
                if isValid(row, i, board):
                    board[row][i] = 'Q'
                    backtrack(board, row+1)
                    board[row][i] = '.'
        res = []
        board = [['.'] * n for _ in range(n)]
        backtrack(board,0)
        return res

代码优化：通过集合记录之前放置过元素的正向对角线，负向对角线，及列，判断当前点是否在集合中，在的话说明不满足要求，这种判断方式速度更快。

def solveNQueens(self, n: int) -> List[List[str]]:
        def isValid(row, col):
            # 如果该点所对应的右斜线或左斜线或列已经放置了皇后则放回Fasle
            if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash:
                return False
            return True
        def backtrack(board, row):
            if row >= n:
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)
                return
            for col in range(n):
                if isValid(row, col, board):
                    board[row][col] = 'Q'
                    pie_hash.add(row + col)
                    na_hash.add(row - col)
                    col_hash.add(col)
                    backtrack(board, row+1)
                    board[row][col] = '.'
                    pie_hash.remove(row + col)
                    na_hash.remove(row-col)
                    col_hash.remove(col)
        res = []
        board = [['.'] * n for _ in range(n)]
        pie_hash = set() # 记录放置了皇后的右斜线
        na_hash = set()  # 记录放置了皇后的左斜线
        col_hash = set() # 记录放置了皇后的列
        backtrack(board,0)
        return res

后续会继续更新关于回溯算法的相关题解，欢迎持续关注！
如果喜欢作者，欢迎点赞、收藏及关注，谢谢！