Solve a Two-by-Three Sliding Puzzle
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Solve a Two-by-Three Sliding Puzzle
You are given a `2 x 3` board containing the integers `0` through `5` exactly once. The value `0` is the empty square. In one move, swap `0` with a horizontally or vertically adjacent value.
Return the minimum number of moves needed to reach the target board `[[1, 2, 3], [4, 5, 0]]`, or `-1` if the target is unreachable.
### Function Signature
```python
def sliding_puzzle(board: list[list[int]]) -> int:
```
### Examples
```text
Input: [[1, 2, 3], [4, 0, 5]]
Output: 1
Input: [[1, 2, 3], [5, 4, 0]]
Output: -1
```
### Constraints
- `board` has exactly two rows and three columns.
- Every integer from `0` through `5` appears exactly once.
- Only swaps involving `0` and an orthogonally adjacent cell are legal.
### Clarifications
- The input board need not be modified.
- Return `0` when the board is already in the target arrangement.
### Hints
- Treat each complete arrangement as a state in an unweighted graph.
- Choose a compact, hashable state representation and avoid revisiting states.
Quick Answer: Find the minimum moves needed to solve a 2-by-3 sliding puzzle, or report that the target is unreachable. Model each arrangement as a compact graph state, generate legal swaps involving the blank, and use breadth-first search without revisiting configurations.
Return the minimum adjacent-zero swaps needed to transform a 2-by-3 permutation of 0 through 5 into [[1,2,3],[4,5,0]], or -1 if no sequence can reach the target.
Constraints
- The board has exactly two rows and three columns.
- Each integer from 0 through 5 occurs exactly once.
- Only orthogonally adjacent values may swap with zero.
Examples
Input: {'board':[[1,2,3],[4,0,5]]}
Expected Output: 1
Explanation: One horizontal swap reaches the target.
Input: {'board':[[1,2,3],[5,4,0]]}
Expected Output: -1
Explanation: This permutation has the wrong parity.
Hints
- Encode a board as a six-character tuple or string.
- Breadth-first search finds shortest paths in the unweighted state graph.