LeetCode · #773

Sliding Puzzle Solution

Find the minimum number of moves to transform a 2 × 3 board into [[1,2,3],[4,5,0]]. Each board arrangement is a graph node, so this is a textbook state-space BFS problem.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #773

🏗️

Pattern

Graph — BFS on states

The empty cell 0 can swap with any adjacent tile. That means each valid board configuration leads to a few neighboring configurations. We want the minimum number of swaps, which is exactly the shortest path in an unweighted state graph.

Example

 Input: board = [[1,2,3],[4,0,5]]
Output: 1 // swap 0 with 5 → [[1,2,3],[4,5,0]] 

Constraints

 • board.length == 2 • board[0].length == 3 • board contains the numbers 0..5 exactly once 

Section Two · Brute Force

DFS Search with Backtracking — Explosive

A brute-force attempt would recursively try every legal move, backtrack, and track the minimum move count that reaches the solved board.

Why it works

If you explore every reachable state, the smallest number of moves that reaches the goal is the correct answer.

Problem: Many paths revisit the same board state through different move orders. Without BFS plus a visited set, you waste time rediscovering the same positions, and DFS still does not naturally guarantee the minimum number of moves first.

Java — recursive search sketch

 class Solution {
private int best = Integer.MAX_VALUE;
public int slidingPuzzle(int[][] board) {
String start = encode(board);
dfs(start, 0, new java.util.HashSet<>());
return best == Integer.MAX_VALUE ? -1 : best;
    }
private void dfs(String state, int moves, java.util.Set<String> seen) {
if (moves >= best || seen.contains(state)) return;
if (state.equals("123450")) { best = moves; return; }
        seen.add(state);
// try each state reachable by swapping 0 with an adjacent tile...
seen.remove(state);
    }
}

Python — recursive search sketch

 class Solution:
def slidingPuzzle(self, board: list[list[int]]) -> int:
        start = ''.join(str(num) for row in board for num in row)
        best = [float('inf')]
def dfs(state: str, moves: int, seen: set[str]) -> None:
if moves >= best[0] or state in seen:
return if state == "123450":
                best[0] = moves
return
seen.add(state)
# try all neighbor states here...
seen.remove(state)
dfs(start, 0, set())
return -1 if best[0] == float('inf') else best[0]

Section Three · Optimal

State-Space BFS — Shortest Moves First

Flatten the board into a 6-character string like "123405". The index of 0 tells us which swaps are legal. For a 2×3 board, these moves are fixed, so we can precompute the neighbor indices. Then BFS over states until we reach "123450".

💡 Mental model: Think of each board arrangement as a room in a maze. A legal tile swap opens a door to another room. BFS explores all rooms 1 move away, then 2 moves away, then 3 moves away — so the first time we find the target room, we used the fewest moves.

Algorithm

Encode the board as a string.
Use a fixed neighbor map for the 0 position:
0→[1,3], 1→[0,2,4], 2→[1,5], 3→[0,4], 4→[1,3,5], 5→[2,4].
Queue the start state with 0 moves.
For each state, swap 0 with each allowed neighbor to generate next states.
Use a visited set so each board state is processed once.

🎯 Recognition pattern: When the problem space consists of configurations — boards, strings, locks, robot positions, masks — and you need the minimum moves between them, model each configuration as a node and use BFS.

Section Four · Walkthrough

Visual Walkthrough

Each swap of 0 generates neighboring states

Section Five · Code

Code — Java & Python

Java — BFS on encoded board states

 import java.util.*;
class Solution {
private static final int[][] NEIGHBORS = {
        {1, 3},
        {0, 2, 4},
        {1, 5},
        {0, 4},
        {1, 3, 5},
        {2, 4}
    };
public int slidingPuzzle(int[][] board) {
StringBuilder sb = new StringBuilder();
for (int[] row : board)
for (int value : row)
                sb.append(value);
String start = sb.toString();
String target = "123450";
if (start.equals(target)) return 0;
Queue<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
int moves = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
String state = queue.poll();
if (state.equals(target)) return moves;
int zeroIndex = state.indexOf('0');
for (int nextIndex : NEIGHBORS[zeroIndex]) {
String next = swap(state, zeroIndex, nextIndex);
if (visited.add(next))
                        queue.offer(next);
                }
            }
            moves++;
        }
return -1;
    }
private String swap(String s, int i, int j) {
char[] chars = s.toCharArray();
char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
return new String(chars);
    }
}

Python — BFS on encoded board states

 from collections import deque
class Solution:
def slidingPuzzle(self, board: list[list[int]]) -> int:
        start = ''.join(str(value) for row in board for value in row)
        target = "123450"
neighbors = {
0: (1, 3),
1: (0, 2, 4),
2: (1, 5),
3: (0, 4),
4: (1, 3, 5),
5: (2, 4)
        }

        queue = deque([(start, 0)])
        visited = {start}
while queue:
            state, moves = queue.popleft()
if state == target:
return moves

            zero_index = state.index('0')
for next_index in neighbors[zero_index]:
                chars = list(state)
                chars[zero_index], chars[next_index] = chars[next_index], chars[zero_index]
                next_state = ''.join(chars)
if next_state not in visited:
                    visited.add(next_state)
                    queue.append((next_state, moves + 1))
return -1 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursive search	Exponential	Exponential / recursion-heavy	Revisits states and does not prioritize shorter solutions.
State-space BFS ← optimal	O(V + E) over reachable states	O(V)	Processes each board configuration once and finds the minimum moves first.

Small but powerful fact:

The 2×3 puzzle has only 6! = 720 possible arrangements, and only half are reachable from any given parity class.
That makes BFS very practical here.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Already solved board	Return `0`	No moves are needed.
Unsolvable board	Return `-1`	BFS will exhaust all reachable states.
Visited set omitted	Huge duplicate exploration	The same state can be reached by many move sequences.
Neighbor map wrong	Missing or illegal moves	The correctness depends on generating exactly the valid swaps of the empty tile.
Counting moves per state instead of level	Off-by-one answers	BFS levels correspond to move counts.

⚠ Common Mistake: Building neighbors dynamically with row/column arithmetic each time is fine, but many bugs come from mixing up the flattened index layout. For a 2×3 board, a fixed neighbor table is simpler, faster, and less error-prone.

← Back to BFS problems

LearningTree

LC 773 · Sliding Puzzle — Solution & Explanation | DSA Guide