Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Backtracking solution in Clear category for Stepping Stones Puzzle by Phil15
from itertools import product
def stepping_stones(n: int, ones: list[tuple[int, int]]) -> int:
grid = [[0] * n for _ in range(n)]
sums = [[0] * n for _ in range(n)]
def update_sums(r: int, c: int, diff: int) -> None:
for i, j in product(
range(max(0, r - 1), min(r + 2, n)),
range(max(0, c - 1), min(c + 2, n)),
):
sums[i][j] += diff
for r, c in ones:
grid[r][c] = 1
update_sums(r, c, 1)
best = 1
def backtrack(k: int) -> None:
nonlocal best
for r, c in product(range(n), repeat=2):
if grid[r][c] == 0 and sums[r][c] == k:
grid[r][c] = k
update_sums(r, c, k)
if k > best:
best = k
backtrack(k + 1)
grid[r][c] = 0
update_sums(r, c, -k)
backtrack(2)
return best
Jan. 25, 2023
