# LeetCode 773: Sliding Puzzle

## Problem Restatement

We are given a `2 x 3` sliding puzzle board.

The board contains the numbers `1` through `5` and one empty slot represented by `0`.

A move consists of swapping `0` with one of its 4-directionally adjacent numbers.

The goal state is:

```python
[[1, 2, 3],
 [4, 5, 0]]
```

Return the least number of moves needed to reach the goal state.

If it is impossible, return `-1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A `2 x 3` board |
| Empty slot | `0` |
| Valid move | Swap `0` with an adjacent tile |
| Output | Minimum number of moves to reach `[[1,2,3],[4,5,0]]` |
| Impossible case | Return `-1` |

Example function shape:

```python
def slidingPuzzle(board: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
board = [[1, 2, 3], [4, 0, 5]]
```

Output:

```python
1
```

The empty slot `0` is next to `5`.

Swap them:

```python
[[1, 2, 3], [4, 5, 0]]
```

So the answer is `1`.

Example 2:

```python
board = [[1, 2, 3], [5, 4, 0]]
```

Output:

```python
-1
```

This starting state cannot reach the solved state.

Example 3:

```python
board = [[4, 1, 2], [5, 0, 3]]
```

Output:

```python
5
```

One shortest sequence takes `5` moves.

## First Thought: Treat Each Board as a State

Every board arrangement is a state.

A move creates another state by swapping `0` with one adjacent tile.

So this is a graph problem:

| Graph Idea | Puzzle Meaning |
|---|---|
| Node | One board arrangement |
| Edge | One valid swap involving `0` |
| Start | Given board |
| Target | `[[1,2,3],[4,5,0]]` |

Since every move has cost `1`, we need the shortest path in an unweighted graph.

That means breadth-first search is the right tool.

## Key Insight

BFS explores states by number of moves.

It first visits all states reachable in `0` moves, then all states reachable in `1` move, then all states reachable in `2` moves, and so on.

Therefore, the first time BFS reaches the target state, we have found the minimum number of moves.

Because the board is only `2 x 3`, there are at most:

```text
6! = 720
```

possible arrangements.

So BFS is small and efficient.

## State Representation

Instead of storing the board as a nested list, convert it to a string.

For example:

```python
[[1, 2, 3], [4, 0, 5]]
```

becomes:

```python
"123405"
```

The target is:

```python
"123450"
```

This makes states easy to store in a set.

## Neighbor Positions

The string has indices:

```text
0 1 2
3 4 5
```

For each possible position of `0`, precompute the indices it can swap with:

```python
neighbors = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 5],
    3: [0, 4],
    4: [1, 3, 5],
    5: [2, 4],
}
```

For example, if `0` is at index `4`, it can move up to index `1`, left to index `3`, or right to index `5`.

## Algorithm

1. Convert the board into a string `start`.
2. Set `target = "123450"`.
3. If `start == target`, return `0`.
4. Run BFS from `start`.
5. For each state:
   1. Find the index of `0`.
   2. Swap `0` with each valid neighbor.
   3. If the new state is unseen, add it to the queue.
6. If BFS reaches `target`, return the current move count.
7. If BFS ends without reaching `target`, return `-1`.

## Correctness

Each string state represents exactly one board arrangement.

Each generated neighbor is produced by swapping `0` with one adjacent tile, so every generated edge corresponds to one legal puzzle move.

The BFS starts from the initial board and explores states level by level. All states at level `d` are exactly the states reachable in `d` moves.

When the algorithm first reaches `"123450"`, BFS guarantees that no smaller number of moves could have reached it earlier. Therefore, returning that level is correct.

If the queue becomes empty, then every reachable board state has been explored. Since the target was not found, the target is unreachable from the starting board, so returning `-1` is correct.

## Complexity

There are at most `720` board arrangements.

| Metric | Value | Why |
|---|---|---|
| Time | `O(720)` | Each possible state is processed at most once |
| Space | `O(720)` | The queue and visited set store board states |

More generally, for a board with `m` cells, the state space is `O(m!)`.

## Implementation

```python
from collections import deque

class Solution:
    def slidingPuzzle(self, board: list[list[int]]) -> int:
        start = "".join(str(value) for row in board for value in row)
        target = "123450"

        if start == target:
            return 0

        neighbors = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4],
        }

        queue = deque([start])
        visited = {start}
        moves = 0

        while queue:
            for _ in range(len(queue)):
                state = queue.popleft()

                if state == target:
                    return moves

                zero = state.index("0")

                for nxt in neighbors[zero]:
                    chars = list(state)
                    chars[zero], chars[nxt] = chars[nxt], chars[zero]
                    next_state = "".join(chars)

                    if next_state in visited:
                        continue

                    visited.add(next_state)
                    queue.append(next_state)

            moves += 1

        return -1
```

## Code Explanation

We flatten the board:

```python
start = "".join(str(value) for row in board for value in row)
```

This turns the `2 x 3` board into a six-character string.

The solved board is:

```python
target = "123450"
```

If the board is already solved:

```python
if start == target:
    return 0
```

we return immediately.

The `neighbors` map tells which positions can be swapped with `0`.

BFS starts with:

```python
queue = deque([start])
visited = {start}
moves = 0
```

For each state, find where `0` is:

```python
zero = state.index("0")
```

Then generate every legal next state by swapping characters:

```python
chars = list(state)
chars[zero], chars[nxt] = chars[nxt], chars[zero]
next_state = "".join(chars)
```

If this state was already seen, skip it.

Otherwise, add it to BFS:

```python
visited.add(next_state)
queue.append(next_state)
```

After each BFS level, increment the move count:

```python
moves += 1
```

If the search finishes without finding the target:

```python
return -1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.slidingPuzzle([[1, 2, 3], [4, 0, 5]]) == 1
    assert s.slidingPuzzle([[1, 2, 3], [5, 4, 0]]) == -1
    assert s.slidingPuzzle([[4, 1, 2], [5, 0, 3]]) == 5
    assert s.slidingPuzzle([[1, 2, 3], [4, 5, 0]]) == 0
    assert s.slidingPuzzle([[3, 2, 4], [1, 5, 0]]) == 14

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| One move away | Confirms basic BFS move count |
| Impossible state | Confirms unreachable detection |
| Multi-step example | Confirms shortest path search |
| Already solved | Returns `0` |
| Larger distance | Confirms BFS explores multiple levels |