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.
- Difficulty: Hard
- Topics: Arrays, Matrix, Breadth-First Search
- Asked at: Amazon, Google, Apple, Airbnb
- 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 == 2board[i].length == 30 <= board[i][j] <= 5Each value of board is unique.
Hints for Sliding Puzzle
Hint 1
There are only
6! = 720arrangements, so the entire state space can be searched.Hint 2
Encode a board as a short sequence of six digits and breadth-first search over those states.
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
- 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
-1when 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 -1Java
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