子寒的博客
0%

leetcode51 N-Queens 解题报告

发表于 更新于 分类于

英文原题

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

pic

分析

    queens能进攻的范围是米字（横竖再加两个斜线）。这题得用递归搜索构建棋盘，一行一行构建，很明显每一行只能放一个’Q’，接下来要考虑的就是新的一行的’Q’和斜线，竖线两个方向的冲突。我用(x1, y1) 和 (x2, y2)来表示两个’Q’:     - 竖线方向：x1 != x2     - 左上到右下的斜线：(x1-y1)+n-1 != (x2-y2)+n-1     - 右上到左下的斜线：x1+y1 != x2+y2 满足以上条件两个’Q’就不冲突。

python 代码

    board是构建的棋盘，board_s是用来记录目前depth前面的’Q’位置的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board_s = [-1 for _ in range(n)]
        
        def available(depth, j):
            for i in range(depth):
                if board_s[i] == j or i-board_s[i]+n-1 == depth-j+n-1 or i+board_s[i] == depth+j:
                    return False
            return True
        
        def dfs(depth, board):
            if depth == n:
                res.append(board)
                return
            for j in range(n):
                if available(depth, j):
                    col = '.' * n
                    board_s[depth] = j
                    dfs(depth+1, board+[col[:j] + 'Q' + col[j+1:]])
                
        dfs(0, [])
        return res