pacai.eightpuzzle.board

  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 random
  7
  8import pacai.core.action
  9import pacai.core.board
 10
 11DIM: int = 3
 12""" The length of one dimension/size of the puzzle. """
 13
 14LENGTH: int = DIM * DIM
 15""" The total number of numbers in the puzzle. """
 16
 17SOLVED_NUMBERS: list[int] = list(range(LENGTH))
 18""" The sequence of numbers that represents a solved puzzle. """
 19
 20BLANK_NUMBER: int = 0
 21""" The number used to represent the blank space. """
 22
 23class EightPuzzleBoard:
 24    """
 25    An instance of an 8 Puzzle board.
 26
 27    8 Puzzle (a smaller variant of 15 Puzzle) is a type of sliding puzzle
 28    where the numbers 1-8 are arranged on square tiles on a square grid with one blank space
 29    (sometimes represented with a 0).
 30    The goal of the puzzle is to slide the tiles so that the empty space
 31    is in the top left and all other tiles are in increasing order.
 32    A solved puzzles looks like:
 33    ```
 34        -------------
 35        |   | 1 | 2 |
 36        -------------
 37        | 3 | 4 | 5 |
 38        -------------
 39        | 6 | 7 | 8 |
 40        -------------
 41    ```
 42
 43    An interesting note about 8 Puzzle is that every configuration of the board is both
 44    a valid puzzle and a valid starting location
 45    (image a game of chess where any configuration of the board is a valid starting position).
 46
 47    In the real world, you move tiles into the blank space on the puzzle.
 48    In this representation, we will instead "slide" the blank space in one of the four cardinal directions.
 49    This makes our representation of moves easier, since we don't have to keep track of which tile is being moved
 50    (it is always the blank tile/space).
 51    """
 52
 53    def __init__(self, numbers: list[int]) -> None:
 54        if (len(numbers) != LENGTH):
 55            raise ValueError(f"Incorrect number of puzzle inputs. Required: {LENGTH}, Found: {len(numbers)}.")
 56
 57        for (i, value) in enumerate(numbers):
 58            if ((value < 0) or (value >= LENGTH)):
 59                raise ValueError(f"Puzzle value at index {i} is out of bounds. Found {value}, must be in [0, {LENGTH - 1}].")
 60
 61        self._numbers = numbers.copy()
 62
 63    def is_solved(self) -> bool:
 64        """ Check if this puzzle in in the solved position. """
 65
 66        return (self._numbers == SOLVED_NUMBERS)
 67
 68    def get_legal_actions(self) -> list[pacai.core.action.Action]:
 69        """
 70        Get a list if the current legal actions.
 71
 72        Legal actions consists of cardinal directions that the blank tile can be moved to.
 73
 74        Note that these moves are the opposite of the real world where you slide another tile into the blank tile's space.
 75        """
 76
 77        actions = []
 78
 79        blank_position = self.get_blank_position()
 80
 81        for (action, offset) in pacai.core.board.CARDINAL_OFFSETS.items():
 82            new_position = blank_position.add(offset)
 83            if ((new_position.row < 0) or (new_position.row >= DIM) or (new_position.col < 0) or (new_position.col >= DIM)):
 84                continue
 85
 86            actions.append(action)
 87
 88        return actions
 89
 90    def get_blank_position(self) -> pacai.core.board.Position:
 91        """ Get the position of the blank space. """
 92
 93        index = self._numbers.index(BLANK_NUMBER)
 94        row = index // DIM
 95        col = index % DIM
 96
 97        return pacai.core.board.Position(row, col)
 98
 99    def apply_action(self, action: pacai.core.action.Action) -> 'EightPuzzleBoard':
100        """ Returns a new EightPuzzleBoard after taking the given action. """
101
102        offset = pacai.core.board.CARDINAL_OFFSETS.get(action, None)
103        if (offset is None):
104            raise ValueError(f"Illegal action: '{action}'.")
105
106        # Get the old and new positions.
107        old_blank_position = self.get_blank_position()
108        new_blank_position = old_blank_position.add(offset)
109
110        # Convert the positions to indexes.
111        old_blank_index = (old_blank_position.row * DIM) + old_blank_position.col
112        new_blank_index = (new_blank_position.row * DIM) + new_blank_position.col
113
114        # Get a copy of the numbers, and swap the old/new blank positions.
115        new_numbers = self._numbers.copy()
116        new_numbers[old_blank_index], new_numbers[new_blank_index] = new_numbers[new_blank_index], new_numbers[old_blank_index]
117
118        return EightPuzzleBoard(new_numbers)
119
120    def __eq__(self, other: object) -> bool:
121        if (not isinstance(other, EightPuzzleBoard)):
122            return False
123
124        return self._numbers == other._numbers
125
126    def __hash__(self) -> int:
127        return hash(str(self._numbers))
128
129    def __lt__(self, other: object) -> bool:
130        if (not isinstance(other, EightPuzzleBoard)):
131            raise TypeError(f"Puzzles must be of the same type, found '{type(self)}' and '{type(other)}'.")
132
133        return self._numbers < other._numbers
134
135    def __str__(self) -> str:
136        separator = '-' * (DIM * (DIM + 1) + 1)
137        lines = [separator]
138
139        for row in range(DIM):
140            line = '|'
141
142            for col in range(DIM):
143                index = (row * DIM) + col
144
145                value: str | int = self._numbers[index]
146                if (value == BLANK_NUMBER):
147                    value = ' '
148
149                line += f" {value} |"
150
151            lines.append(line)
152            lines.append(separator)
153
154        return "\n".join(lines)
155
156    def __repr__(self) -> str:
157        return str(self._numbers)
158
159def from_rng(rng: random.Random, move_count: int = 100) -> EightPuzzleBoard:
160    """
161    Create a new EightPuzzleBoard from a random seed.
162    The given number of random moves will be taken to scramble the board
163    (starting from the solved board).
164    """
165
166    puzzle = EightPuzzleBoard(SOLVED_NUMBERS)
167    for _ in range(move_count):
168        actions = puzzle.get_legal_actions()
169        action = rng.sample(actions, 1)[0]
170        puzzle = puzzle.apply_action(action)
171
172    return puzzle