Represents a state in 8-puzzle solving with A* algorithm.
| 3 | |
| 4 | |
| 5 | class PuzzleState: |
| 6 | """Represents a state in 8-puzzle solving with A* algorithm.""" |
| 7 | |
| 8 | def __init__( |
| 9 | self, |
| 10 | board: List[List[int]], |
| 11 | goal: List[List[int]], |
| 12 | moves: int = 0, |
| 13 | previous: Optional["PuzzleState"] = None, |
| 14 | ) -> None: |
| 15 | self.board = board # Current 3x3 board configuration |
| 16 | self.goal = goal # Target 3x3 configuration |
| 17 | self.moves = moves # Number of moves taken to reach here |
| 18 | self.previous = previous # Previous state in solution path |
| 19 | |
| 20 | def __lt__(self, other: "PuzzleState") -> bool: |
| 21 | """For PriorityQueue ordering: compare priorities.""" |
| 22 | return self.priority() < other.priority() |
| 23 | |
| 24 | def priority(self) -> int: |
| 25 | """A* priority: moves + Manhattan distance.""" |
| 26 | return self.moves + self.manhattan() |
| 27 | |
| 28 | def manhattan(self) -> int: |
| 29 | """Calculate Manhattan distance using actual goal positions.""" |
| 30 | distance = 0 |
| 31 | # Create a lookup table for goal tile positions |
| 32 | goal_pos = {self.goal[i][j]: (i, j) for i in range(3) for j in range(3)} |
| 33 | |
| 34 | for i in range(3): |
| 35 | for j in range(3): |
| 36 | value = self.board[i][j] |
| 37 | if value != 0: # skip the empty tile |
| 38 | x, y = goal_pos[value] |
| 39 | distance += abs(x - i) + abs(y - j) |
| 40 | return distance |
| 41 | |
| 42 | |
| 43 | def is_goal(self) -> bool: |
| 44 | """Check if current state matches goal.""" |
| 45 | return self.board == self.goal |
| 46 | |
| 47 | def neighbors(self) -> List["PuzzleState"]: |
| 48 | """Generate all valid neighboring states by moving empty tile (0).""" |
| 49 | neighbors = [] |
| 50 | x, y = next((i, j) for i in range(3) for j in range(3) if self.board[i][j] == 0) |
| 51 | for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: |
| 52 | nx, ny = x + dx, y + dy |
| 53 | if 0 <= nx < 3 and 0 <= ny < 3: |
| 54 | new_board = [row[:] for row in self.board] |
| 55 | new_board[x][y], new_board[nx][ny] = new_board[nx][ny], new_board[x][y] |
| 56 | neighbors.append( |
| 57 | PuzzleState(new_board, self.goal, self.moves + 1, self) |
| 58 | ) |
| 59 | return neighbors |
| 60 | |
| 61 | |
| 62 | def solve_puzzle( |
no outgoing calls
no test coverage detected