Reachable states of the 8-puzzle
The 8-puzzle is a frame holding tiles 1-8 and one empty cell; a move slides a tile adjacent to the empty cell into it. Starting from the solved position, how many different arrangements (of the 8 tiles and the blank among the 9 cells) can be reached?
Show hints (2)+
- Treat the blank as a ninth tile. What does a single move do to the parity of the permutation?
- Combine that with the parity of the blank's position on the board.
Answer
Reveal answer →Final answer
181440
Create a free account to see the full worked solution and track your progress.
Interview format: Trading Aptitude Tests, Prop Trading