500. Sliding Puzzle
A sliding puzzle sits on a 2×3 board: five tiles labeled 1 through 5 plus one empty square, written as 0. You are given the board as a 2×3 integer grid board.
In one move you may slide a tile that sits directly above, below, left of, or right of the empty square into it — equivalently, swap 0 with one of its 4-directional neighbors.
The puzzle is solved when the board reads [[1,2,3],[4,5,0]]. Return the minimum number of moves needed to solve the puzzle, or -1 if the solved state can never be reached.
Example 1:
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Sliding tile 5 one square to the left produces [[1,2,3],[4,5,0]], the solved board, so one move suffices.
Example 2:
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: Tiles 4 and 5 are swapped relative to the solved board. No sequence of slides can fix that parity, so the puzzle is unsolvable.
Example 3:
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: One optimal line takes 5 slides: 5 right, 4 down, 1 left, 2 left, 3 up — passing through [[4,1,2],[0,5,3]], [[0,1,2],[4,5,3]], [[1,0,2],[4,5,3]], [[1,2,0],[4,5,3]] and ending at [[1,2,3],[4,5,0]]. No shorter sequence exists.
Constraints:
- board.length == 2 and board[r].length == 3
- 0 ≤ board[r][c] ≤ 5
- Every value from 0 to 5 appears exactly once.
Hints:
Stop thinking about tiles and think about **whole board layouts**. Each layout is a node in a graph; each legal slide is an edge to another layout. There are only 6! = 720 layouts, so the graph is tiny.
"Minimum number of moves" on an unweighted graph is a breadth-first search. Flatten the board to a 6-character string like "123405" so layouts can go in a hash set, and precompute which flat indices are adjacent on the 2×3 board.
If BFS exhausts every reachable layout without meeting "123450", the start is in the unsolvable half of the permutations — return -1.
To go further, run A* with the Manhattan-distance heuristic: order the frontier by moves-so-far plus how far every tile still is from home. It reaches the goal after expanding far fewer states.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: board = [[1,2,3],[4,0,5]]
Expected output: 1