Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Backtracking solution in Clear category for Peaceable Queens by Phil15
NEIGHBORS = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1),
]
def peaceable_queens(size: int) -> int:
if size == 0:
return 0
in_grid = frozenset((r, c) for r in range(size) for c in range(size))
# `influences[r * size + c]` is the set of the positions attackable by a queen at row r and column c.
influences = [
frozenset(
(r + s * dr, c + s * dc)
for dr, dc in NEIGHBORS
for s in range(size)
) & in_grid
for r in range(size)
for c in range(size)
]
max_depth = size ** 2
max_queens, nb_queens, free = 0, 0, in_grid
def backtrack(recursion_level: int):
nonlocal max_queens, nb_queens, free
if recursion_level == max_depth or max_depth - recursion_level < max_queens - nb_queens:
# Reach the end of the grid OR there are not enough remaining cells to get more queens than the max.
return
# Try with a queen at this new position: `(row, column) = divmod(recursion_level, size)`.
new_free = free - influences[recursion_level]
# Enough free places for opposite queens?
if len(new_free) >= nb_queens + 1:
backup, free = free, new_free
nb_queens += 1
if nb_queens > max_queens:
max_queens = nb_queens
# Is there place for even more queens?
if len(free) > nb_queens:
backtrack(recursion_level + 1)
nb_queens -= 1
free = backup
# Or without a queen at the position.
backtrack(recursion_level + 1)
backtrack(0)
return max_queens
if __name__ == '__main__':
import time
for size, answer in (1, 0), (2, 0), (3, 1), (4, 2), (5, 4), (6, 5), (7, 7):
t = -time.perf_counter()
assert peaceable_queens(size) == answer, (size, answer)
t += time.perf_counter()
print(f'{size}: {t:.6f} seconds')
Feb. 1, 2023
Comments:
