the 8 puzzle

Whatever is on your mind, whether Lisp related or not.

the 8 puzzle

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

Re: the 8 puzzle

Postby 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).
User avatar
nuntius
 
Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: the 8 puzzle

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

Re: the 8 puzzle

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


Return to The Lounge

Who is online

Users browsing this forum: Google [Bot] and 2 guests