the 8 puzzle

[The_Ash]

Hi guys!a math question:
i've spent lots of hours trying to figure it out,so if it seems easy,i'm just dumb not lazy^^
anyhow:
i'm reading the artificial intelligence book by russel and norvig,where the 8 puzzle is described as the usual 3*3 board with 8 numbered tiles and an empty cell...
the authors claim that only 9!/2 states can be reached from a given initial state(wich means there are only 2 equivalence classes).well intuitively it seems
correct,but i can't figure out any satisfying proof.i know i just could use a few lines of code to calculate this,but the authors mentioned that so casually
that it seems like it's the result of a very simple deduction...so what am i missing?
by the way i posted that on mathoverflow,they closed it in less than 5 minutes.

[nuntius]

My memory is that there was a simple symmetry that explained the equivalence classes. I'm wanting to think about this even less than you do...

I took a quick look at an abstract algebra book that I remember having some related problems. The 15 puzzle (4x4 board) is equivalent to A15 (the alternating group of 15 elements). Searching for "alternating group" with A7 or A15 should find some interesting literature (hopefully not hidden in too much abstraction).

[gugamilare]

It's not about a simetry, it's about the possible states that you can reach. There are 9! possible states, but half of those states are not reachable.

Wikipedia explains this.

[The_Ash]

thanks a lot guys.i hadn't noticed the proof sketch on wikipedia.It needed more creativity than i thought(i'm talking about the definition of the parity function).
Anyhow,i still think it's a bit odd that the authors of the book easily mention that without any allusion to any proof,while they tend to prove a lot of trivial things that most often are direct results of some definition.