Your number of configurations i misleading since there ios plenty of symmetry. I expect someone from Donald Michie's Dept. of machine Intelligence working in the 60's will have done the computation in Edinburgh. John McKay From: IN%"math-fun@mailman.xmission.com" "math-fun" 9-NOV-2003 21:37:37.48 To: IN%"math-fun@mailman.xmission.com" "math-fun" CC: Subj: RE: [math-fun] 15-puzzle Return-path: <math-fun-bounces@mailman.xmission.com> Received: from clyde.concordia.ca (clyde.Concordia.CA [132.205.1.1]) by vax2.concordia.ca (PMDF V6.2 #30759) with ESMTP id <01L2UCJ5B1GA000YT5@vax2.concordia.ca> for mckay@vax2.concordia.ca (ORCPT mckay@vax2.concordia.ca); Sun, 09 Nov 2003 21:37:36 -0400 (EDT) Received: from mailman.xmission.com (mailman.xmission.com [198.60.22.29]) by clyde.concordia.ca (8.12.10/8.12.10) with ESMTP id hAA2bQk9172924 for <mckay@vax2.concordia.ca>; Sun, 09 Nov 2003 21:37:26 -0500 (EST) Received: from localhost ([127.0.0.1] helo=mailman.xmission.com) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1AJ1vY-0001V5-03; Sun, 09 Nov 2003 19:37:16 -0700 Received: from place.org ([65.163.18.18] helo=zachs.place.org ident=postfix) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1AJ1vW-0001Uy-00 for <math-fun@mailman.xmission.com>; Sun, 09 Nov 2003 19:37:14 -0700 Received: from ACW.alum.mit.edu (pool-129-44-175-237.bos.east.verizon.net [129.44.175.237]) by zachs.place.org (Postfix) with ESMTP id E61A8180EC for <math-fun@mailman.xmission.com>; Sun, 09 Nov 2003 20:36:57 -0600 (CST) Date: Sun, 09 Nov 2003 21:28:51 -0500 From: "Allan C. Wechsler" <acw@alum.mit.edu> Subject: Re: [math-fun] 15-puzzle In-reply-to: <200311100120.UAA84181@fry.research.att.com> Sender: math-fun-bounces@mailman.xmission.com X-Sender: acw@place.org To: math-fun <math-fun@mailman.xmission.com> Errors-to: math-fun-bounces@mailman.xmission.com Reply-to: math-fun <math-fun@mailman.xmission.com> Message-id: <5.1.0.14.0.20031109212244.023f4d90@place.org> MIME-version: 1.0 X-Mailer: QUALCOMM Windows Eudora Version 5.1 Content-type: text/plain; format=flowed; charset=us-ascii Precedence: list X-BeenThere: math-fun@mailman.xmission.com X-Mailman-Version: 2.1.1 X-Scanned-By: MIMEDefang 2.35 List-Post: <mailto:math-fun@mailman.xmission.com> List-Subscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=subscribe> List-Unsubscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=unsubscribe> List-Archive: <http://mailman.xmission.com/cgi-bin/mailman/private/math-fun> List-Help: <mailto:math-fun-request@mailman.xmission.com?subject=help> List-Id: math-fun <math-fun.mailman.xmission.com> Original-recipient: rfc822;mckay@vax2.concordia.ca

I'm surprised that the 4x4 case hasn't been solved - can anyone help? NJAS Why is this surprising? There are more than 2e13 configurations. If we could search a thousand configurations per second, considering each of them would take almost a millennium. So, someone will have to do some non-trivial theory in order to get a better handle on the diameter of the 15-puzzle. I believe the diameter of Rubik's Cube is also not known, in any of the popular metrics. -A

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun