Author |
Topic: 8 puzzle (Read 4533 times) |
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
Show that 8-puzzle states (also can be called possible configurations) are divided intp two disjoint sets, such that no state in one set can be transformed into a state in the other set by any number of moves.Devise a procedure that will tell you which class a given state is in.
(Taken from Artificial Intelligence: A Modern Approach by Stuart Russel and Peter Norvig)
(Yes this is from my text book but keep no worries since its not my homework and moreover i have solved it anyways  )
|
|
 IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: 8 puzzle
« Reply #1 on: Aug 18th, 2004, 8:45am » |
 Quote  Modify
|
hee, I have that book 
I never really read much in it though.. (I've passed most of my exams to date without reading the books that went with the course)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 8 puzzle
« Reply #2 on: Aug 19th, 2004, 11:01am » |
Quote Modify
|
I am sure there is a simpler proof than this.
Just write out the numbers reading left to right and top to bottom. What we get is a permutation of (1,2,3,4,5,6,7,8 ) (Skip the empty cell)
Now sliding the counter horizontally does nothing to the permutation. Consider the vertical slide of the counter.
Moving the number x, makes it move two spaces to the left or two spaces to right (when the grid is written out). In permutation terms, this is multiplying by an even permutation, being the product of 2 transpositions. Thus the parity of the permutation does not change during the play of the 8 puzzle. This shows that two permutations have to be same parity if they can be gotten from each other by any number of moves.
So we have that there are *at least* 2 disjoint classes. -(1)
We need to show that there are exactly 2.
I think we can show that no matter what permutation we begin with we can get the permutation to (1,2,3,4,5,6,x,y).
This will prove that there are at most 2 disjoint classes. Combining with (1) we get exactly 2 such classes.
For that consider the 3x2 puzzle. A grid with 6 cells, 2 rows and 3 columns. If we can show that for this puzzle, we can get to (1,2,3,x,y) from any permutation we should be done for the 8 puzzle by repeatedly applying the 3x2 result to sub-grids of the 8x8 puzzle.
Here is an algorithm for the 3x2 puzzle:
Say we start with
a b c
d e _
_ is the empty space.
We can easily get 1 and _ to their right spots. So let us assume a = 1.
so we have
1 b c
d e _
Now is 2 is one of b c e, we can get 2 to its right spot too.
So say d = 2.
So we have
1 b c
2 e _
Move this to (I am skipping some steps)
_ b c
1 2 e
then
b 2 c
1 _ e
b 2 _
1 e c
b _ 2
1 e c
1 b 2
e c _
Now 2 can be moved to its right spot.
Similarly 3 can be moved to its right spot.
(
by considering
2 _ x
1 y z
)
An easy identifier to tell which class a state is in is the parity of the corresponding permutation.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 8 puzzle
« Reply #3 on: Aug 21st, 2004, 3:23pm » |
Quote Modify
|
Simpler.
-->
Consider the hole to be number 9. Every position, wherever the hole is, is a permutation of the 9 digits.
Every movement switches 2 numbers. So, the parity of any position depends on the number of moves to go there. Any series of moves that results in the hole at the bottom right has an even number of moves. So, for all valid positions, the permutation of the 9 digits is even. To complete the proof, you need to see that you can easily rotate any 3 pieces.
The procedure to test the parity is to switch 1 with whatever is at 1's position, then 2, etc, until you have every piece in its place. Count the number of times you actually have to switch. (sometimes it is in place already). If the number of switches is odd, the position is impossible. If even, it is possible.
<--
|
|
IP Logged |
|
|
|
Disoriented
Newbie
Posts: 6
|
|
Re: 8 puzzle
« Reply #4 on: Aug 24th, 2004, 3:47pm » |
Quote Modify
|
So let's generalize... how many disjoint sets of positions are there for an n x n grid? 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 8 puzzle
« Reply #5 on: Aug 24th, 2004, 3:53pm » |
Quote Modify
|
(sigh) Consider the hole to be number 0. The rest of the demonstration is the same.
The only exception would be the case of a nxm grid where one of n or m is 1 and the other one is >3.
Or maybe you thought of a nxn grid always with the 8 pieces of the original puzzle?
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 8 puzzle
« Reply #6 on: Aug 25th, 2004, 4:30am » |
Quote Modify
|
Good Job Grimbal and Aryabhatta!!
Ofcourse Grimbal's version is a variant of Aryabhatta's solution .... i did it by counting the number of inversions which again is simply a variant of Aryabhatta's method.
The nxn grid becomes interesting to study tho,
if n is odd then there will be [edit]no[/edit] change in parity
but if n is even , shifting blocks vertically should change parity which would mean that for even n's we cannot have any disjoint classes but for odd n's we certainly have atleast 2 disjoint classes.
|
| « Last Edit: Aug 25th, 2004, 9:45am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 8 puzzle
« Reply #7 on: Aug 25th, 2004, 6:01am » |
Quote Modify
|
But the infamous Sam Lloyd 15 puzzle consists of a 4*4 grid arranged 1,2,3,4;5,6,7,8;9,10,11,12;13,15,14,X with a cash prize for swapping the 14 and 15...
It is possible to slide the blocks from that position to reach a position with the blank space in a corner, and the other blocks in numerical order (which is what Aryabhatta's proof comes to) but in that situation, the blank is not on the bottom row, so doesn't satisfy the original terms.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 8 puzzle
« Reply #8 on: Aug 25th, 2004, 9:22am » |
Quote Modify
|
Here is one proof of the nxn case which proves that there are at least 2 disjoint classes.
For n odd, just consider the parity of the permutation, just like the n = 3 case.
For n even, consider the parity of the permutation + the parity of the row number of the hole. In the n even case, if the permutation changes parity, so does the row number. Thus keeping the parity of the permutation + row number invariant.
I guess we can show that there are exactly two classes too.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 8 puzzle
« Reply #9 on: Aug 26th, 2004, 5:07am » |
Quote Modify
|
More simply, consider that every legal move swaps the hole with another piece, inverting the transposition parity (whether the number of swaps to get the position is odd or even) and also the hole's position parity (if you imagine the underlying grid as coloured like a chess-board, whether the hole is over a black or a white square). Therefore, if the two parities don't match, the position cannot be reached from the "home" position, so there must be at least two disjoint sets.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 8 puzzle
« Reply #10 on: Aug 27th, 2004, 7:50am » |
Quote Modify
|
right!
darn that was a dumb observation i made there ..... should spend more time over a problem than just 10-15 minutes 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print