45 lines
1.1 KiB
Python
45 lines
1.1 KiB
Python
import random
|
|
from typing import Callable
|
|
|
|
from .board import Board
|
|
|
|
|
|
def solve(
|
|
state: Board,
|
|
is_solved: Callable[[Board], bool],
|
|
*,
|
|
history: list[tuple[int, Board]] | None = None,
|
|
shuffle: bool = False,
|
|
) -> list[tuple[int, Board]] | None:
|
|
|
|
if history is None:
|
|
# create starting state
|
|
history = [(-1, state)]
|
|
|
|
if is_solved(state):
|
|
return history
|
|
|
|
buttons = state.buttons
|
|
if shuffle:
|
|
buttons = random.sample(buttons, len(buttons))
|
|
|
|
for button in buttons:
|
|
# try to click all buttons
|
|
next = state.click(button)
|
|
|
|
if next is not None:
|
|
# click successful
|
|
binary_history = (
|
|
state.binary_repr
|
|
for _, state in history
|
|
)
|
|
|
|
if next.binary_repr not in binary_history:
|
|
# "next" is a new state
|
|
solution = solve(
|
|
next, is_solved,
|
|
history=[*history, (button, next)]
|
|
)
|
|
|
|
if solution is not None:
|
|
return solution
|