Skip to content
Get started

Reachable states of the 8-puzzle

The 8-puzzle is a 3×33\times 3 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)+
  1. Treat the blank as a ninth tile. What does a single move do to the parity of the permutation?
  2. Combine that with the parity of the blank's position on the board.

Answer

Reveal answer →

181440

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Prop Trading

Related questions