the 8 puzzle

Whatever is on your mind, whether Lisp related or not.
Post Reply
The_Ash
Posts: 6
Joined: Sun Mar 04, 2012 10:21 am

the 8 puzzle

Post by The_Ash » Wed Mar 07, 2012 11:13 am

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
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: the 8 puzzle

Post by nuntius » Wed Mar 07, 2012 4:40 pm

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
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: the 8 puzzle

Post by gugamilare » Wed Mar 07, 2012 6:57 pm

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
Posts: 6
Joined: Sun Mar 04, 2012 10:21 am

Re: the 8 puzzle

Post by The_Ash » Thu Mar 08, 2012 1:25 pm

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.

Post Reply