> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/graph-search/graph-theory/graph-traversal/sliding-puzzle.md). # 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)