Path: utzoo!attcan!uunet!mcsun!tuvie!vmars!gerhard
From: gerhard@vmars.tuwien.ac.at (Gerhard Fohler)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Message-ID: <1894@tuvie>
Date: 2 Oct 90 14:18:48 GMT
References: <1491@meaddata.meaddata.com>
Sender: news@tuvie
Lines: 22

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