# Sliding Puzzle ## Introduction Sliding puzzle and its variations are pretty popular among puzzle games. Typically, the game is played on a 3 x 3 board or a 4 x 4 board with one empty tile to shift. You can check it out [here](https://www.helpfulgames.com/subjects/brain-training/sliding-puzzle.html) if you haven't played before. ## Sliding Puzzle ([LC.773](https://leetcode.com/problems/sliding-puzzle/)) > Given the puzzle board `board`, return *the least number of moves required so that the state of the board is solved*. If it is impossible for the state of the board to be solved, return `-1`. ## Example ``` Input: board = [[1,2,3],[4,0,5]] Output: 1 Input: board = [[1,2,3],[5,4,0]] Output: -1 Input: board = [[4,1,2],[5,0,3]] Output: 5 ``` ## Level BFS ``` idea ``` ## Code ```python BoardState = Tuple[Tuple[int], Tuple[int]] Pos = Tuple[int, int] class Solution: DESIRED_STATE: BoardState = ((1, 2, 3), (4, 5, 0)) POS_DELTAS: List[Pos] = [(-1, 0), (1, 0), (0, -1), (0, 1)] def _is_in_bound(self, i: int, j: int) -> bool: return 0 <= i <= 1 and 0 <= j <= 2 def is_desired_state(self, board_state: BoardState) -> bool: return board_state == self.DESIRED_STATE def moves(self, board_state: BoardState) -> Iterator[BoardState]: board = [list(board_state[0]), list(board_state[1])] zero_pos = (0, 0) for i in range(len(board)): for j in range(len(board[i])): if board_state[i][j] == 0: zero_pos = (i, j) for delta in self.POS_DELTAS: new_state = copy.deepcopy(board) swap_i = zero_pos[0] + delta[0] swap_j = zero_pos[1] + delta[1] if self._is_in_bound(swap_i, swap_j): new_state[zero_pos[0]][zero_pos[1]] = new_state[swap_i][swap_j] new_state[swap_i][swap_j] = 0 yield tuple(new_state[0]), tuple(new_state[1]) def slidingPuzzle(self, board: List[List[int]]) -> int: init_state = (tuple(board[0]), tuple(board[1])) if self.is_desired_state(init_state): return 0 num_moves = 0 queue: Deque[BoardState] = deque() visited_state: Set[BoardState] = set() queue.append(init_state) visited_state.add(init_state) while len(queue) > 0: level_len = len(queue) for i in range(level_len): current_state = queue.popleft() for next_state in self.moves(current_state): if next_state in visited_state: continue if self.is_desired_state(next_state): return num_moves + 1 queue.append(next_state) visited_state.add(next_state) num_moves += 1 return -1 ``` ## Solvability Proof tbd ```python def is_solvable(self, board: List[List[int]]) -> bool: inversions = 0 flat_board = [e for row in board for e in row] for i in range(len(flat_board)): if flat_board[i] == 0: continue for j in range(i + 1, len(flat_board)): if flat_board[j] == 0: continue if flat_board[i] > flat_board[j]: inversions += 1 return inversions % 2 == 0 ``` This check improves the runtime from 228ms to 84ms. ## A\* Search We can frame this question as a shortest path finding in a weighted graph. * Shortest path - Dijkstra's algorithm * Weight * Actual cost - Number of steps * Heuristic - Manhattan distance (admissible) * Estimate the cost from the current node to the target node * Best lower bound to the actual cost A very helpful visualization can be found [here](https://qiao.github.io/PathFinding.js/visual/). ## Code ```python class Solution: DESIRED_STATE = ((1, 2, 3), (4, 5, 0)) POS_DELTAS = ( (-1, 0), (1, 0), (0, -1), (0, 1) ) DESIRED_POS = { 1: (0, 0), 2: (0, 1), 3: (0, 2), 4: (1, 0), 5: (1, 1) } def total_man_dist(self, board_state: BoardState) -> int: total_dist = 0 for i in range(len(board_state)): for j in range(len(board_state[i])): cur_tile = board_state[i][j] if cur_tile != 0: desired_pos = self.DESIRED_POS[cur_tile] man_dist = abs(desired_pos[0] - i) + abs(desired_pos[1] - j) total_dist += man_dist return total_dist def _is_in_bound(self, i: int, j: int) -> bool: return 0 <= i <= 1 and 0 <= j <= 2 def is_desired_state(self, board_state: BoardState) -> bool: return board_state == self.DESIRED_STATE def is_solvable(self, board: List[List[int]]) -> bool: inversions = 0 flat_board = [e for row in board for e in row] for i in range(len(flat_board)): if flat_board[i] == 0: continue for j in range(i + 1, len(flat_board)): if flat_board[j] == 0: continue if flat_board[i] > flat_board[j]: inversions += 1 return inversions % 2 == 0 def moves(self, board_state: BoardState) -> Iterator[BoardState]: board = [list(board_state[0]), list(board_state[1])] zero_pos = (0, 0) for i in range(len(board)): for j in range(len(board[i])): if board_state[i][j] == 0: zero_pos = (i, j) for delta in self.POS_DELTAS: new_state = copy.deepcopy(board) swap_i = zero_pos[0] + delta[0] swap_j = zero_pos[1] + delta[1] if self._is_in_bound(swap_i, swap_j): new_state[zero_pos[0]][zero_pos[1]] = new_state[swap_i][swap_j] new_state[swap_i][swap_j] = 0 yield tuple(new_state[0]), tuple(new_state[1]) def slidingPuzzle(self, board: List[List[int]]) -> int: if not self.is_solvable(board): return -1 init_state = (tuple(board[0]), tuple(board[1])) if self.is_desired_state(init_state): return 0 # [(priority, board state)] pq: List[Tuple[int, BoardState]] = [] # {board state: steps} visited_dict: Dict[BoardState, int] = dict() heapq.heappush(pq, (0, init_state)) visited_dict[init_state] = 0 while len(pq) > 0: current_state = heapq.heappop(pq)[1] for next_state in self.moves(current_state): if next_state in visited_dict: continue next_steps = visited_dict[current_state] + 1 if self.is_desired_state(next_state): return next_steps next_priority = next_steps + self.total_man_dist(next_state) heapq.heappush(pq, (next_priority, next_state)) visited_dict[next_state] = next_steps return -1 ``` This improves the runtime from 84ms to 52ms. The graph size is pretty small for this question because of the board size. The performance improvement should be more noticeable if the board size is 4 x 4 or larger. ## Analysis The search graph is a lot smaller with a\* than regular BFS. For example with this board `[[4,1,2],[5,0,3]]` ``` # regular BFS visited set: {((4, 2, 0), (5, 1, 3)), ((5, 4, 2), (1, 3, 0)), ((0, 1, 2), (4, 5, 3)), ((1, 2, 0), (4, 5, 3)), ((4, 1, 2), (5, 3, 0)), ((1, 5, 2), (0, 4, 3)), ((4, 1, 2), (0, 5, 3)), ((4, 3, 1), (5, 0, 2)), ((1, 5, 2), (4, 0, 3)), ((4, 2, 3), (5, 0, 1)), ((0, 4, 1), (5, 3, 2)), ((1, 0, 2), (4, 5, 3)), ((4, 0, 1), (5, 3, 2)), ((0, 4, 2), (5, 1, 3)), ((5, 4, 2), (1, 0, 3)), ((4, 2, 3), (5, 1, 0)), ((4, 0, 2), (5, 1, 3)), ((4, 1, 2), (5, 0, 3)), ((4, 0, 3), (5, 2, 1)), ((1, 5, 2), (4, 3, 0)), ((5, 4, 2), (0, 1, 3)), ((4, 1, 0), (5, 3, 2)), ((4, 2, 3), (0, 5, 1)), ((5, 0, 2), (1, 4, 3))} # a* search visited dict: {((4, 1, 2), (5, 0, 3)): 0, ((4, 0, 2), (5, 1, 3)): 1, ((4, 1, 2), (0, 5, 3)): 1, ((4, 1, 2), (5, 3, 0)): 1, ((0, 1, 2), (4, 5, 3)): 2, ((1, 0, 2), (4, 5, 3)): 3, ((1, 5, 2), (4, 0, 3)): 4, ((1, 2, 0), (4, 5, 3)): 4} ``` O(whole graph) to O(1 / 4 of the graph?) ## Reading * Medium - [Solving Search Problem with Iterative Deepening A\* ](https://gsurma.medium.com/sliding-puzzle-solving-search-problem-with-iterative-deepening-a-d7e8c14eba04) * Algorithms - [Slider puzzle assignment ](https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/specification.php) * CMPUT 396 – [Sliding Tile Puzzle](http://webdocs.cs.ualberta.ca/~hayward/396/hoven/4stile.pdf?fbclid=IwAR0f_CyleC6gKK33g-AAa98CBd_o_zYOWo7We5FRd0yGDXsufdA2TddZWA4) * StackExchange - [How to check if a 8-puzzle is solvable? ](https://math.stackexchange.com/questions/293527/how-to-check-if-a-8-puzzle-is-solvable) * Red Blob Games - [Implementation of A\*](https://www.redblobgames.com/pathfinding/a-star/implementation.html#python) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://zedive.gitbook.io/project-l/part-2/graph-search/graph-theory/graph-traversal/sliding-puzzle.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.