Sliding Puzzle — Hard Problem & Solution

A 2 × 3 board holds the tiles 1 … 5 and one empty square written as 0. A move swaps the 0 with a tile directly above, below, left or right of it.

Difficulty: Hard
Topics: Arrays, Matrix, Breadth-First Search
Asked at: Amazon, Google, Apple
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A 2 × 3 board holds the tiles 1 … 5 and one empty square written as 0. A move swaps the 0 with a tile directly above, below, left or right of it.

The board is solved when it reads [[1,2,3],[4,5,0]]. Return the least number of moves that solves it, or -1 if it cannot be solved.

Example 1

Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the `0` with the `5`.

Example 2

Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: This arrangement cannot be reached from the solved one.

Example 3

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

Constraints

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

How to solve Sliding Puzzle

Treat each arrangement as a node and each legal swap as a unit edge, then breadth-first search from the given board to the solved one.

Approach

Flatten the board to six digits and encode it as a single integer in base 6.
Use a fixed adjacency table for the six positions of a 2 × 3 grid.
BFS: locate the 0, swap it with each neighbouring position, and enqueue unvisited results.
Return the distance on reaching the solved encoding, or -1 when the queue empties.

Why it works

Exactly half of the 720 arrangements are reachable from the solved board — sliding puzzles preserve permutation parity — which is why -1 is a genuine outcome rather than a missed search. BFS explores the reachable half in full, so an empty queue is a proof of unsolvability, not a timeout.

Complexity

Time — O(6! · 6)
Space — O(6^6) for the flat visited table

Pitfalls

The goal is [[1,2,3],[4,5,0]], with the blank last — not [[0,1,2],[3,4,5]].
Base-6 encoding wastes a little space (6^6 slots for 720 states) but makes the visited table a plain array.
An already-solved board answers 0.

Reference solution

Python

from typing import List
from collections import deque

NBRS = ((1, 3), (0, 2, 4), (1, 5), (0, 4), (1, 3, 5), (2, 4))

def slidingPuzzle(board: List[List[int]]) -> int:
    start = tuple(board[0] + board[1])
    goal = (1, 2, 3, 4, 5, 0)
    if start == goal:
        return 0
    seen = {start: 0}
    q = deque([start])
    while q:
        cur = q.popleft()
        z = cur.index(0)
        for j in NBRS[z]:
            nxt = list(cur)
            nxt[z], nxt[j] = nxt[j], 0
            nxt = tuple(nxt)
            if nxt in seen:
                continue
            seen[nxt] = seen[cur] + 1
            if nxt == goal:
                return seen[nxt]
            q.append(nxt)
    return -1

JavaScript

var slidingPuzzle = function(board) {
    var NBRS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
    var enc = function(a) {
        var v = 0;
        for (var i = 0; i < 6; i++) v = v * 6 + a[i];
        return v;
    };
    var dec = function(v) {
        var a = [0, 0, 0, 0, 0, 0];
        for (var i = 5; i >= 0; i--) { a[i] = v % 6; v = Math.floor(v / 6); }
        return a;
    };
    var start = enc([board[0][0], board[0][1], board[0][2], board[1][0], board[1][1], board[1][2]]);
    var goal = enc([1, 2, 3, 4, 5, 0]);
    if (start === goal) return 0;
    var dist = [];
    for (var i = 0; i < 46656; i++) dist.push(-1);
    dist[start] = 0;
    var q = [start];
    var head = 0;
    while (head < q.length) {
        var cur = q[head++];
        var a = dec(cur);
        var z = 0;
        for (i = 0; i < 6; i++) if (a[i] === 0) z = i;
        for (var k = 0; k < NBRS[z].length; k++) {
            var j = NBRS[z][k];
            var b = a.slice();
            b[z] = b[j];
            b[j] = 0;
            var nv = enc(b);
            if (dist[nv] >= 0) continue;
            dist[nv] = dist[cur] + 1;
            if (nv === goal) return dist[nv];
            q.push(nv);
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue