8-Puzzle
Description
The 8 Puzzle is a sliding block game played on a 3×3 grid containing 8 numbered tiles (from 1 to 8) and one empty space represented by 0. The objective is to rearrange the tiles into a specific goal configuration by sliding them one at a time.
Only tiles adjacent to the empty space (0) can be moved, and each move consists of swapping a tile with the 0.
Input Format
2D array that contains the initial state of the puzzle.
Output Format
Integer indicating the minimum possible number of moves to solve the 8-Puzzle problem.
If the puzzle configuration is unsolvable, return -1.
A grid is considered solved if it is of the following configuration:
1 2 3
4 5 6
7 8 0Sample Input
[[1,2,0],[4,5,3],[7,8,6]]Sample Output
2This is the classic 8-puzzle shortest-move problem. Each board state can be treated as a graph node, and each legal swap with the adjacent zero creates an edge, so BFS is a natural way to find the minimum number of moves to the goal state. A solvability check based on inversion parity can be used to return -1 quickly when the puzzle cannot be solved. In the sample, the board [[1,2,0],[4,5,3],[7,8,6]] reaches the target in 2 moves.
