Path: utzoo!attcan!uunet!mcsun!ukc!edcastle!aipna!uk.ac.ed.aipna!peter
From: peter@uk.ac.ed.aipna (Peter Ross)
Newsgroups: comp.lang.prolog
Subject: Re: 8-tile puzzle
Message-ID: <2580@aipna.ed.ac.uk>
Date: 4 Jul 90 10:20:08 GMT
References: <12398@sun.udel.edu> <3343@goanna.cs.rmit.oz.au> <36714@shemp.CS.UCLA.EDU>
Sender: news@aipna.ed.ac.uk
Reply-To: peter@uk.ac.ed.aipna (Peter Ross)
Organization: Dept of AI, University of Edinburgh, Scotland
Lines: 23

ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:

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

A lightweight comment: the heuristic I use which enables me to solve
the 8- and 15-puzzles by hand without much trouble is, to refer to
the 8-puzzle case, to look at it as a roundabout of the eight exterior
cells and a single register in the centre. I use the single register
while doing a sort of the sequence of the eight exterior cells to
achieve the order 1/2/3/6/blank/8/7/4. The operators are obvious:
cycle the roundabout one left, cycle it one right, move the blank to or
from a centre-side. The same idea applies to the 15-puzzle; the main
memory load is remembering the ordering of the exterior cells to be
achieved. I find it harder to work the 24-puzzle..

Not difficult to implement this in Prolog, of course.

Peter Ross
Dept of AI
Edinburgh University