1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
import heapq
from typing import List, Optional, Tuple
class PuzzleBoardAStar:
def __init__(self, board: List[List[Optional[int]]], moves: int = 0, parent_state: str = ""):
self.board = board
self.moves = moves
self.parent_state = parent_state
self.heuristic = self._calculate_manhattan_distance()
self.empty_row, self.empty_col = self._find_empty()
def _find_empty(self) -> Tuple[int, int]:
for i in range(3):
for j in range(3):
if self.board[i][j] is None:
return i, j
return -1, -1
def _calculate_manhattan_distance(self) -> int:
distance = 0
goal_positions = {
1: (0, 0), 2: (0, 1), 3: (0, 2),
4: (1, 0), 5: (1, 1), 6: (1, 2),
7: (2, 0), 8: (2, 1)
}
for i in range(3):
for j in range(3):
if self.board[i][j] is not None and self.board[i][j] != 0:
target_row, target_col = goal_positions[self.board[i][j]]
distance += abs(i - target_row) + abs(j - target_col)
return distance
def __str__(self) -> str:
return ','.join(str(self.board[i][j]) for i in range(3) for j in range(3))
def __lt__(self, other):
return (self.moves + self.heuristic) < (other.moves + other.heuristic)
def get_neighbors(self) -> List['PuzzleBoardAStar']:
neighbors = []
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
new_row = self.empty_row + dr
new_col = self.empty_col + dc
if 0 <= new_row < 3 and 0 <= new_col < 3:
new_board = [row[:] for row in self.board]
new_board[self.empty_row][self.empty_col] = new_board[new_row][new_col]
new_board[new_row][new_col] = None
neighbors.append(PuzzleBoardAStar(new_board, self.moves + 1, str(self)))
return neighbors
def is_goal(self) -> bool:
goal = [[1, 2, 3], [4, 5, 6], [7, 8, None]]
return self.board == goal
class Solution:
def solve_8_puzzle_astar(self, initial: List[List[Optional[int]]]) -> List[List[List[Optional[int]]]]:
start = PuzzleBoardAStar(initial)
heap = [start]
visited = {str(start)}
parent = {str(start): ""}
while heap:
current = heapq.heappop(heap)
if current.is_goal():
return self._reconstruct_path(str(current), parent)
for neighbor in current.get_neighbors():
neighbor_str = str(neighbor)
if neighbor_str not in visited:
visited.add(neighbor_str)
parent[neighbor_str] = current.parent_state if current.parent_state else str(start)
heapq.heappush(heap, neighbor)
return [] # No solution found
def _reconstruct_path(self, goal_state: str, parent: dict) -> List[List[List[Optional[int]]]]:
path = []
current = goal_state
while current != "":
path.append(self._string_to_board(current))
current = parent[current]
path.reverse()
return path
def _string_to_board(self, board_str: str) -> List[List[Optional[int]]]:
parts = board_str.split(',')
board = []
for i in range(3):
row = []
for j in range(3):
idx = i * 3 + j
if idx < len(parts):
val = parts[idx]
row.append(None if val == 'None' else int(val))
else:
row.append(None)
board.append(row)
return board
|