Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: 8-tile puzzle
Message-ID: <3343@goanna.cs.rmit.oz.au>
Date: 30 Jun 90 07:56:20 GMT
References: <12398@sun.udel.edu>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 16

In article <12398@sun.udel.edu>, jms@sun.udel.edu (John Milbury-Steen) writes:
> [the 8-puzzle, any heuristics?  how about a Prolog program?]

A reasonable approach is to use the A* algorithm.  That requires an
estimate of the distance from the current position to a solution, and
a fairly common heuristic for that is to count the number of tiles
which are not in their final position.  A* is not _quite_ as trivial
as depth first search (although if you have the DEC-10 Prolog or
Quintus Prolog library(heaps) and library(ordsets) packages or
functional equivalents it's actually rather simple) but for a problem
like this where the search space has more cycles than you can shake
a stick at and isn't all that small even if you disregard the cycles,
the extra performance of A* is well worth having.

-- 
"private morality" is an oxymoron, like "peaceful war".