The 8-puzzle is a 3×3 board of tiles 1–8 plus a blank (0). A move slides a neighbouring tile into the blank. What's the minimum number of moves to reach:
1 2 3
4 5 6
7 8 0
Treat each board as a state and each move as an edge. The shortest path in an unweighted graph is found by BFS. Encode boards as strings like "123456780" so you can store visited states in a set.
There are only 9!/2 = 181,440 reachable states, so plain BFS is fast. Half of all boards are unsolvable, and BFS proves it by running out of states. For extra credit, check the inversion count: an odd count means the board can't be solved.