HardArrayDynamic ProgrammingBacktrackingBreadth-First SearchMemoizationMatrixUpdated Sep 2026

773. Sliding Puzzle

Asked at Airbnb

Difficulty

Hard

Time

O(6! * 6)

Space

O(6!)

Pattern

Array

Companies

1

Problem

You are given a 2 x 3 board holding the tiles 1 through 5 and one empty square written as 0. In one move you pick the empty square and swap it with a tile that shares an edge with it (up, down, left or right).

The board is solved when it looks exactly like [[1,2,3],[4,5,0]]. Return the smallest number of moves needed to reach that state. If no sequence of moves can ever solve the board, return -1.

Each board layout is a state, and each legal swap is an edge between two states. So this is a shortest-path problem on a graph where every edge costs 1 move — a plain BFS finds the answer. The total number of layouts is only 6! = 720, so exploring all of them is cheap.

One swap of 0 with a neighbor

board012011234050 is at (1,1); the tile 5 at (1,2) is adjacent, sothey can swap.after 1 move01201123450After the swap the board matches the goal, so theanswer is 1.
The empty square 0 can swap with any tile touching it, and the goal is the layout with 0 in the bottom-right corner.

Constraints

  • ●board.length == 2
  • ●board[i].length == 3
  • ●0 <= board[i][j] <= 5
  • ●Each value board[i][j] is unique

Examples

Example 1
Inputboard = [[1,2,3],[4,0,5]]
Output1
WhyThe 0 sits next to the 5, so swapping them gives [[1,2,3],[4,5,0]] in a single move.
Example 2
Inputboard = [[1,2,3],[5,4,0]]
Output-1
WhyTiles 4 and 5 are swapped relative to the goal. That flip cannot be fixed by sliding, so no number of moves works.
Example 3
Inputboard = [[4,1,2],[5,0,3]]
Output5
WhyThe shortest path takes 5 swaps: move 0 left, then left again, then right, then right, then right, ending at [[1,2,3],[4,5,0]].

Asked At

1 companies
CompanyDifficulty
AirbnbHardView all Airbnb questions →

How to Think About It

1

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.

2

The state space is small: at most 6! = 720 boards, so BFS explores everything quickly.

3

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.

4

Neighbors by index: 0: [1,3], 1: [0,2,4], 2: [1,5], 3: [0,4], 4: [1,3,5], 5: [2,4].

5

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!).

BFS over board states

flatten board to stringpush start, steps = 0pop state, check goalswap 0 with each neighborenqueue unseen statesBFS visits states in order of move count, so the firsttime we see the goal we have the minimum.state string412503012345The start board [[4,1,2],[5,0,3]] becomes "412503";index 4 holds the 0.neighbors of index 4: 1, 3, 5swap 0 with a neighbor to get next stategoal string = "123450"
Encode each board as a 6-character string, then expand states level by level until the goal string appears.
ComplexityTime O(6! * 6)Space O(6!)There are at most 720 states, and each state tries at most 4 swaps, so the work is bounded by the tiny state space.

What Trips People Up in Real Interviews

1

Using DFS. It finds a path but not the shortest one, and without a depth bound it can wander through the whole state space.

2

Storing boards as nested lists in the visited set — lists are not hashable. Serialize to a string or tuple.

3

Hard-coding neighbor math wrong at row boundaries (index 2 is not adjacent to index 3). Precompute the neighbor list.

4

Forgetting the unsolvable case and looping forever or returning 0.

Solution Code

O(6! * 6) time
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 -1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(6! * 6) time and O(6!) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.