N-Queens II 使用回溯很慢 [英] N-Queens II using backtracking is slow
问题描述
n-queens 难题是将 n 个皇后放在 n x n 棋盘上的问题,这样就不会有两个皇后互相攻击.
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.
给定一个整数 n,返回 n-queens 难题的不同解的数量.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
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 时失败.我不知道为什么,以及如何减少迭代.看来我已经在做尽可能少的迭代了.
It fails at n=8. I can't figure out why, and how to have less iterations. It seems I am already doing the minimum iterations possible.
推荐答案
restricted
集似乎在时间和空间方面都是浪费的.在成功的递归结束时,n
层深度增长到 n^2
大小,这将总复杂度驱动到 O(n^3)代码>.它并不是真正需要的.通过查看已经放置的皇后更容易检查正方形的可用性(请原谅国际象棋术语;
file
代表垂直,rank
代表水平):
The restricted
set seems wasteful, both time- and space-wise. At the end of the successful recursion, n
levels deep it grows to n^2
size, which drives the total complexity to O(n^3)
. And it is not really needed. It is much easier to check the availability of the square by looking at the queens already placed (please forgive the chess lingo; file
stand for vertical, and rank
for horizontal):
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 倍).
And there is a plenty of room for the optimization. For example, you may want to special-case the first rank: due to a symmetry, you only need to inspect a half of it (cutting execution time by the factor of 2).
这篇关于N-Queens II 使用回溯很慢的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!