Sliding Puzzle
Sliding Puzzle is a hard graphs problem solved with the bfs for shortest path pattern.
The best approach, optimal (bfs on string states with a neighbor table), runs in O(S · k) time and O(S · k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs over copied boards up.
Problem
You are given a 2 x 3 board holding five numbered tiles 1 to 5 and one empty cell, shown as 0. In one move you may slide a tile that is directly above, below, left or right of the empty cell into it, which is the same as swapping the 0 with one of its up to four neighbors.
The board is solved when it reads [[1, 2, 3], [4, 5, 0]]. Return the smallest number of moves needed to solve the given board, or -1 if no sequence of moves can solve it.
Examples
Example 1
- Input
board = [[1, 2, 3], [0, 4, 5]]- Output
2- Why
- Slide 4 left into the gap, then slide 5 left; the gap ends in the bottom-right corner.
Example 2
- Input
board = [[2, 1, 3], [4, 5, 0]]- Output
-1- Why
- Only tiles 1 and 2 are out of place, and a single swap of two tiles can never be produced by sliding moves.
Example 3
- Input
board = [[3, 2, 4], [1, 5, 0]]- Output
14- Why
- A breadth-first search over board layouts first reaches the solved layout after 14 moves.
Constraints
board.length == 2andboard[i].length == 3boardcontains each of the numbers0to5exactly once.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| BFS over copied boards | O(S · R · C) | O(S · R · C) |
| Optimal (BFS on string states with a neighbor table) | O(S · k) | O(S · k) |
1BFS over copied boards
O(S · R · C)Each of the S reachable layouts (at most 360 of the 720) is expanded once, and each expansion copies and serializes the R x C board several times.O(S · R · C)The queue and the visited set hold up to S boards of R x C cells.Run a breadth-first search where each state is a full 2 x 3 board. For each state, find the empty cell by scanning, try the up to four directions, build a new board for each legal slide, and use a text form of the board as the visited key.
- Start the queue with the input board at distance 0 and mark its key as seen.
- Pop a board; if its key equals the solved key, return its distance.
- Locate the 0, and for each of the four directions that stays on the grid, copy the board, swap the 0 with that neighbor and enqueue the copy if its key is new.
- If the queue empties, return -1.
class Solution {
public int slidingPuzzle(int[][] board) {
String goal = Arrays.deepToString(new int[][] { { 1, 2, 3 }, { 4, 5, 0 } });
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
Deque<int[][]> queue = new ArrayDeque<>();
Set<String> seen = new HashSet<>();
queue.add(board);
seen.add(Arrays.deepToString(board));
int moves = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
int[][] cur = queue.poll();
if (Arrays.deepToString(cur).equals(goal)) return moves;
int zr = 0, zc = 0;
for (int r = 0; r < 2; r++)
for (int c = 0; c < 3; c++)
if (cur[r][c] == 0) { zr = r; zc = c; }
for (int[] d : dirs) {
int nr = zr + d[0], nc = zc + d[1];
if (nr < 0 || nr >= 2 || nc < 0 || nc >= 3) continue;
int[][] next = new int[2][];
for (int r = 0; r < 2; r++) next[r] = cur[r].clone();
next[zr][zc] = next[nr][nc];
next[nr][nc] = 0;
if (seen.add(Arrays.deepToString(next))) queue.add(next);
}
}
moves++;
}
return -1;
}
}class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
goal = str([[1, 2, 3], [4, 5, 0]])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = deque([board])
seen = {str(board)}
moves = 0
while queue:
for _ in range(len(queue)):
cur = queue.popleft()
if str(cur) == goal:
return moves
zr = zc = 0
for r in range(2):
for c in range(3):
if cur[r][c] == 0:
zr, zc = r, c
for dr, dc in dirs:
nr, nc = zr + dr, zc + dc
if nr < 0 or nr >= 2 or nc < 0 or nc >= 3:
continue
nxt = [row[:] for row in cur]
nxt[zr][zc] = nxt[nr][nc]
nxt[nr][nc] = 0
key = str(nxt)
if key not in seen:
seen.add(key)
queue.append(nxt)
moves += 1
return -1class Solution {
string key(const vector<vector<int>>& b) {
string s;
for (auto& row : b) {
for (int x : row) s += to_string(x) + ",";
s += ";";
}
return s;
}
public:
int slidingPuzzle(vector<vector<int>>& board) {
string goal = key({{1, 2, 3}, {4, 5, 0}});
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<vector<vector<int>>> q;
unordered_set<string> seen;
q.push(board);
seen.insert(key(board));
int moves = 0;
while (!q.empty()) {
for (int size = q.size(); size > 0; size--) {
vector<vector<int>> cur = q.front();
q.pop();
if (key(cur) == goal) return moves;
int zr = 0, zc = 0;
for (int r = 0; r < 2; r++)
for (int c = 0; c < 3; c++)
if (cur[r][c] == 0) { zr = r; zc = c; }
for (auto& d : dirs) {
int nr = zr + d[0], nc = zc + d[1];
if (nr < 0 || nr >= 2 || nc < 0 || nc >= 3) continue;
vector<vector<int>> next = cur;
next[zr][zc] = next[nr][nc];
next[nr][nc] = 0;
if (seen.insert(key(next)).second) q.push(next);
}
}
moves++;
}
return -1;
}
};function slidingPuzzle(board) {
const goal = JSON.stringify([[1, 2, 3], [4, 5, 0]]);
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let queue = [board];
const seen = new Set([JSON.stringify(board)]);
let moves = 0;
while (queue.length > 0) {
const next = [];
for (const cur of queue) {
if (JSON.stringify(cur) === goal) return moves;
let zr = 0, zc = 0;
for (let r = 0; r < 2; r++)
for (let c = 0; c < 3; c++)
if (cur[r][c] === 0) { zr = r; zc = c; }
for (const [dr, dc] of dirs) {
const nr = zr + dr, nc = zc + dc;
if (nr < 0 || nr >= 2 || nc < 0 || nc >= 3) continue;
const copy = cur.map((row) => row.slice());
copy[zr][zc] = copy[nr][nc];
copy[nr][nc] = 0;
const k = JSON.stringify(copy);
if (!seen.has(k)) {
seen.add(k);
next.push(copy);
}
}
}
queue = next;
moves++;
}
return -1;
}2Optimal (BFS on string states with a neighbor table)
O(S · k)Each of the S = 6!/2 = 360 reachable strings is processed once, with at most 3 swaps of a k = 6 character string.O(S · k)The queue and the seen set store up to S strings of length k.Flatten the board into a 6-character string, reading row by row. In that string, index i is cell (i / 3, i % 3), so the cells next to each index never change and can be written down once. A breadth-first search from the start string then only swaps characters, and the first time it pops the goal string the level count is the answer.
- Precompute
adj = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]]: the indices next to each index. - Build the start string from the board; enqueue it with distance 0 and add it to
seen. - Process the queue level by level. For each string, return the level if it equals
"123450". - Otherwise find the '0', and for each
jinadj[zero]swap the two characters; enqueue the result if it is new. - If the queue runs out, return -1.
class Solution {
public int slidingPuzzle(int[][] board) {
int[][] adj = { { 1, 3 }, { 0, 2, 4 }, { 1, 5 }, { 0, 4 }, { 1, 3, 5 }, { 2, 4 } };
StringBuilder sb = new StringBuilder();
for (int[] row : board)
for (int x : row) sb.append(x);
String start = sb.toString(), goal = "123450";
Deque<String> queue = new ArrayDeque<>();
Set<String> seen = new HashSet<>();
queue.add(start);
seen.add(start);
int moves = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
String cur = queue.poll();
if (cur.equals(goal)) return moves;
int zero = cur.indexOf('0');
for (int j : adj[zero]) {
char[] chars = cur.toCharArray();
chars[zero] = chars[j];
chars[j] = '0';
String next = new String(chars);
if (seen.add(next)) queue.add(next);
}
}
moves++;
}
return -1;
}
}class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
adj = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
start = "".join(str(x) for row in board for x in row)
goal = "123450"
queue = deque([start])
seen = {start}
moves = 0
while queue:
for _ in range(len(queue)):
cur = queue.popleft()
if cur == goal:
return moves
zero = cur.index("0")
for j in adj[zero]:
chars = list(cur)
chars[zero], chars[j] = chars[j], "0"
nxt = "".join(chars)
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
moves += 1
return -1class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
vector<vector<int>> adj = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
string start;
for (auto& row : board)
for (int x : row) start += char('0' + x);
string goal = "123450";
queue<string> q;
unordered_set<string> seen;
q.push(start);
seen.insert(start);
int moves = 0;
while (!q.empty()) {
for (int size = q.size(); size > 0; size--) {
string cur = q.front();
q.pop();
if (cur == goal) return moves;
int zero = cur.find('0');
for (int j : adj[zero]) {
string next = cur;
next[zero] = next[j];
next[j] = '0';
if (seen.insert(next).second) q.push(next);
}
}
moves++;
}
return -1;
}
};function slidingPuzzle(board) {
const adj = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
const start = board.flat().join("");
const goal = "123450";
let queue = [start];
const seen = new Set([start]);
let moves = 0;
while (queue.length > 0) {
const next = [];
for (const cur of queue) {
if (cur === goal) return moves;
const zero = cur.indexOf("0");
for (const j of adj[zero]) {
const chars = cur.split("");
chars[zero] = chars[j];
chars[j] = "0";
const s = chars.join("");
if (!seen.has(s)) {
seen.add(s);
next.push(s);
}
}
}
queue = next;
moves++;
}
return -1;
}Edge cases to test
- The board is already solved (answer 0)
- Unsolvable layouts, which are exactly half of all 720 layouts
- The farthest solvable layouts, which need 21 moves
Hints
Hint 1
Treat every arrangement of the six cells as a node in a graph; one move connects two arrangements. The question asks for a shortest path.
Hint 2
There are only 6! = 720 arrangements, so a breadth-first search with a visited set is cheap. If the search ends without reaching the goal, the answer is -1.
Hint 3
Encode a board as a 6-character string and precompute, for each position of the 0, which positions it can swap with.
FAQ
What is the best time complexity for Sliding Puzzle?
Optimal (BFS on string states with a neighbor table) runs in O(S · k) time and O(S · k) extra space. Each of the S = 6!/2 = 360 reachable strings is processed once, with at most 3 swaps of a k = 6 character string.
Which pattern does Sliding Puzzle use?
It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.
Is there a brute force solution for Sliding Puzzle?
Yes. BFS over copied boards takes O(S · R · C) time and O(S · R · C) space. Run a breadth-first search where each state is a full 2 x 3 board.
Which edge cases should I test for Sliding Puzzle?
The board is already solved (answer 0); Unsolvable layouts, which are exactly half of all 720 layouts; The farthest solvable layouts, which need 21 moves.