>From: gerhard@vmars.tuwien.ac.at (Gerhard Fohler)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 2 Oct 90 14:18:48 GMT
gordon@meaddata.com (Gordon Edwards) writes:
>I would like references on the 15-puzzle and various approaches to solving it.
>I know Pohl used it when performing his bi-directional and heuristic search
>work.
A well-known algorithm capable of solving the 15-puzzle on existing machines is depth-first iterative deepening by Richard Korf(1). As a summary of algorithms
for search problems I would recommend Korf (2), which briefly addresses future
directions for research on search also.
At our department we use a modified version of this algorithm for finding
schedules for distributed hard real-time systems, a NP hard problem. Our
experiences so far are quite promissing.
Gerhard Fohler
--------------
(1) Korf, R.E., 1985: Depth-first iterative deepening: An optimal
admissible tree search, Artificial Intelligence. 27(1):97-109
(2) Korf, R.E., 1988: Search: A Survey of Recent Results, in: Shrobe, H.E.:
Exploring Artificial Intelligence, Survey Talks from the National
Conferences on Artificial Intelligence, Morgan Kaufmann Publishers, Inc.,
San Mateo, California
-------------------------------------------------------------------------
>From: pmm@acsu.buffalo.edu (patrick m mullhaupt)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 2 Oct 90 18:14:52 GMT
In article <1491@meaddata.meaddata.com> meaddata!gordon@uunet.uu.net writes:
>I would like references on the 15-puzzle and various approaches to solving it.
>
>Thanks,
>-- Gordon (gordon@meaddata.com)
A good reference for information on the 8-puzzle, (little brother of
the 15-puzzle), is:
Problem Solving in Artificial Intelligence,
by Nils Nilsson (1971)
I'm citing this from memory, so it may not be exactly correct, but
it's correct enough so that you can look it up. To find other
information on the 15-puzzle, it might help to look under 8-puzzle,
since I believe the 8-puzzle is the more common variant.
Hope this helps,
Patrick Mullhaupt
-------------------------------------------------------------------------
>From: nagle@well.sf.ca.us (John Nagle)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 4 Oct 90 07:34:20 GMT
gordon@meaddata.com (Gordon Edwards) writes:
>I would like references on the 15-puzzle and various approaches to solving it.
One simple approach is to get the top row and left column in order by
suitable manipulation. Having done this, which is easy, you have reduced the
4x4 15-puzzle to the 3x3 8-puzzle. Repetition of this process reduces the
8-puzzle to the 2x2 3-puzzle. A final repetition solves the puzzle.
Who needs AI?
John Nagle
-------------------------------------------------------------------------
>From: lindsay@comp.vuw.ac.nz (Lindsay Groves)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 5 Oct 90 01:02:38 GMT
Organization: Computer Science Dept, Victoria University, Wellington, NEW ZEALAND
In article <20930@well.sf.ca.us>, nagle@well.sf.ca.us (John Nagle) writes:
|> gordon@meaddata.com (Gordon Edwards) writes:
|>
|> >I would like references on the 15-puzzle and various approaches to
|> solving it.
|>
|> One simple approach is to get the top row and left column in
|> order by
|> suitable manipulation. Having done this, which is easy, you have
|> reduced the
|> 4x4 15-puzzle to the 3x3 8-puzzle. Repetition of this process
|> reduces the
|> 8-puzzle to the 2x2 3-puzzle. A final repetition solves the puzzle.
|> Who needs AI?
|>
|> John Nagle
I'd like to see a system that, given a description of the puzzle, could
find this way of solving the puzzle, rather than just finding *a*
solution. Then I'd think there might be something intelligent going
on!
Lindsay
-------------------------------------------------------------------------
>From: coleman@moby.cs.ucla.edu (Michael Coleman)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 5 Oct 90 03:45:36 GMT
nagle@well.sf.ca.us (John Nagle) writes:
> One simple approach is to get the top row and left column in order by
>suitable manipulation. Having done this, which is easy, you have reduced the
>4x4 15-puzzle to the 3x3 8-puzzle. Repetition of this process reduces the
>8-puzzle to the 2x2 3-puzzle. A final repetition solves the puzzle.
>Who needs AI?
It is not clear (to me) from inspection that this will necessarily always
work. Is it always the case that after you set up the top row and left
column, you can reach the final configuration without changing them? It may
be true for 4x4, but I don't think it is true for the 3x3 puzzle.
(In the terminology, I think I am asking whether or not this is a serializable
subgoal.)
--Mike
-------------------------------------------------------------------------
>From: houpt@svax.cs.cornell.edu (Charles E. Houpt)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 5 Oct 90 06:12:13 GMT
Organization: Cornell Univ. CS Dept, Ithaca NY
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.
-------------------------------------------------------------------------
>From: druby@ics.uci.edu (David Ruby)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 5 Oct 90 17:35:44 GMT
Organization: UC Irvine Department of ICS
>In article <20930@well.sf.ca.us>, nagle@well.sf.ca.us (John Nagle) writes:
>|> gordon@meaddata.com (Gordon Edwards) writes:
>|>
>|> >I would like references on the 15-puzzle and various approaches to
>|> solving it.
>|>
>|> One simple approach is to get the top row and left column in
>|> order by
>|> suitable manipulation. Having done this, which is easy, you have
>|> reduced the
>|> 4x4 15-puzzle to the 3x3 8-puzzle. Repetition of this process
>|> reduces the
>|> 8-puzzle to the 2x2 3-puzzle. A final repetition solves the puzzle.
>|> Who needs AI?
>|>
>|> John Nagle
>I'd like to see a system that, given a description of the puzzle, could
>find this way of solving the puzzle, rather than just finding *a*
>solution. Then I'd think there might be something intelligent going
>on!
>Lindsay
SteppingStone, a learning problem solver, does solve the tile sliding puzzle is
a manner very similar to this. It begins by ordering the subgoals (tiles to be
placed) using a general heuristic called openness. The effect of this
ordering is to set up the tiles along the upper row and left hand column to
be solved first, reducing the problem difficulty as mentioned. A means-ends
analysis like approach is then used to try and place the tiles without undoing
them once solved. With the orderings produced using the openness heuristic,
there is only one tile along the upper row and one tile along the left
hand column that can't be solved in this manner.
When a tile cannot be solved under this assumption, the system searches
through its knowledge to see if it has an approach for solving this type of
subproblem. Knowledge is stored as a new sequence of subgoals for leading the
means-ends analysis component to a state where all of the previously solved
subgoals are still solved and the current subgoal is also solved. When the
system does not have knowledge for solving a particular subgoal it falls back
on a local search approach. After solving the subproblem, the solution is
generalized into a new sequence of subgoals for reuse on other problems.
Note, that the system only checks its knowledge when it cannot solve a subgoal
(tile) under its simplifying assumption.
Unlike previous learning problem solvers that learn control rules or
macro-operators, SteppingStone learns sequences of subgoals or stepping
stones. Here a subgoal is a partial state description. The stepping stones
are used by the means-ends analysis component to lead the system through
difficult portions of the problem. SteppingStone solved tile sliding problems
ranging in size from the 3x3 8-puzzle to the 6x6 35-puzzle. The results were
published in the article:
"Learning subgoal sequences for planning" by David Ruby and Dennis Kibler
in the proceeding of the Eleventh International Joint Conference on Artificial
Intelligence (IJCAI-89).
More recently SteppingStone has been used to learn to optimize logic synthesis
problems. The goal is now to demonstrate it on a series of benchmarks in the
logic synthesis community as well as extend it to other domains.
David Ruby
Graduate Student
University of California, Irvine
-------------------------------------------------------------------------
>From: mmh@cs.qmw.ac.uk (Matthew Huntbach)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 10 Oct 90 16:58:34 GMT
Organization: Computer Science Dept, QMW, University of London, UK.
In article <46717@cornell.UUCP> houpt@svax.cs.cornell.edu (Charles E. Houpt) writes:
>
> One method commonly used by humans to solve the 8 puzzle (and the 15
>puzzle) is the Round-About or Merry-Go-Round method.
All these methods involving macro-operators and subgoals are
not guaranteed to give the optimal solution. If you want the
least number of moves to reach the goal you must still employ the
standard search techniques.
Matthew Huntbach
-------------------------------------------------------------------------
>From: kudu@.ucalgary.ca (Gopi Kuduvalli, The Gemini)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 5 Oct 90 21:27:49 GMT
Organization: The University of Calgary
In article coleman@moby.cs.ucla.edu (Michael Coleman) writes:
>nagle@well.sf.ca.us (John Nagle) writes:
>> One simple approach is to get the top row and left column in order by
>>suitable manipulation. Having done this, which is easy, you have reduced the
>>4x4 15-puzzle to the 3x3 8-puzzle. Repetition of this process reduces the
>>8-puzzle to the 2x2 3-puzzle. A final repetition solves the puzzle.
>>Who needs AI?
>
>It is not clear (to me) from inspection that this will necessarily always
>work. Is it always the case that after you set up the top row and left
>column, you can reach the final configuration without changing them? It may
>be true for 4x4, but I don't think it is true for the 3x3 puzzle.
>
>
>--Mike
>--
The algorithm *certainly* fails at the 2x2 stage. (Cursory inspection
would show this). Since it fails for atleast one case, it is not a
*generalized* solution.
-- Gopi
Gopinath R. Kuduvalli = "In view of the stupidity of the majority
Email : kudu@enel.UCalgary.CA * of the people, a widely held opinion is
kudu@uncamyr.UCalgary.CA = more likely to be foolish than sensible."
#include * - Bert Russell in 'Marriage and morals'
-------------------------------------------------------------------------
>From: nagle@well.sf.ca.us (John Nagle)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Date: 13 Oct 90 00:56:25 GMT
kudu@.ucalgary.ca (Gopi Kuduvalli, The Gemini) writes:
> The algorithm *certainly* fails at the 2x2 stage. (Cursory inspection
>would show this). Since it fails for at least one case, it is not a
>*generalized* solution.
Only half of the possible starting states allow a solution for puzzles
of this class. If you can reach a state in an 8-puzzle of the form
1 2 3
4 5 6
8 7
it is not possible to reach the state
1 2 3
4 5 6
7 8
and it is a special case of this general principle that you are
observing when you report that the 2x2 3-puzzle is not solvable for
some conditions. A full analysis of this I leave to someone more into
mathematical recreations than I. It is probably covered in the works
of Martin Gardner.
John Nagle
-------------------------------------------------------------------------
>From: sjr87@ecs.soton.ac.uk (Simon Roberts)
Newsgroups: comp.ai
Subject: 8-puzzle heuristic needed
Date: 29 Nov 90 10:37:16 GMT
I am currently engaged in writing a PROLOG program to solve the
8-puzzle, ie get 123
456
78
from any starting configuration.
I have been using the heuristic: h = d + (3*s) to solve it but I run
into problems. Can anyone supply me with an appropriate formula to
apply to the problem, along with any relevant scoring criteria??
I would be most grateful if you could email rather than post to the
address below.
Regards,
Zak Roberts : sjr87@ecs.soton.ac.uk (+ nsfnet-relay.ac.uk)
-------------------------------------------------------------------------
>From: sjr87@ecs.southampton.ac.uk (Simon Roberts)
Newsgroups: comp.ai
Subject: 8-puzzle (repost)
Date: 30 Nov 90 20:03:06 GMT
Organization: The University of Southampton, Hampshire, UK.
Sorry for reposting this, but I'm not sure if our news software sent
it out the first time.
I am having problems with writing a PROLOG problem to solve the
8-puzzle from any starting goal to:
123
456
78
I have up to now been using the heuristic d + 3*s which is normally
used for the goal:
123
8 4
765
But this is not so good for the first case.
Can anyone push me in the right direction as how to tackle this
problem to achieve the optimal solution??
I would be most grateful.
Regards,
Simon
####################################################################
# -- Simon Roberts -- #
####################################################################
# JANET : sjr87@uk.ac.soton.ecs #
# INTERNET : sjr87@ecs.soton.ac.uk (+ nsfnet-relay.ac.uk) #
####################################################################
-------------------------------------------------------------------------
>From: eiverson@nmsu.edu (Eric Iverson)
Newsgroups: comp.ai
Subject: Solving the 8 puzzle through hill climbing
Date: 18 Aug 92 08:06:23 GMT
Organization: Computing Research Lab
Below is a brief series of steps to solve one configuration of the 8
puzzle. I am looking for a fitness function such that each successive
step would be judged to be more fit than its predecessor, thus enabling
hill climbing. I realize that hill climbing is not the best way to
solve the 8 puzzle, but that's what I want to do. (No, this isn't
homework. It's a question in Rich's textbook that I just happen to be
rereading.) Any suggestions would be appreciated.
[1,2,3]
[8,5,6]
[4,7,*]
[1,2,3]
[8,5,*]
[4,7,6]
[1,2,3]
[8,*,5]
[4,7,6]
[1,2,3]
[*,8,5]
[4,7,6]
[1,2,3]
[4,8,5]
[*,7,6]
[1,2,3]
[4,8,5]
[7,*,6]
[1,2,3]
[4,*,5]
[7,8,6]
[1,2,3]
[4,5,*]
[7,8,6]
[1,2,3]
[4,5,6]
[7,8,*]
--
------------------------------------------------------------------------
Eric Iverson Internet: eiverson@nmsu.edu
Computing Research Lab
Box 30001/3CRL Life is something to do when
New Mexico State University you can't get to sleep.
Las Cruces, NM 88003-0001 -Fran Lebowitz
VOICE: (505) 646-5711
FAX: (505) 646-6218
-------------------------------------------------------------------------
>From: babraham@unpcs1.cs.unp.ac.za (Bobby Abraham)
Newsgroups: comp.ai
Subject: 8 Puzzle (Is it connected)
Date: 7 Sep 92 07:10:34 GMT
Organization: Dept. Computer Science, UNP
I recently gave the 8 puzzle to an Intro AI class. I remember reading that
the 15 puzzle was not solvable from any position. In other words the graph
of this problem was not connected.
Can anyone tell me if the same applies to the 8 puzzle? I would be
interested in the proof as well.
Thank you
-------------------------------------------------------------------
Bobby Abraham
Dept. of Computer Science
University of Natal, Pietermaritzburg
email - babraham@unpcs1.cs.unp.ac.za
abraham@unpsun1.cc.unp.ac.za
-------------------------------------------------------------------
>From: ginsberg@t.Stanford.EDU (Matthew L. Ginsberg)
Newsgroups: comp.ai
Subject: Re: 8 Puzzle (Is it connected)
Date: 7 Sep 92 15:57:20 GMT
Organization: Computer Science Department, Stanford University
In article babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes:
>I recently gave the 8 puzzle to an Intro AI class. I remember reading that
>the 15 puzzle was not solvable from any position. In other words the graph
>of this problem was not connected.
>
>Can anyone tell me if the same applies to the 8 puzzle? I would be
>interested in the proof as well.
None of these puzzles is connected. If you consider the blank a tile,
each legal move swaps two tiles and therefore obviously retains the "parity"
of the overall position.
Matt Ginsberg
-------------------------------------------------------------------------
>From: mgv@cs.scarolina.edu (Marco Valtorta)
Newsgroups: comp.ai
Subject: Re: 8 Puzzle (Is it connected)
Date: 7 Sep 92 18:05:37 GMT
Organization: USC Department of Computer Science
ginsberg@t.Stanford.EDU (Matthew L. Ginsberg) writes:
>In article babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes:
>>I recently gave the 8 puzzle to an Intro AI class. I remember reading that
>>the 15 puzzle was not solvable from any position. In other words the graph
>>of this problem was not connected.
>>
>>Can anyone tell me if the same applies to the 8 puzzle? I would be
>>interested in the proof as well.
>None of these puzzles is connected. If you consider the blank a tile,
>each legal move swaps two tiles and therefore obviously retains the "parity"
>of the overall position.
> Matt Ginsberg
A while ago, Torben Mogensen gave the argument in more detail. (What follows
is e-mail he sent me relating to his posting, rather than his actual posting
to comp.ai.)
For the trivia enthusiast, the argument was first made by William E. Story in
Woolsey Johnson, Wm. and William E. Story.
"Notes on the "15" Puzzle."
_American Journal of Mathematics, 2 (1879), 397-404.
Marco Valtorta, Assistant Professor usenet: ...!ncrcae!usceast!mgv
Department of Computer Science internet: mgv@usceast.cs.scarolina.edu
University of South Carolina tel.: (1)(803)777-4641
Columbia, SC 29208 tlx: 805038 USC
U.S.A. fax: (1)(803)777-3767
usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv
-------------------------------------------------------------------------
Date: Thu, 10 Oct 91 11:18:02 +0100
>From: Torben AEgidius Mogensen
To: mgv@usceast.cs.scarolina.edu
Subject: Re: Re: Tiled Puzzle Problem for 2x2 or 5x5 square
>Could you please sketch the argument or give a reference to the proof
>of the result?
The argument I gave you was actually slightly incomplete: it requires
that the empty space is in the same position in the initial and final
states. Or, more precisely, that the empty space is an even number of
squares away from the initial position (the initial and final squares
would have the same colour on a chess board).
The proof goes like this:
1) A single move is an exchange between the empty space and one other
piece.
2) The empty space will, in a single move, change from a black square
to a white or vice versa.
3) Thus any sequence of moves that leaves the empty space on the same
colour will have to be even.
4) An even number of moves corresponds to an even number of exchanges
of pieces (including the empty space).
5) This can be seen from a result about permutations, stating that if
the permutation can be achieved by an even number of exchanges, no
odd number of exhanges will achieve the same permutation (and vice
versa). The permotation is said to have even or odd parity.
Thus, a solution exist if the empty space starts and ends on the same
colour and an even number of exchanges is required or the empty space
starts and ends on opposite colours and an odd number of exchanges is
required.
Torben Mogensen (torbenm@diku.dk)
-------------------------------------------------------------------------
>From: matthew@psych.psy.uq.oz.au (Matthew McDonald)
Newsgroups: comp.ai,rec.puzzles
Subject: How do I solve the 8/15... Puzzle (was (Is it connected))
Date: 8 Sep 92 04:10:03 GMT
Organization: Psychology Department, University of Queensland
Marco Valtorta writes:
> ginsberg@t.Stanford.EDU (Matthew L. Ginsberg) writes:
>
> >In article babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes:
> >>I recently gave the 8 puzzle to an Intro AI class. I remember reading that
> >>the 15 puzzle was not solvable from any position. In other words the graph
> >>of this problem was not connected.
[...]
I believe there's a very simple algorithm for these puzzles
that will reach the solution in a reasonable number of moves.
Could anybody tell me what algorithm is? (Most puzzle books
seem to only use Loyd's 15 puzzle to illustrate parity, saying that
actually solving the puzzle is trivial...)
I can see plenty of ways of doing it but none of them are
both simple and efficient for the larger versions of the puzzle.
(I do have a serious reason for wanting to know...)
I don't think this is of general interest, but I'll gladly
summarise if anyone wants.
=-=-
Matthew McDonald matthew@psych.psy.uq.oz.au
-------------------------------------------------------------------------
>From: nau@frabjous.cs.umd.edu (Dana Nau)
Newsgroups: comp.ai,rec.puzzles
Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected))
Date: 9 Sep 92 02:50:07 GMT
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
From: matthew@psych.psy.uq.oz.au (Matthew McDonald)
Newsgroups: comp.ai,rec.puzzles
Date: 8 Sep 92 04:10:03 GMT
Organization: Psychology Department, University of Queensland
I believe there's a very simple algorithm for these puzzles
that will reach the solution in a reasonable number of moves.
Could anybody tell me what algorithm is? (Most puzzle books
seem to only use Loyd's 15 puzzle to illustrate parity, saying that
actually solving the puzzle is trivial...)
I can see plenty of ways of doing it but none of them are
both simple and efficient for the larger versions of the puzzle.
(I do have a serious reason for wanting to know...)
It *is* trivial, provided that you are satisfied with a
less-than-optimal solution (i.e., one that takes more than the least
possible number of moves). When I was a kid, I could solve the
15-puzzle in a few seconds, using the following simple-minded
algorithm:
for i = 1 to n (where n is the total number of tiles)
put tile i into its proper place,
while preserving the locations of tiles 1 through i-1
The only place there's any problem is that you have to temporarily
disturb the tiles in the second-to-last row in order to get the tiles
in the last row into their proper order. But there's a simple
procedure for that, too. Try it a few times and you'll probably
figure it out.
I haven't taken the time to do a proper complexity analysis, but I
believe the total number of moves for this algorithm is no worse than
O(n^4).
--
Dana S. Nau
Computer Science Dept. Internet: nau@cs.umd.edu
University of Maryland UUCP: uunet!mimsy!nau
College Park, MD 20742 Telephone: (301) 405-2684
-------------------------------------------------------------------------
>From: mgv@cs.scarolina.edu (Marco Valtorta)
Newsgroups: comp.ai
Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected))
Date: 9 Sep 92 15:51:17 GMT
Organization: USC Department of Computer Science
nau@frabjous.cs.umd.edu (Dana Nau) writes:
> From: matthew@psych.psy.uq.oz.au (Matthew McDonald)
> Newsgroups: comp.ai,rec.puzzles
> Date: 8 Sep 92 04:10:03 GMT
> Organization: Psychology Department, University of Queensland
> I believe there's a very simple algorithm for these puzzles
> that will reach the solution in a reasonable number of moves.
> Could anybody tell me what algorithm is? (Most puzzle books
> seem to only use Loyd's 15 puzzle to illustrate parity, saying that
> actually solving the puzzle is trivial...)
>It *is* trivial, provided that you are satisfied with a
>less-than-optimal solution (i.e., one that takes more than the least
>possible number of moves). When I was a kid, I could solve the
>15-puzzle in a few seconds, using the following simple-minded
>algorithm:
> for i = 1 to n (where n is the total number of tiles)
> put tile i into its proper place,
> while preserving the locations of tiles 1 through i-1
>The only place there's any problem is that you have to temporarily
>disturb the tiles in the second-to-last row in order to get the tiles
>in the last row into their proper order. But there's a simple
>procedure for that, too. Try it a few times and you'll probably
>figure it out.
>I haven't taken the time to do a proper complexity analysis, but I
>believe the total number of moves for this algorithm is no worse than
>O(n^4).
>--
> Dana S. Nau
> Computer Science Dept. Internet: nau@cs.umd.edu
> (I do have a serious reason for wanting to know...)
> University of Maryland UUCP: uunet!mimsy!nau
> College Park, MD 20742 Telephone: (301) 405-2684
Since there is interest in this, maybe it helps to repost a recent message.
Marco Valtorta, Assistant Professor usenet: ...!ncrcae!usceast!mgv
Department of Computer Science internet: mgv@usceast.cs.scarolina.edu
University of South Carolina tel.: (1)(803)777-4641
Columbia, SC 29208 tlx: 805038 USC
U.S.A. fax: (1)(803)777-3767
usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv
>From: nagle@netcom.com (John Nagle)
Newsgroups: comp.ai
Subject: Re: generalized 15-puzzle is NP-hard (NOT!)
Date: 1 Aug 92 20:22:15 GMT
Organization: Netcom - Online Communication Services (408 241-9760 guest)
chan@tutics.tut.ac.jp (Chan Namkiu) writes:
>In the paper titled _Finding a shortest solution for the nxn extension
>of the 15-puzzle is intractable_ appeared in AAAI-86, D. Ratner and
>M. Warmuth have argued that finding an optimal solution for general
>nxn board puzzle is NP-hard. Specifically, they have shown that
>the following decision problem (nPUZ) is NP-complete.
> Instance: Two nxn boards and a bound k.
> Question: Is there a solution for transforming the first board
> to the second board requiring less than k moves?
This does not indicate that SOLVING a generalized 15-puzzle
is NP-hard (it's far easier than that). It indicates that finding the
OPTIMAL SOLUTION is NP-hard, which is something else again, and not
suprising.
An approach to solving such puzzles is as follows:
1) Solve the top row. Never modify the top row again.
2) Solve the left column (less the top element). Never
modify the left column again.
3) The puzzle has now been reduced from nxn to (n-1) x (n-1).
If n>1, recurse, solving the remaining puzzle.
Proving that this works is left to the reader.
John Nagle
-------------------------------------------------------------------------
>From: bws@ccs.carleton.ca (Brian Sullivan)
Newsgroups: comp.ai
Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected))
Date: 10 Sep 92 13:03:05 GMT
Organization: Carleton University
> This does not indicate that SOLVING a generalized 15-puzzle
>is NP-hard (it's far easier than that). It indicates that finding the
>OPTIMAL SOLUTION is NP-hard, which is something else again, and not
>suprising.
> An approach to solving such puzzles is as follows:
> 1) Solve the top row. Never modify the top row again.
> 2) Solve the left column (less the top element). Never
> modify the left column again.
> 3) The puzzle has now been reduced from nxn to (n-1) x (n-1).
> If n>1, recurse, solving the remaining puzzle.
>Proving that this works is left to the reader.
> John Nagle
This works fine when n > 2 (the last recursion). It is very probable
that the last 3 tiles will be out of order. The only way to deal with
this would be to disturb one of the other rows or columns.
Sorry John, I've had a bad morning and am being picky.
-------------------------------------------------------------------------
>From: allis@cs.rulimburg.nl (Victor Allis)
Newsgroups: comp.ai
Subject: Re: 8 Puzzle (Is it connected)
Date: 10 Sep 92 08:23:50 GMT
Organization: University of Limburg
>The proof goes like this:
>1) A single move is an exchange between the empty space and one other
> piece.
>2) The empty space will, in a single move, change from a black square
> to a white or vice versa.
>3) Thus any sequence of moves that leaves the empty space on the same
> colour will have to be even.
>4) An even number of moves corresponds to an even number of exchanges
> of pieces (including the empty space).
>5) This can be seen from a result about permutations, stating that if
> the permutation can be achieved by an even number of exchanges, no
> odd number of exhanges will achieve the same permutation (and vice
> versa). The permotation is said to have even or odd parity.
>Thus, a solution exist if the empty space starts and ends on the same
>colour and an even number of exchanges is required or the empty space
>starts and ends on opposite colours and an odd number of exchanges is
>required.
The five steps shown above just state that there are AT LEAST two classes
of positions which are closed to the operation of making moves, not that
there are EXACTLY two classes. The conclusion thus is premature.
Note that a similar argument applies to Rubik's Cube, where there are not
two but twelve classes. Or look at a variation of the 8-puzzle, where we
have 4 squares on a line, with one of them empty. Clearly, we can only achieve
four positions, while there are 24 possible permutations, thus there are
six classes.
I remember once proving that if the board has a form such that it can be fully
covered by 2x2 squares, with each of these small squares covering exactly
four squares of the original puzzle (thus not extending over the edge of the
puzzle), then there are EXACTLY two classes of positions.
Victor Allis.
-------------------------------------------------------------------------
>From: peter@icce.rug.nl ()
Subject: Heuristic search and the 8 puzzle
Organization: The ICCE Experience
Date: Wed, 29 Sep 1993 13:21:10 GMT
I'm currently implementing some search algorithms in C++. For testing
purposes I use the 8 puzzle. The problem is what heuristic to
use for best search. The standard heuristic used in the 8 puzzle problem
as described in e.g. 'Nilsson, Problem-solving methods in artificial
intelligence' is the following:
h(n) = P(n) + 3S(n)
Where P(n) is the sum of distances that each tile is from "home" and
S(n) is a 'sequence score': every noncentral tile gets 2 points when it's
not followed by its proper successor and 0 if it is, a piece in the centre
scores 1. So far so good. When I implemented this I got far different results
than Nilsson writes. Next I checked Bratko, who also uses the same heuristic,
but again I didn't get the same result. The problem is not just that nodes
get different values, but (as a consequence of that) a different path is
followed (in one case according to Nilsson and Bratko a solution is found
in 18 steps while my program needs 22). I think the problem is in S(n),
what exactly does it mean that a tile is followed by another tile, does
this also apply to edges? and what about the last tile? (Bratko solves this
apparently by pretending that the last tile is 'followed' by the first, but
even when I followed his scheme I didn't get the same result).
So...my question is, has anyone worked on this before, if so, how did
you compute the sequence score? Or if you never of a better heuristic (this
one isn't admissible) let me know!
Thanks in advance!
Peter Bouthoorn
-------------------------------------------------------------------------
>From: mgv@cs.scarolina.edu (Marco Valtorta)
Subject: Re: Heuristic search and the 8 puzzle
Organization: USC Department of Computer Science
Date: 29 Sep 93 18:02:56 GMT
peter@icce.rug.nl () writes:
>Hi,
>I'm currently implementing some search algorithms in C++. For testing
>purposes I use the 8 puzzle. The problem is what heuristic to
>use for best search. The standard heuristic used in the 8 puzzle problem
> Or if you never of a better heuristic (this
>one isn't admissible) let me know!
>Thanks in advance!
>Peter Bouthoorn
Two very good admissible heuristics are the Linear Conflict heuristic of
O.~Hansson, A.~Mayer, and M.~Yung.
\newblock Relaxed Models Yield Powerful Admissible Heuristics.
\newblock {\it Information Sciences}, to appear.
[This has appeared, but I do not have the exact reference
handy--apologies!]
and the X-Y heuristic described in
A.~Prieditis.
\newblock {\it Machine Discovery of Effective Admissible Heuristics}.
\newblock In {\it Proceedings of the Twelfth International Joint Conference
on
Artificial Intelligence}, Sidney, 1991, 720--725.
I hope this helps. Good luck!
Marco Valtorta, Assistant Professor and Undergraduate Director
Department of Computer Science internet: mgv@usceast.cs.scarolina.edu
University of South Carolina tel.: (1)(803)777-4641
Columbia, SC 29208, U.S.A. fax: 777-3767 tlx: 805038 USC
-------------------------------------------------------------------------
>From: schmid@bastille.berkeley.edu (Scott Schmidler)
Newsgroups: comp.ai
Subject: Re: Heuristic search and the 8 puzzle
Date: 1 Oct 1993 03:54:37 GMT
Organization: University of California, Berkeley
In article ,
Marco Valtorta wrote:
>Two very good admissible heuristics are the Linear Conflict heuristic of
>O.~Hansson, A.~Mayer, and M.~Yung.
>\newblock Relaxed Models Yield Powerful Admissible Heuristics.
>\newblock {\it Information Sciences}, to appear.
>[This has appeared, but I do not have the exact reference
>handy--apologies!]
The reference for this is:
O. Hansson, A.Mayer, and M. M. Yung. Criticizing Solutions to
Relaxed Models Yields Powerful Admissible Heuristics.
Information Sciences, 63:3, 1992
scott.
Article 27136 of comp.ai:
Xref: acsu.buffalo.edu comp.ai:27136 sci.math:93568
Newsgroups: comp.ai,sci.math
Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!udel!gatech!howland.reston.ans.net!math.ohio-state.edu!jussieu.fr!pasteur.fr!news2.EUnet.fr!julienas!fozzie!phil
From: phil@eurocontrol.fr (Philip Gibbs)
Subject: Re: How many eight puzzle states?
Sender: news@fozzie.eurocontrol.fr (News Distribution System)
Message-ID: <1995Feb14.141038.18372@fozzie.eurocontrol.fr>
Date: Tue, 14 Feb 1995 14:10:38 GMT
Reply-To: phil@galilee.eurocontrol.fr
References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu>
Nntp-Posting-Host: galilee.eurocontrol.fr
Organization: Eurocontrol
Lines: 27
In article , nagle@netcom.com (John Nagle) writes:
>
> Half the possible states are legal, but I don't have a cite for that.
>
> Incidentally, the way to solve the 2^N-1 puzzle generally is as
you mean N^2-1
> follows:
>
> 1. Solve the top row. Never touch it again.
> 2. Solve the left column. Never touch it again.
> 3. Recurse to solve the remaining subpuzzle.
>
If you know about signatures of permutations you can solve this problem. In
the case where N is even the signature of the permutation of the pieces is
an invariant of the group of transformations. That is the permutation defined
by reading of the numbers left-to-right and top-to-bottom and ignoring the
space. Therefore only even permutations can be legal. To show that all
even permutations are legal you just have to prove that the solution John
described works for those cases.
Sorry that's a bit brief I'm in a rush.
Article 27148 of comp.ai:
Xref: acsu.buffalo.edu comp.ai:27148 sci.math:93630
Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!udel!news.sprintlink.net!howland.reston.ans.net!EU.net!nova.puug.pt!news.rccn.net!news.ist.utl.pt!poirot.ist.utl.pt!aml
From: aml@poirot.ist.utl.pt (Antonio Leitao)
Newsgroups: comp.ai,sci.math
Subject: Re: How many eight puzzle states?
Date: 14 Feb 1995 19:29:36 GMT
Organization: Grupo de Inteligencia Artificial, Instituto Superior Tecnico
Lines: 91
Distribution: world
Message-ID:
References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu>
NNTP-Posting-Host: sol.ist.utl.pt
In-reply-to: cswellin@eos.ncsu.edu's message of 13 Feb 1995 14:49:01 GMT
In article <3hnrgt$o3d@taco.cc.ncsu.edu> cswellin@eos.ncsu.edu (Carol Smith Wellington) writes:
>
>In article <3hmhuv$803@tribune.usask.ca>, Henry_Choy@engr.usask.ca (Henry Choy) writes:
>>
>> How do you find the number of states in the eight puzzle?
>>
>> --
>>
>> Henry Choy
>> choy@cs.usask.ca
>>
>
>There are 9! states if you do not consider the fact that some states
>cannot be reached from a legal starting state without picking up some of the
>tiles. The problem is how to enumerate those illegal states. While I believe
>proofs are available, unfortunately, I have not proven my intuition about the
>number of illegal states.
>
>I have discovered picking up and switching an odd number of pairs of tiles
>from a legal state gives an illegal state. In addition, rotating any 4 tiles
>of a legal state gives an illegal state. Unfortunately, not all operations
>which can cause illegal states always do. For instance, rotating 5 tiles from
>a legal state may cause an illegal state, but might lead to another legal state.
>
>In general, for every legal state I can give at least one illegal state without
>worrying about duplicates from modifying other legal states. For instance, for
>every legal state, the state generated by switching the first two tiles will be
>illegal and specific to this state. Therefore, the number of legal states
>cannot be greater than 9!/2, but I cannot prove that is the exact number of
>legal states.
>
You are absolutely right and 9!/2 is indeed the number of 'legal' states, but
there are no such thing as 'illegal' states.
The state space of the 8-puzzle can be divided in two halves, where any state
in one half can reach any other state in the same half but not in the other
half. There is a proof of this property but I forgot it...sorry :-)
To check if two states are in the same half there is an algorithm:
1) Concatenate all rows of the puzzle in a single row.
For instance
3 4 5
6 2 1
8 b 7
becomes 3 4 5 6 2 1 8 b 7 (b is the empty tile)
2) Define a reference state (for instance 1 2 3 4 5 6 7 8 b)
3) Count the number of misplaced pieces that are in front of each piece
(relative to the reference state) and
sum this for every piece. Do this for the two states of the problem.
4) If both count are odd or even, the states are in the same half, otherwise
they are in different halves and you can't reach one from the other.
Ex:
1 2 3 1 2 3
4 5 6 -> 5 4 6
7 8 b 7 8 b
1 2 3 4 5 6 7 8 b has zero misplaced pieces relative to the reference state
1 2 3 5 4 6 7 8 b has one misplaced pieces relative to the reference state(5
is before 4)
So we can conclude that this example is impossible.
The same thing is true for the 15-puzzle (15!/2 states in each half) and so on.
Finally, let's answer the initial question:
>> How do you find the number of states in the eight puzzle?
Consider an empty puzzle (no pieces).
You can put a 1 in the first position or in the second or in the third...
or in the ninth, that is 9 hypotheses. For each one, you can put a 2 in any
other of the remaining 8 free positions, that is 8 hypotheses for each of
the previous 9 hypotheses. Do this to all pieces, including the empty one,
and you will get 9*8*7*6*5*4*3*2*1 hypotheses, that is 9!.
Aml
Article 27179 of comp.ai:
Xref: acsu.buffalo.edu comp.ai:27179 sci.math:93735
Path: acsu.buffalo.edu!ub!dsinc!spool.mu.edu!howland.reston.ans.net!gatech!taco.cc.ncsu.edu!cswellin
From: cswellin@eos.ncsu.edu (Carol Smith Wellington)
Newsgroups: comp.ai,sci.math
Subject: Re: How many eight puzzle states?
Date: 13 Feb 1995 14:49:01 GMT
Organization: North Carolina State University, Project Eos
Lines: 33
Distribution: world
Message-ID: <3hnrgt$o3d@taco.cc.ncsu.edu>
References: <3hmhuv$803@tribune.usask.ca>
Reply-To: cswellin@eos.ncsu.edu (Carol Smith Wellington)
NNTP-Posting-Host: c00746-400wi.eos.ncsu.edu
Originator: cswellin@c00746-400wi.eos.ncsu.edu
In article <3hmhuv$803@tribune.usask.ca>, Henry_Choy@engr.usask.ca (Henry Choy) writes:
>
> How do you find the number of states in the eight puzzle?
>
> --
>
> Henry Choy
> choy@cs.usask.ca
>
> Anything worth doing is worth overdoing. - R. Heinlein
> is worth doing well. - Philip Dormer Stanhope, Earl of Chesterfield
>
There are 9! states if you do not consider the fact that some states
cannot be reached from a legal starting state without picking up some of the
tiles. The problem is how to enumerate those illegal states. While I believe
proofs are available, unfortunately, I have not proven my intuition about the
number of illegal states.
I have discovered picking up and switching an odd number of pairs of tiles
from a legal state gives an illegal state. In addition, rotating any 4 tiles
of a legal state gives an illegal state. Unfortunately, not all operations
which can cause illegal states always do. For instance, rotating 5 tiles from
a legal state may cause an illegal state, but might lead to another legal state.
In general, for every legal state I can give at least one illegal state without
worrying about duplicates from modifying other legal states. For instance, for
every legal state, the state generated by switching the first two tiles will be
illegal and specific to this state. Therefore, the number of legal states
cannot be greater than 9!/2, but I cannot prove that is the exact number of
legal states.
Article 27202 of comp.ai:
Xref: acsu.buffalo.edu comp.ai:27202 sci.math:93801
Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!noc.near.net!root
From: alan@cit.state.vt.us (Alan Williams)
Newsgroups: comp.ai,sci.math
Subject: Re: How many eight puzzle states?
Date: 15 Feb 1995 13:59:06 GMT
Organization: State of Vermont
Lines: 40
Message-ID: <3ht1ba$c3b@vtsis05.cit.state.vt.us>
References: <3hmhuv$803@tribune.usask.ca> <1995Feb13.181516.19455@zh014.ubs.ubs.ch>
NNTP-Posting-Host: cit11.cit.state.vt.us
X-Newsreader: WinVN 0.92.6+
In article <1995Feb13.181516.19455@zh014.ubs.ubs.ch>, bit@svusenet.ubs.ch says:
>
>Henry Choy (Henry_Choy@engr.usask.ca) wrote:
>: How do you find the number of states in the eight puzzle?
>
>What is the eight puzzle ?
>
I think the origial posting referred to the sliding block puzzle:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 | <=== Impressive ASCII art huh?
+---+---+---+
| 7 | 8 | |
+---+---+---+
There are 9! ways of putting the 8 tiles in place. Since the puzzle
has a parity of 2 any initial configuration can be transformed (by sliding)
into exactly 9!/2 - 1 of the other configurations. For instance, the
configuration shown above cannot be transformed into:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 | <=== Even More Impressive ASCII art.
+---+---+---+
| 8 | 7 | |
+---+---+---+
See the rec.puzzles FAQ, probably under The Fifteen Puzzle.
Alan "Flame me *real* hard if I goofed" Williams
State of Vermont
alan@cit.state.vt.us
Article 27229 of comp.ai:
Xref: acsu.buffalo.edu comp.ai:27229 sci.math:93928
Newsgroups: comp.ai,sci.math
Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!hookup!swrinde!howland.reston.ans.net!ix.netcom.com!netcom.com!nagle
From: nagle@netcom.com (John Nagle)
Subject: Re: How many eight puzzle states?
Message-ID:
Organization: NETCOM On-line Communication Services (408 261-4700 guest)
References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu>
Date: Tue, 14 Feb 1995 01:12:48 GMT
Lines: 27
Sender: nagle@netcom19.netcom.com
cswellin@eos.ncsu.edu (Carol Smith Wellington) writes:
>I have discovered picking up and switching an odd number of pairs of tiles
>from a legal state gives an illegal state. In addition, rotating any 4 tiles
>of a legal state gives an illegal state. Unfortunately, not all operations
>which can cause illegal states always do. For instance, rotating 5 tiles from
>a legal state may cause an illegal state, but might lead to another legal state.
>In general, for every legal state I can give at least one illegal state without
>worrying about duplicates from modifying other legal states. For instance, for
>every legal state, the state generated by switching the first two tiles will be
>illegal and specific to this state. Therefore, the number of legal states
>cannot be greater than 9!/2, but I cannot prove that is the exact number of
>legal states.
Half the possible states are legal, but I don't have a cite for that.
Incidentally, the way to solve the 2^N-1 puzzle generally is as
follows:
1. Solve the top row. Never touch it again.
2. Solve the left column. Never touch it again.
3. Recurse to solve the remaining subpuzzle.
Once you know this, all the fun goes out of doing it by hand. You
also realize it's really a rather lame puzzle.
John Nagle
Article 27296 of comp.ai:
Xref: acsu.buffalo.edu comp.ai:27296 sci.math:94211
Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!newshost.marcam.com!charnel.ecst.csuchico.edu!nic-nac.CSU.net!usc!howland.reston.ans.net!pipex!sunsite.doc.ic.ac.uk!susx.ac.uk!mattst
From: mattst@cogs.susx.ac.uk (Matthew Stanfield)
Newsgroups: comp.ai,sci.math
Subject: Re: How many eight puzzle states?
Followup-To: comp.ai,sci.math
Date: 20 Feb 1995 20:00:44 GMT
Organization: University of Sussex
Lines: 272
Distribution: world
Message-ID: <3iasdc$srd@infa.central.susx.ac.uk>
References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu>
NNTP-Posting-Host: tsunb-gw.susx.ac.uk
X-Newsreader: TIN [version 1.2 PL2]
: > How do you find the number of states in the eight puzzle?
: > Henry Choy
: > choy@cs.usask.ca
: >
: > Anything worth doing is worth overdoing. - R. Heinlein
Henry,
Well if that's your signing off quotation, here's a POP11
program written by me to solve the 8 puzzle. It uses blind
search so it's fairly inefficient - but quite quick anyway.
Enjoy it.
Matthew 'Anything worth doing is worth overdoing' Stanfield
mattst@cogs.susx.ac.uk (No big sigs = No mess!)
;;; The 8 puzzle solution.
;;; By Matthew Stanfield
;;; Start takes the 'completed' puzzle & makes a jumbled puzzle, which
;;; guarantees that the puzzle is solvable. Then it gives this solvable
;;; puzzle to search, initiating the whole solving process.
define start();
[[1 2 3][4 5 6][7 8 9]] -> state;
repeat 9 times
oneof(nextfrom(state)) -> state;
endrepeat;
state =>
pr(newline);
search(state);
enddefine;
define search(state);
vars alternatives considered templist;
[^state] -> alternatives; ;;;initially the start state is the only alternative to search from
[] -> considered;
until alternatives==[] do ;;;Keep searching until nor more alternatives
dest(alternatives)->alternatives->state; ;;; pick first state in alternatives
;;; equivalent to hd(alternatives)->state;
;;; tl(alternatives)->alternatives;
[^state ^^considered] -> considered; ;;;add chosen state to considered list
print(state);
if isgoal(state) then ;;; if it solves the problem then return
return(state)
endif;
nextfrom(state) -> templist; ;;;generate list of daughter states
for state in templist do ;;;unless these have been seen before insert them into
;;;alternatives list
unless isoneof(state,alternatives) or isoneof(state,considered) then
insert(state, alternatives) -> alternatives
endunless;
endfor;
enduntil;
return(false); ;;;return false if run out of alternatives
enddefine;
define isoneof(state,list); ;;;checks if a state is already in a list (criterion of equality given by
;;;samestate
vars prevstate;
for prevstate in list do
if samestate(state, prevstate) then
return(true);
endif;
endfor;
return(false)
enddefine;
define insert(newstate, list) -> result; ;;;inserts a state into a list ordered by isbetter
vars state, rest;
if list matches [?state ??rest] and isbetter(state, newstate) then
insert(newstate, rest) -> result;
[^state ^^result] -> result;
else
[^newstate ^^list] -> result;
endif;
enddefine;
;;; Nextfrom takes state and returns output which is a list of lists.
;;; Each of these lists is a possible move for the blank piece. Find_blank
;;; finds the position of the blank piece. Change_pos then does the swaping
;;; if appropriate leaving the new list on the stack for the '[% %]'
;;; notation to pick up. The result is the list of daughter states.
define nextfrom(state) -> output;
vars r c t;
copytree(state) -> t;
find_blank(state) -> c -> r;
[% if r > 1 then
change_pos(r-1, c, r, c, t);
endif;
copytree(state) -> t;
if r < 3 then
change_pos(r+1, c, r, c, t);
endif;
copytree(state) -> t;
if c > 1 then
change_pos(r, c-1, r, c, t);
endif;
copytree(state) -> t;
if c < 3 then
change_pos(r, c+1, r, c, t);
endif; %] -> output;
enddefine;
;;; Change_pos swaps the blank piece and the piece it is going to replace.
;;; The variables are : r & c the row & column (within the list) of the
;;; piece where the blank is going to move and br & bc which is the position
;;; of the blank piece.
define change_pos(r, c, br, bc, list) -> new;
vars temp;
copytree(list) -> new;
new(r)(c) -> temp;
9 -> new(r)(c);
temp -> new(br)(bc);
enddefine;
;;; Find_blank finds the position of the blank piece. It returns r & c which
;;; is the blanks position in the list. '9' denotes the blank.
define find_blank(list) -> c -> r;
1 -> r;
1 -> c;
until list(r)(c) = 9 do
c + 1 -> c;
if c = 4 then
1 -> c, r + 1 -> r;
endif;
enduntil;
enddefine;
;;; Isbetter takes 2 states & decides which is nearer the solution. It gets the
;;; Manhatan distance for each state and returns true or false. [Nb: True if
;;; they are equal - it must make a decision!]
define isbetter(state1, state2);
vars score1 score2;
get_md(state1) -> score1;
get_md(state2) -> score2;
if score1 <= score2 then
return(true);
else
return(false);
endif;
enddefine;
;;; Get_md returns the Manhatan distance which is the total of the distances
;;; that each piece has to travel before it is in the correct place. This
;;; includes the position of the blank.
define get_md(list) -> total;
vars r1 r2 num pos act;
0 -> total;
for r1 from 1 to 3 do
for r2 from 1 to 3 do
list(r1)(r2) -> pos;
cords_total(pos) -> num;
r1 + r2 -> act;
abs(act - num) + total -> total;
endfor;
endfor;
enddefine;
;;; Coords_total returns the sum of row + column for any particuar position of
;;; a piece in the state, this is necessary for the calculation of the Manhatan
;;; distance.
define cords_total(num) -> total;
vars row col;
if num = 1 then 1 -> row, 1 -> col;
elseif num = 2 then 1 -> row, 2 -> col;
elseif num = 3 then 1 -> row, 3 -> col;
elseif num = 4 then 2 -> row, 1 -> col;
elseif num = 5 then 2 -> row, 2 -> col;
elseif num = 6 then 2 -> row, 3 -> col;
elseif num = 7 then 3 -> row, 1 -> col;
elseif num = 8 then 3 -> row, 2 -> col;
elseif num = 9 then 3 -> row, 3 -> col;
endif;
row + col -> total;
enddefine;
;;; Isgoal returns true or false as to whether its input state is the final
;;; solution or not.
define isgoal(state);
if state = [ [1 2 3] [4 5 6] [7 8 9] ] then
return(true);
else
return(false);
endif;
enddefine;
;;; Samestate returns true or false as to whether its 2 states of input are the
;;; same or not, that is equal rather than identical.
define samestate(state1, state2);
if state1 = state2 then
return(true);
else
return(false);
endif;
enddefine;
;;; Print prints state in the shape of the puzzle.
define print(state);
vars i item;
for i from 1 to 3 do
for item from 1 to 3 do
pr(tab);
pr(state(i)(item));
endfor;
pr(newline);
endfor;
pr(newline);
enddefine;
start(); ;;; Initiates the program.
/* Sample output...
** [[2 9 3] [1 5 6] [4 7 8]]
2 9 3
1 5 6
4 7 8
2 5 3
1 9 6
4 7 8
2 5 3
1 7 6
4 9 8
2 5 3
1 7 6
4 8 9
2 5 3
1 7 9
4 8 6
9 2 3
1 5 6
4 7 8
1 2 3
9 5 6
4 7 8
1 2 3
4 5 6
9 7 8
1 2 3
4 5 6
7 9 8
1 2 3
4 5 6
7 8 9
*/
Article 50004 of comp.ai:
Newsgroups: comp.ai
Path: acsu.buffalo.edu!news.acsu.buffalo.edu!news.sunydutchess.edu!zombie.ncsc.mil!newsgate.duke.edu!nntprelay.mathworks.com!newsfeed.internetmci.com!4.1.16.34!cpk-news-hub1.bbnplanet.com!news.bbnplanet.com!ix.netcom.com!nagle
From: nagle@netcom.com (John Nagle)
Subject: Re: The Eight Pazzle
Message-ID:
Organization: Netcom On-Line Services
X-Newsreader: NN version 6.5.0 CURRENT #9
References: <19971201202101.PAA20392@ladder01.news.aol.com> <65v97h$8ke$1@pith.uoregon.edu>
Date: Tue, 2 Dec 1997 02:45:09 GMT
Lines: 24
Sender: nagle@netcom6.netcom.com
Xref: acsu.buffalo.edu comp.ai:50004
ginsberg@dt.cirl.uoregon.edu (Matthew L. Ginsberg) writes:
>In article <19971201202101.PAA20392@ladder01.news.aol.com>,
>SHANHON wrote:
>>Hello, everyone. I have some trouble in this problem, "The Eight Pazzle". I
>>have tried to search information about this from Internet, but I cannot find
>>anything useful for this problem. Can anyone explain it for me?
>Any good AI text should have a reasonable description of this
>problem.
>You might consider starting with the text in the AI class that
>you are currently taking.
It's a classic AI problem, although algorithmic solutions are
available.
The general 2^N-1 puzzle can be solved as follows:
- Solve the top row. Never touch it again.
- Solve the remainder of the left column. Never touch it again.
- You have now reduced the order of the puzzle by 1. Recurse
as necessary.
John Nagle