Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Peaceable Queens by tokiojapan55
from functools import lru_cache
def peaceable_queens(size: int) -> int:
CELLS = [(r, c) for r in range(size) for c in range(size)]
@lru_cache
def occupy(qr: int, qc: int) -> set:
result = set()
for dr, dc in [(0, 1), (1, 0), (1, 1), (1, -1)]:
for n in range(-size, size + 1):
rc = (qr + dr * n, qc + dc * n)
if rc in CELLS:
result.add(rc)
return result
def free_cells(queens: list):
restrict = set()
for qr, qc in queens:
restrict |= occupy(qr, qc)
return size**2 - len(restrict)
occupy.cache_clear()
stack, answer = [[(0, 0)]], 0
while stack:
queens = stack.pop()
free = free_cells(queens)
if free >= len(queens):
answer = max(answer, len(queens))
if free > len(queens):
free, candidate = None, []
for rc in [rc for rc in CELLS if rc not in queens]:
n = free_cells(queens + [rc])
if free == None or free < n:
free = n
candidate = [rc]
elif free == n:
candidate.append(rc)
if candidate and free > len(queens):
stack.extend(queens + [c] for c in candidate)
return answer
Jan. 17, 2024
Comments:
