8-puzzle problem: The puzzle consists of an area divided into a grid, 3 by 3. On each grid square is a tile, except for one square which remains empty. A tile that is next to the empty grid square can be moved into the empty space, leaving its previous position empty in turn.

Given any initial state of the puzzle, there are exactly $9!/2$ reachable states. How do I prove this? And how should I generalized the proof to $(n^2-1)$-puzzle problem derived using $n$ by $n$ grid?

  • $\begingroup$ So the 8 tiles are all different, right? Please make that clear. $\endgroup$ – Yuval Filmus Jul 26 '19 at 5:41
  • $\begingroup$ For the upper bound, the parity of the permutation never changes. $\endgroup$ – Yuval Filmus Jul 26 '19 at 5:41
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because this is a pure math question which belongs to Mathematics. $\endgroup$ – Yuval Filmus Jul 26 '19 at 5:41
  • 1
    $\begingroup$ Solved here: cs.stackexchange.com/questions/16515/… $\endgroup$ – Yuval Filmus Jul 26 '19 at 7:08

Browse other questions tagged or ask your own question.