Sliding Puzzle

Hard
941.

Sliding Puzzle

Sliding Puzzle is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Apple and Airbnb interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} board
 * @return {number}
 */
var slidingPuzzle = function(board) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sliding Puzzle — Solution in Python, Java & C++

Sliding Puzzle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Sliding Puzzle is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Apple and Airbnb interviews.

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.

Hints for Sliding Puzzle

  1. Hint 1

    There are only 6! = 720 arrangements, so the entire state space can be searched.

  2. Hint 2

    Encode a board as a short sequence of six digits and breadth-first search over those states.

  3. Hint 3

    Precompute which squares each position can swap with — the board never changes shape.

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

  1. Flatten the board to six digits and encode it as a single integer in base 6.
  2. Use a fixed adjacency table for the six positions of a 2 × 3 grid.
  3. BFS: locate the 0, swap it with each neighbouring position, and enqueue unvisited results.
  4. 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

Java

public static int slidingPuzzle(int[][] board) {
    int[][] nbrs = { {1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4} };
    int start = 0;
    for (int i = 0; i < 6; i++) start = start * 6 + board[i / 3][i % 3];
    int goal = 0;
    int[] g = { 1, 2, 3, 4, 5, 0 };
    for (int i = 0; i < 6; i++) goal = goal * 6 + g[i];
    if (start == goal) return 0;
    int[] dist = new int[46656];
    Arrays.fill(dist, -1);
    dist[start] = 0;
    int[] q = new int[46656];
    int head = 0, tail = 0;
    q[tail++] = start;
    while (head < tail) {
        int cur = q[head++];
        int[] a = new int[6];
        int tmp = cur;
        for (int i = 5; i >= 0; i--) { a[i] = tmp % 6; tmp /= 6; }
        int z = 0;
        for (int i = 0; i < 6; i++) if (a[i] == 0) z = i;
        for (int j : nbrs[z]) {
            int[] b = a.clone();
            b[z] = b[j];
            b[j] = 0;
            int nv = 0;
            for (int i = 0; i < 6; i++) nv = nv * 6 + b[i];
            if (dist[nv] >= 0) continue;
            dist[nv] = dist[cur] + 1;
            if (nv == goal) return dist[nv];
            q[tail++] = nv;
        }
    }
    return -1;
}

C++

int slidingPuzzle(vector<vector<int>>& board) {
    vector<vector<int>> nbrs = { {1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4} };
    int start = 0;
    for (int i = 0; i < 6; i++) start = start * 6 + board[i / 3][i % 3];
    int g[6] = { 1, 2, 3, 4, 5, 0 };
    int goal = 0;
    for (int i = 0; i < 6; i++) goal = goal * 6 + g[i];
    if (start == goal) return 0;
    vector<int> dist(46656, -1), q;
    dist[start] = 0;
    q.push_back(start);
    for (size_t head = 0; head < q.size(); head++) {
        int cur = q[head];
        int a[6], tmp = cur;
        for (int i = 5; i >= 0; i--) { a[i] = tmp % 6; tmp /= 6; }
        int z = 0;
        for (int i = 0; i < 6; i++) if (a[i] == 0) z = i;
        for (int j : nbrs[z]) {
            int b[6];
            for (int i = 0; i < 6; i++) b[i] = a[i];
            b[z] = b[j];
            b[j] = 0;
            int nv = 0;
            for (int i = 0; i < 6; i++) nv = nv * 6 + b[i];
            if (dist[nv] >= 0) continue;
            dist[nv] = dist[cur] + 1;
            if (nv == goal) return dist[nv];
            q.push_back(nv);
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal