How do you solve Sliding Puzzle on LeetCode?

Sliding Puzzle (LeetCode #773) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The BFS approach guarantees the shortest path due to its level-order exploration.

What is the brute force solution for Sliding Puzzle?

The brute force approach for Sliding Puzzle is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves generating all possible states of the board by swapping the empty tile (0) with its adjacent tiles. We can then check each state to see if it matches the solved configuration. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Sliding Puzzle?

Always clarify the problem statement and constraints before jumping into coding. Think about edge cases, such as already solved boards or impossible configurations. Explain your thought process as you code; it helps the interviewer understand your reasoning.

What are common mistakes when solving Sliding Puzzle?

Failing to track visited states can lead to infinite loops. Not considering all possible moves from the empty tile can miss valid configurations.

#773

Sliding Puzzle

Hard

ArrayDynamic ProgrammingBacktrackingBreadth-First SearchMemoizationMatrixBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a breadth-first search (BFS) to explore the board configurations efficiently. By treating each configuration as a node and the valid moves as edges, we can find the shortest path to the target configuration. This method leverages the properties of BFS to ensure we find the least number of moves.

⚙️

Algorithm

4 steps

1Step 1: Convert the board to a string representation and initialize a queue for BFS.
2Step 2: Track visited configurations to avoid cycles.
3Step 3: For each configuration, generate new configurations by swapping the empty tile with its adjacent tiles.
4Step 4: If a new configuration matches the target, return the number of moves taken to reach it.

solution.py24 lines

1from collections import deque
2
3def slidingPuzzle(board):
4    target = '123450'
5    start = ''.join(str(num) for row in board for num in row)
6    queue = deque([(start, start.index('0'), 0)])
7    visited = set([start])
8    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
9    while queue:
10        state, zero_index, moves = queue.popleft()
11        if state == target:
12            return moves
13        zero_row, zero_col = divmod(zero_index, 3)
14        for dr, dc in directions:
15            new_row, new_col = zero_row + dr, zero_col + dc
16            if 0 <= new_row < 2 and 0 <= new_col < 3:
17                new_zero_index = new_row * 3 + new_col
18                new_state = list(state)
19                new_state[zero_index], new_state[new_zero_index] = new_state[new_zero_index], new_state[zero_index]
20                new_state = ''.join(new_state)
21                if new_state not in visited:
22                    visited.add(new_state)
23                    queue.append((new_state, new_zero_index, moves + 1))
24    return -1

ℹ

Complexity note: The time complexity is O(n) because we explore each configuration at most once, and there are a limited number of configurations (6!). The space complexity is O(n) due to the storage of the queue and visited states.

1The BFS approach guarantees the shortest path due to its level-order exploration.
2Understanding the board's configuration as a string simplifies the swapping logic.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.