Fwd: about hard 8puzzles

[Subbarao Kambhampati <rao@asu.edu>]

Date: Tue, 30 Sep 2003 17:25:54 -0700 (MST)
From: menkes@asu.edu
Subject: about hard 8puzzles
X-Originating-IP: 149.169.28.102
To: rao@asu.edu
Cc: th@asu.edu
User-Agent: IMP/PHP IMAP webmail program 2.2.3
X-Spam-Status: No, hits=-98.2 required=5.0
        tests=BAYES_01,NO_REAL_NAME,USER_AGENT,USER_IN_WHITELIST
        version=2.53
X-Spam-Level:
X-Spam-Checker-Version: SpamAssassin 2.53 (1.174.2.15-2003-03-30-exp)



Dr. Rao,

Me and Thomas were checking which 8 puzzle initial positions would take a
maximum number of optimal moves towards the goal state. According to this
webpage the worst case scenario for an 8-puzzle is 31 steps. This guy did
actually do a total enumeration on all the 9! different initial positions to
find the true "worst case" position.

http://www.msoworld.com/programming/results0001.html

Menkes