Leetcode 51. N皇后问题(N Queens) Python解法

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

解题思路

N皇后问题是一道典型的递归求解问题，常见为8皇后、4皇后问题。递归对象为在$0 -(n-1)$0−(n−1)行的皇后已经放置的基础上，第$n$n行皇后应该放置的位置，直到最后一行，递归结束，返回满足条件的放置位置。

Python代码

class Solution:
    def solveNQueens(self, n):
        res = set()		# 存放每行的皇后放置的坐标
        # 递归
        def find_pos(row_index, queen, n):
            for j in range(n):
                if pos_available(queen, (row_index, j)):
                    queen[row_index] = j
                    if row_index == n-1:    # 已经是最后一行并且找到了可以放的位置
                        res.add(tuple(queen))
                        return
                    else:   #没到最后一行
                        find_pos(row_index+1, queen, n)
		# 检验当前位置是否可用
        def pos_available(queen, pos):
            # 放第i行  根据0~i-1行进行判断
            for i in range(pos[0]):
                if queen[i] == pos[1]:  # 同列
                    return False
                elif abs(i-pos[0]) == abs(queen[i]-pos[1]): # 主副对角线
                    return False
            return True
		# 把坐标形式打印成 Q...形式
        def plot_queen(queen, n):
            out = []
            for i in range(n):
                s = '.' * queen[i] + 'Q' * 1 + '.' * (n-queen[i]-1)
                out.append(s)
            return out

        # 初始皇后位置-1  其实没有影响
        queen = [-1 for _ in range(n)]  # 初始位置
        # 递归  从第0行开始
        find_pos(0, queen, n)
        out = []
        for t in res:
            out.append(plot_queen(t, n))
        return out

# 测试代码
test = Solution()
print(test.solveNQueens(4))

输出样例

[['.Q..', 
  '...Q', 
  'Q...', 
  '..Q.'], 
 ['..Q.', 
  'Q...', 
  '...Q', 
  '.Q..']]