On the disconnectedness of the 8-puzzle search space (or Learninglessons the hard way)+History of sliding tile puz

[Subbarao Kambhampati <rao@asu.edu>]

Although it looks simple, the 8-puzzle is quite tricky. The
most
difficult puzzle requires 18 moves to solve. The 8-puzzle graph also
has the nasty property that its graph has two *disconnected parts* each
with 181440 nodes. 

If the start position is no one half, and the goal in the other half,
the puzzle has no solution.

Now, you think you can spot such a property quite easily... turns out
that it is not that easy to tell if two random positions are in the
same connected graph. 

Here is what happened (true (TM) story) to one hapless student last year 

He used what he thought was a simple initial state to check his
code. The init state he used is

1 2 3
4 5 6
8 0 7

(and the goal state is the usual

1 2 3
4 5 6 
7 8 0
)

Turns out that these two states are in two different components and
the problem is unsolvable. Since he is using A* search without any
checks to avoid repeated nodes, what this meant basically is that he
will do search until all the cows come home without ever exhausting
the space. 

Note that the very similar looking state

1 2 3 
4 5 6
7 0 8

is trivially solvable... [[**See below for how you could figure this
out**]]

The student of course assumed that this is a problem with his code. He
came for help during my office hours. After spending a futile 1 hour
to check his code for errors, I finally decided to look at the actual
supposedly simple init state he was using. At that point we checked
the code against all the init state I provided in the class and his
code works flawlessly. 

I tried to explain to him that he should consider himself lucky to
have stumbled on a reasonably deep truth about puzzle problems, but he
didn't seem to appreciate the merit of hard-earned lessons ;-)

Anyways, this has an implication for generating random tile puzzle
instances--you 
can't just randomly generate init and goal state since they can be in two 
different components. The normal way to generate random instances of
8-puzzle problems _starts_ with goal-state and generates problems by
starting with goal-state and making some sequence of moves from goal
state to generate an initial state (this way we know they are in the
same connected component!)

The following "footnotes" point out that this poor student is
not
exactly alone in getting stuck with disconnected states... the very
first challenge problem in 15-puzzle, 100 years back, turned out to be
an unsolvable one (and indirectly lead to the invention of theory of
permutation groups).


Rao

Footnote 1: [[ The theory behind disconnectedness 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.]]


Footnote 2:

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
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. 

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's
Cube:       10^19            
68,000 years   
24
Puzzle:              10^25            
12 billion years

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? ;-)