Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!rochester!cornell!houpt
From: houpt@svax.cs.cornell.edu (Charles E. Houpt)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Message-ID: <46717@cornell.UUCP>
Date: 5 Oct 90 06:12:13 GMT
References: <1491@meaddata.meaddata.com> <20930@well.sf.ca.us>
Sender: nobody@cornell.UUCP
Reply-To: houpt@svax.cs.cornell.edu (Charles E. Houpt)
Distribution: comp
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 66


   One method commonly used by humans to solve the 8 puzzle (and the 15
puzzle) is the Round-About or Merry-Go-Round method. This method has
two phases. In the first you find and extend the longest sequence of tiles
around the outer ring of squares. You do this by "parking" a tile in
the center square and circulating the other tiles around until there
is a gap to insert the parked tile into the sequence.

   Once you have all the tiles in the correct order (but not necessarily
the correct positions), you start the second phase. In the second phase
you park one tile and rotate the other tiles into their correct position.

   This method can be extended to the 15 puzzle by using two rings, an
inner 4 square ring and an outer 12 square ring. Both rings use the
other to "park" tiles.

   Despite the fact that this is a common method among humans, there are
very few AI programs that solve the 8-puzzle this way, and there are
none that can learn the Merry-Go-Round method.

   I find this method interesting because it solves the problem of
conflicting subgoals by modifying the goals. So, instead of trying to
get the tiles into their correct position all at once, you
first get them into a correct sequence, and only then do you
move them into their correct positions.

Michie describes this method in:

Michie, D. "Strategy-Building with the Graph Traverser" in Machine
Intelligence 1, N. L. Collins and D. Michie (eds), American Elsevier, NY
1967 pg135-152.

-Chuck Houpt

P.S. Here an complete example:

6 2 3    Notice the sequence 2-3-4-5
1 0 4    So you first park 1 in the center and insert
7 8 5    it before the 2.

RULLDDRU

6 1 2
7 0 3    Now park the 7 and insert it after the 5.
8 5 4

RDLLUURD

1 2 3    Now every tile except the 6 is in the correct order.
6 0 4    So park 6 and rotate 8 and 7 to their final position.
8 7 5

RULD

1 2 3    Solved!
8 0 4
7 6 5

In this case the second phase was short (just moving 8 and 7), but
this is not always the case. For example:

7 8 0
6 4 1
5 3 2

Requires a lot of rotation: UURRDDLLUURRDDLLUR.