wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 8 puzzle
        
(Message started by: TenaliRaman on Aug 18^th, 2004, 8:40am)

Title: 8 puzzle
Post by TenaliRaman on Aug 18^th, 2004, 8:40am

Show that [link=http://www.permadi.com/java/puzzle8/]8-puzzle[/link] 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 :) )

Title: Re: 8 puzzle
Post by towr on Aug 18^th, 2004, 8:45am

hee, I have that book :P
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)

Title: Re: 8 puzzle
Post by Aryabhatta on Aug 19^th, 2004, 11:01am

I am sure there is a simpler proof than this.

[hide]

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.

[/hide]

Title: Re: 8 puzzle
Post by Grimbal on Aug 21^st, 2004, 3:23pm

Simpler.
-->[hide]
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.
[/hide]<--

Title: Re: 8 puzzle
Post by Disoriented on Aug 24^th, 2004, 3:47pm

So let's generalize... how many disjoint sets of positions are there for an n x n grid? ;D

Title: Re: 8 puzzle
Post by Grimbal on Aug 24^th, 2004, 3:53pm

(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?

Title: Re: 8 puzzle
Post by TenaliRaman on Aug 25^th, 2004, 4:30am

Good Job Grimbal and Aryabhatta!!
Ofcourse Grimbal's version is a variant of Aryabhatta's solution .... i did it by [hide]counting the number of inversions[/hide] 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.

Title: Re: 8 puzzle
Post by rmsgrey on Aug 25^th, 2004, 6:01am

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.

Title: Re: 8 puzzle
Post by Aryabhatta on Aug 25^th, 2004, 9:22am

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.

Title: Re: 8 puzzle
Post by rmsgrey on Aug 26^th, 2004, 5:07am

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.

Title: Re: 8 puzzle
Post by TenaliRaman on Aug 27^th, 2004, 7:50am

right!
darn that was a dumb observation i made there ..... should spend more time over a problem than just 10-15 minutes :-[