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