python - N-Queens II 使用回溯很慢

Question

n-皇后拼图是将n 个皇后放在n x n 棋盘上的问题，这样就不会有两个皇后互相攻击。
给定一个整数 n，返回 n-queens 谜题的不同解的数量。
https://leetcode.com/problems/n-queens-ii/
我的解决方案:

class Solution:
    def totalNQueens(self, n: int) -> int:
        def genRestricted(restricted, r, c):
            restricted = set(restricted)
            for row in range(n): restricted.add((row, c))
            for col in range(n): restricted.add((r, col))
            movements = [[-1, -1], [-1, 1], [1, -1], [1, 1]]
            for movement in movements:
                row, col = r, c
                while 0 <= row < n and 0 <= col < n:
                    restricted.add((row, col))
                    row += movement[0]
                    col += movement[1]
            return restricted

        def gen(row, col, curCount, restricted):
            count, total_count = curCount, 0

            for r in range(row, n):
                for c in range(col, n):
                    if (r, c) not in restricted:
                        count += 1
                        if count == n: total_count += 1
                        total_count += gen(row + 1, 0, count, genRestricted(restricted, r, c))
                        count -= 1

            return total_count

        return gen(0, 0, 0, set())

它在 n=8 时失败。我不知道为什么，以及如何减少迭代。看来我已经在做尽可能少的迭代了。

Answer 1

restricted set 似乎很浪费，无论是时间上还是空间上。递归结束，n它增长到 n^2大小，这使总复杂度达到 O(n^3) .它并不是真正需要的。通过查看已经放置的皇后更容易检查正方形的可用性(请原谅国际象棋术语；file 代表垂直，rank 代表水平):

def square_is_safe(file, rank, queens_placed):
    for queen_rank, queen_file in enumerate(queens_placed):
        if queen_file == file:                      # vertical attack
            return false
        if queen_file - file == queen_rank - rank:  # diagonal attack
            return false
        if queen_file - file == rank - queen_rank:  # anti-diagonal attack
            return false
    return true

用于

def place_queen_at_rank(queens_placed, rank):
    if rank == n:
        total_count += 1
        return

    for file in range(0, n):
        if square_is_safe(file, rank, queens_placed):
            queens_placed.append(file)
            place_queen_at_rank(queens_placed, rank + 1)

    queens_placed.pop()

而且还有很大的优化空间。例如，您可能希望对第一等级进行特殊处理:由于对称性，您只需检查其中的一半(将执行时间减少 2 倍)。