Solve 8-puzzle using A* algorithm. >>> solve_puzzle([[1,2,3],[4,0,5],[7,8,6]], [[1,2,3],[4,5,6],[7,8,0]]) is not None True
(
initial_board: List[List[int]], goal_board: List[List[int]]
)
| 60 | |
| 61 | |
| 62 | def solve_puzzle( |
| 63 | initial_board: List[List[int]], goal_board: List[List[int]] |
| 64 | ) -> Optional[PuzzleState]: |
| 65 | """ |
| 66 | Solve 8-puzzle using A* algorithm. |
| 67 | |
| 68 | >>> solve_puzzle([[1,2,3],[4,0,5],[7,8,6]], [[1,2,3],[4,5,6],[7,8,0]]) is not None |
| 69 | True |
| 70 | """ |
| 71 | initial = PuzzleState(initial_board, goal_board) |
| 72 | frontier = PriorityQueue() |
| 73 | frontier.put(initial) |
| 74 | explored: Set[Tuple[Tuple[int, ...], ...]] = set() |
| 75 | |
| 76 | while not frontier.empty(): |
| 77 | current = frontier.get() |
| 78 | if current.is_goal(): |
| 79 | return current |
| 80 | explored.add(tuple(map(tuple, current.board))) |
| 81 | for neighbor in current.neighbors(): |
| 82 | if tuple(map(tuple, neighbor.board)) not in explored: |
| 83 | frontier.put(neighbor) |
| 84 | return None |
| 85 | |
| 86 | |
| 87 | def print_solution(solution: Optional[PuzzleState]) -> None: |
nothing calls this directly
no test coverage detected