Sliding Puzzle
Asked at Airbnb
Problem
Sliding Puzzle gives you a 2x3 board with tiles 1-5 and one empty slot (0), and asks for the fewest moves to reach [[1,2,3],[4,5,0]], where a move swaps 0 with an adjacent tile. It is a shortest-path problem over board states, solved with BFS.
Asked At
| Company | Difficulty | |
|---|---|---|
| Airbnb | Hard | View all Airbnb questions → |
How to Think About It
Think of each board configuration as a node in a graph and each legal swap as an edge. The fewest moves is the shortest path — BFS on an unweighted graph.
The state space is small: at most 6! = 720 boards, so BFS explores everything quickly.
Encode a board as a string like "412503" so it can go in a visited set. Precompute, for each index of the empty slot in the flattened 2x3 board, which indices it can swap with.
Neighbors by index: 0: [1,3], 1: [0,2,4], 2: [1,5], 3: [0,4], 4: [1,3,5], 5: [2,4].
If BFS finishes without reaching "123450", the board is unsolvable — return -1. (Half of all permutations are unreachable because of parity.)
Optimal Approach
Step 1: Flatten the board into a string start; target = "123450".
Step 2: BFS from start with steps = 0 and a visited set.
Step 3: For each state: if it equals target, return steps. Otherwise find the index of 0 and, for each neighbor index, swap to create a new state; enqueue it if unseen.
Step 4: If the queue empties, return -1.
Time: O(6! * 6). Space: O(6!).
What Trips People Up in Real Interviews
Using DFS. It finds a path but not the shortest one, and without a depth bound it can wander through the whole state space.
Storing boards as nested lists in the visited set — lists are not hashable. Serialize to a string or tuple.
Hard-coding neighbor math wrong at row boundaries (index 2 is not adjacent to index 3). Precompute the neighbor list.
Forgetting the unsolvable case and looping forever or returning 0.
Solution Code
from collections import deque
def slidingPuzzle(board):
start = ''.join(str(x) for row in board for x in row)
target = '123450'
nbrs = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
q = deque([(start, 0)])
seen = {start}
while q:
state, steps = q.popleft()
if state == target:
return steps
z = state.index('0')
for j in nbrs[z]:
s = list(state)
s[z], s[j] = s[j], s[z]
nxt = ''.join(s)
if nxt not in seen:
seen.add(nxt)
q.append((nxt, steps + 1))
return -1Frequently Asked Questions
What is the Sliding Puzzle problem?
Sliding Puzzle gives you a 2x3 board with tiles 1-5 and one empty slot (0), and asks for the fewest moves to reach `[[1,2,3],[4,5,0]]`, where a move swaps 0 with an adjacent tile. It is a shortest-path problem over board states, solved with BFS.
How do you solve Sliding Puzzle?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Sliding Puzzle?
Sliding Puzzle is asked at Airbnb. It is a hard difficulty problem.
What are common mistakes on Sliding Puzzle?
- Using DFS. It finds a path but not the shortest one, and without a depth bound it can wander through the whole state space.
- Storing boards as nested lists in the visited set — lists are not hashable. Serialize to a string or tuple.
- Hard-coding neighbor math wrong at row boundaries (index 2 is not adjacent to index 3). Precompute the neighbor list.
- Forgetting the unsolvable case and looping forever or returning 0.