On sliding tile problems--history and math (and a question)

[Subbarao Kambhampati <rao@asu.edu>]

****Number of states in n-puzzle games:
Below are some statistics on the sizes of the state spaces, and the
time taken to solve them by brute force enumeration, under the highly
optimistic assumption that you can expand 10 million (10, 000, 000 =
10^7 nodes per second.)
                                                

8 Puzzle:              10^5              .01 seconds
15 Puzzle:              10^13            6 days
3x3 Rubik'sCube:       10^19            68,000 years   
24Puzzle:              10^25            12 billion years

As I mentioned in the class, Manhattan distance heuristic is enough to
bring 15 puzzle down to solvability. 24 puzzle however is a different
beast all together. We are only now able to start cracking 24-puzzle
problems (with pattern database heuristics).


***An interesting point to ponder: 
Here is a question for you to think. The game of chess has about 10^40
legal positions--which is much bigger than 10^25, and yet a computer
is the chess champion. How come? (Answer by adding comments on the blog).

********History of the sliding puzzles is quite interesting..

The fifteen puzzle was invented by sam loyd in the 1870s, and appeared
in the scientific literature shortly thereafter. The editor of the
journal where the paper on 15-puzzle appered said at the front of the
paper" "The 15 puzzle for the last few weeks has been prominently
before the American public, and may safely be said to have engaged
attention of nine out of ten persons of both sexes and of all ages and
conditions of the community" ---In otherwords, it was the pokemon and
hoolaa-hoop of the 1870s.

Part of the reason for the world-wide fifteen puzle craze was that
Loyd offered a $1000 cash prize to transform a particular intiial
state to a particular goal state. Johnson and Story later proved that
it wasn't possible, and that the entire statespace was divided into
even and odd permutations and that there is no way to transform one
into the other by legal moves (see below).

See
http://www.cut-the-knot.com/pythagoras/fifteen.html

Also see
http://members.tripod.com/~dogschool/permutation.html
which explains using the theory of permutations why Samuel's original
puzzle could not be solved. 

****The theory behind disconnectedness of the state-space of tile-puzzles
has got to do with "even and odd permutations". In general if you take
a state, physically lift two consecutive tiles in that state and swap
their positions, then the new state will be disconnected to the old
state. You can see that

1 2 3
4 5 6
8 0 7

can be got by

starting with

1 2 3
4 5 6
7 8 0

physically lifting and swapping 7 and 8

to get

1 2 3
4 5 6
8 7 0

and then moving the blank to the left

The swapping ensures that the goal state and the state

1 2 3
4 5 6
8 0 7 

are disconnected.



cheers
Rao

---------- 
Subbarao Kambhampati 
Professor, Department of Computer Science and Engineering
Ira A. Fulton School of Engineering 
Arizona State University
P.O. Box 878809 
Tempe, AZ 85287 - 8809  rao@asu.edu (email)
480-965-0113 (Phone)  480-965-2751 (FAX) 
WWW: http://rakaposhi.eas.asu.edu/rao.html