Problem 37.7 · Advanced Graph AlgorithmsHard

Sliding Puzzle

PatternGraph BFS Dijkstra's Shortest Path

What it teaches: Search over board states: BFS, or A* with a Manhattan-distance heuristic.

Practise it on judges as “Sliding Puzzle”.

In plain words

Every arrangement of the board is a "place", and one slide moves you to a neighbouring place. The fewest slides is a shortest path. A* explores places in order of moves so far plus a guess of moves left (how far each tile is from its home), so it heads straight for the goal.

Return the fewest moves to reach [[1,2,3],[4,5,0]], or −1. Example: [[4,1,2],[5,0,3]] → 5.

The problem

A 2 × 3 board holds tiles 1–5 and an empty square 0. A move swaps 0 with an adjacent tile. Return the fewest moves to reach [[1,2,3],[4,5,0]], or −1.

Example 1

Input: board = [[4,1,2],[5,0,3]]
Output: 5

Constraints

2 × 3 board

Pattern clues in the wording

→ Fewest moves between puzzle states

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public int slidingPuzzle(int[][] board) {
        return -1;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	board = [[1,2,3],[4,0,5]]	1
2	board = [[1,2,3],[5,4,0]]	-1
3	board = [[4,1,2],[5,0,3]]	5

From slow to fast

Approaches

1. BFS over states · O(6! × 3)2. A* with Manhattan distance · Fewer states expanded on solvable boards

BFS over states

Time O(6! × 3) Space O(6!)

Level-order BFS from the start string; neighbours swap '0' with adjacent indices.

Approach 1

import java.util.*;

class Solution {
    private static final int[][] NEXT = {{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 x : row) sb.append(x);
        String start = sb.toString(), target = "123450";
        Set<String> seen = new HashSet<>(List.of(start));
        Deque<String> q = new ArrayDeque<>(List.of(start));
        for (int moves = 0; !q.isEmpty(); moves++) {
            for (int size = q.size(); size > 0; size--) {
                String s = q.poll();
                if (s.equals(target)) return moves;
                int z = s.indexOf('0');
                for (int j : NEXT[z]) {
                    char[] c = s.toCharArray();
                    c[z] = c[j];
                    c[j] = '0';
                    String t = new String(c);
                    if (seen.add(t)) q.offer(t);
                }
            }
        }
        return -1;
    }
}

Verdict: Only 720 states.

A* with Manhattan distance

Time Fewer states expanded on solvable boards Space O(6!)

Priority = moves so far + sum of tile distances to their goal cells. The heuristic never overestimates, so the first time the target is popped its cost is optimal.

▶ Dry run: A*: moves so far (g) + guess left (h)board = [[4,1,2],[5,0,3]]

score(vars)

g: 0h: 5f: 5

Step 1/6Start. h adds up how far each tile is from home (4, 1, 2 and 3 are one step off each, 5 is one step off): h = 5.

Approach 2

import java.util.*;

class Solution {
    private static final int[][] NEXT = {{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 x : row) sb.append(x);
        String start = sb.toString(), target = "123450";
        Map<String, Integer> best = new HashMap<>();
        best.put(start, 0);
        PriorityQueue<Object[]> pq = new PriorityQueue<>((a, b) -> Integer.compare((int) a[0], (int) b[0]));
        pq.offer(new Object[]{h(start), 0, start});
        while (!pq.isEmpty()) {
            Object[] top = pq.poll();
            int g = (int) top[1];
            String s = (String) top[2];
            if (g > best.get(s)) continue;
            if (s.equals(target)) return g;
            int z = s.indexOf('0');
            for (int j : NEXT[z]) {
                char[] c = s.toCharArray();
                c[z] = c[j];
                c[j] = '0';
                String t = new String(c);
                if (g + 1 < best.getOrDefault(t, Integer.MAX_VALUE)) {
                    best.put(t, g + 1);
                    pq.offer(new Object[]{g + 1 + h(t), g + 1, t});
                }
            }
        }
        return -1;
    }

    private int h(String s) {
        int d = 0;
        for (int i = 0; i < 6; i++) {
            int tile = s.charAt(i) - '0';
            if (tile == 0) continue;
            int goal = tile - 1;
            d += Math.abs(i / 3 - goal / 3) + Math.abs(i % 3 - goal % 3);
        }
        return d;
    }
}

Verdict: Scales to bigger puzzles where BFS can't.

Before you submit

Edge cases and common mistakes

Test these inputs

Already solved (0)
Unsolvable parity (−1)

Mistakes people make

Rebuilding the neighbour list from row/column math each time (fine but error-prone; a table is clearer).

Interview

Follow-up questions

How can you tell a board is unsolvable without searching?

Command Palette