Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!cis.ohio-state.edu!tut.cis.ohio-state.edu!anaconda.cis.ohio-state.edu!meekins
From: meekins@anaconda.cis.ohio-state.edu (timothy lee meekins)
Newsgroups: comp.sys.apple2
Subject: Re: Sliding puzzle problem
Message-ID: <106590@tut.cis.ohio-state.edu>
Date: 12 Apr 91 03:21:03 GMT
References: <1991Apr11.175025.29639@kuhub.cc.ukans.edu>
Sender: news@tut.cis.ohio-state.edu
Organization: The Ohio State University, Department of Computer and Information Science
Lines: 29

In article <1991Apr11.175025.29639@kuhub.cc.ukans.edu> 2hnemarrow@kuhub.cc.ukans.edu writes:
>Excuse me if this sounds a little unrelated, but I need to know the worst case
>and maximum number of moves it takes to solve a 3X3 sliding puzzle, and it
>looks something like this:
>
> _________________
>|     |     |     |
>|  1  |  2  |  3  |        I need it for a program I am writing.
>|_____|_____|_____|        Thanks in advance,
>|     |     |     |
>|  4  |  5  |  6  |        2hnemarrow@kuhub.cc.ukans.edu
>|_____|_____|_____|
>|     |     |     |        Watch for HCADgs v2.0
>|  7  |  8  |     |        Coming soon to a BBS near you!
>|_____|_____|_____|


It will run FOREVER if you don't check in your search tree to see
if you've been in this position before. In the 8-puzzle it is quite
easy to get into a cycle and run forever. I need to go dig out
my AI notes to see what the actual answer is, but I don't remember it
being all that bad.

What is HCADgs? Sounds interesting!
--
+---------------------------S-U-P-P-O-R-T-----------------------------------+
|/ Tim Meekins                  <<>> Snail Mail:           <<>>  Apple II  \|
|>   meekins@cis.ohio-state.edu <<>>   8372 Morris Rd.     <<>>  Forever!  <|
|\   timm@pro-tcc.cts.com       <<>>   Hilliard, OH 43026  <<>>            /|