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 if you haven't played before.

Sliding Puzzle (LC.773)

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

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

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.

Code

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*

• Algorithms - Slider puzzle assignment

• CMPUT 396 – Sliding Tile Puzzle

• StackExchange - How to check if a 8-puzzle is solvable?

• Red Blob Games - Implementation of A*