Sliding Puzzle
You are given a 2x3 board with tiles 1 through 5 and one empty cell marked 0. A move slides the empty cell up, down, left, or right, swapping it with an adjacent tile. Return the minimum number of moves needed to reach the solved board [[1,2,3],[4,5,0]], or -1 if it is unsolvable. Treat each full board arrangement as a node , and each single slide as an edge to a neighboring board. Then breadth-first search from the starting board finds the fewest slides needed, because it explores boards one slide away before any two slides away.
Constraints
- board.length == 2
- boardi.length == 3
- 0 ≤ boardi[j] ≤ 5
- Each value 0-5 appears exactly once in board
Example
board = [[1, 2, 3], [4, 0, 5]]1Explanation Sliding the empty cell right, swapping it with 5, produces the solved board [[1,2,3],[4,5,0]].
In plain terms
- Node
- One item in the graph being searched — here, one full arrangement of the board.
One cell per board arrangement BFS touches — the start, then its three one-slide neighbors
Start the queue with the given board (as "123405"), 0 moves so far.
What happens in this step
start = "123405" target = "123450"
queue = [("123405", 0)] visited = {"123405"}
start !== target, so BFS begins searching for the solved arrangement.Steps to visualize
- The row has four slots: the starting arrangement, then the three arrangements one slide away from it. A slot shows — until that arrangement has been generated.
- Each arrangement is written as the six board values read left to right, top to bottom.
- Flatten the board into a 6-character string and check whether it already matches the solved state.
- Start a queue with the starting arrangement, 0 moves so far.
- Dequeue a board; find the empty cell's position and try swapping it with each of its 2 or 3 neighbors.
- The instant a swap produces the solved arrangement, return moves + 1.
- Otherwise enqueue each new, unseen arrangement at moves + 1; if the queue empties first, return -1.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Start the queue with the given board (as "123405"), 0 moves so far.
What happens in this step
start = "123405" target = "123450"
queue = [("123405", 0)] visited = {"123405"}
start !== target, so BFS begins searching for the solved arrangement.Solution
function slidingPuzzle(board) {
const start = board[0].concat(board[1]).join('');
const target = '123450';
if (start === target) return 0;
const neighborsOf = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4],
4: [1, 3, 5],
5: [2, 4],
};
const queue = [[start, 0]];
const visited = new Set([start]);
while (queue.length > 0) {
const [state, moves] = queue.shift();
const zeroIndex = state.indexOf('0');
for (const next of neighborsOf[zeroIndex]) {
const chars = state.split('');
const temp = chars[zeroIndex];
chars[zeroIndex] = chars[next];
chars[next] = temp;
const candidate = chars.join('');
if (candidate === target) return moves + 1;
if (!visited.has(candidate)) {
visited.add(candidate);
queue.push([candidate, moves + 1]);
}
}
}
return -1;
}- Time
- O(6! * 6)
- Space
- O(6!)
Test cases
| Input | Expected | Covers |
|---|---|---|
board = [[1, 2, 3], [4, 0, 5]] | 1 | example from the docstring |
board = [[1, 2, 3], [4, 5, 0]] | 0 | the board starts already solved |
board = [[1, 2, 3], [5, 4, 0]] | -1 | a parity-locked arrangement that can never reach the solved board |
board = [[1, 0, 3], [4, 2, 5]] | 2 | a board that needs two slides, not one |
board = [[1, 2, 0], [4, 5, 3]] | 1 | a different single slide away from solved |
board = [[1, 0, 2], [4, 5, 3]] | 2 | a second two-slide arrangement reached via a different path |