pacai.eightpuzzle.problem

 1"""
 2This file provides to the logic to work with 8 Puzzle problems.
 38 Puzzle is a smaller variant of the [15 Puzzle game](https://en.wikipedia.org/wiki/15_puzzle).
 4"""
 5
 6import pacai.core.search
 7import pacai.eightpuzzle.board
 8
 9class EightPuzzleNode(pacai.core.search.SearchNode):
10    """
11    The search node for an 8 Puzzle problem,
12    which is just the puzzle's board.
13    """
14
15    def __init__(self, board: pacai.eightpuzzle.board.EightPuzzleBoard) -> None:
16        self.board = board
17
18    def __eq__(self, other: object) -> bool:
19        if (not isinstance(other, EightPuzzleNode)):
20            return False
21
22        return self.board == other.board
23
24    def __hash__(self) -> int:
25        return hash(self.board)
26
27    def __lt__(self, other: object) -> bool:
28        if (not isinstance(other, EightPuzzleNode)):
29            raise TypeError(f"Puzzles must be of the same type, found '{type(self)}' and '{type(other)}'.")
30
31        return self.board < other.board
32
33class EightPuzzleSearchProblem(pacai.core.search.SearchProblem):
34    """
35    A search problem for finding an 8 Puzzle solution.
36    """
37
38    def __init__(self, board: pacai.eightpuzzle.board.EightPuzzleBoard):
39        super().__init__()
40
41        self.board = board
42        """ The starting board for this problem. """
43
44    def get_starting_node(self) -> EightPuzzleNode:
45        return EightPuzzleNode(self.board)
46
47    def is_goal_node(self, node: EightPuzzleNode) -> bool:
48        return node.board.is_solved()
49
50    def get_successor_nodes(self, node: EightPuzzleNode) -> list[pacai.core.search.SuccessorInfo]:
51        successors = []
52        for action in node.board.get_legal_actions():
53            new_board = node.board.apply_action(action)
54            successors.append(pacai.core.search.SuccessorInfo(EightPuzzleNode(new_board), action, 1))
55
56        return successors