From xirion!jandr@relay.nl.net Thu Dec 23 02:48:30 1993 Return-Path: Received: from sun4nl.NL.net by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08367; Thu, 23 Dec 93 02:48:30 EST Received: from xirion by sun4nl.NL.net via EUnet id AA04747 (5.65b/CWI-3.3); Thu, 23 Dec 1993 08:48:27 +0100 Received: by xirion.xirion.nl id AA04326 (5.61/UK-2.1); Thu, 23 Dec 93 08:47:44 +0100 From: Jan de Ruiter Date: Thu, 23 Dec 93 08:47:44 +0100 Message-Id: <4326.9312230747@xirion.xirion.nl> X-Organization: Xirion Unix Software & Consultancy bv Burgemeester Verderlaan 15 X 3454 PE De Meern The Netherlands X-Phone: +31 3406 61990 X-Fax: +31 3406 61981 To: cube-lovers@ai.mit.edu Subject: Re: Rubiks tangle To: anandrao@hk.super.net Cc: cube-lovers@ai.mit.edu >Your concept is theoretically extendable to the 10*10 tangle, but even >with this optimisation the puzzle would take a long time to solve. How >long do you take for the 5*5 Tangle on your computer? Your question prompted me to actually write the program, and to squeeze as much efficiency from the program as I could. You wrote on december the 14th, your program took about 20 minutes on a 486DX2-66, Don Woods writes on the same date, that his program takes 45 seconds on a SparcStation II, And now I am proud to present my timing: trrrrr (drum roll) 7 seconds on a Compacq Deskpro 386/33. (and still only brute force!) Now I am ready to try the 10x10. Some thoughts in the mean time: If the algorithm treats the duplicate pieces just as ordinary pieces, i.e. as different, this will cause the program to find 4 solutions for the 5x5 where only 2 exist (by exchanging the duplicate pieces). This factor of 2 may not be dramatical, but if the same algorithm tries the 10x10, then for every 1 solution that exists, the program will find (5!)^4 x (4!)^20 identical versions (combinations of duplicate exchanges). My program views duplicate pieces as one, which may be placed several times. So for some position X a piece with duplicates will only be tried once. Don Woods writes: >Regarding solving the Tangle, I forgot one other minor optimisation: >When my program is picking a corner piece other than the first, it >requires that the piece "number" be less than or equal to that of the >first corner. I.e., it refuses to search for solutions that are >rotations of other solutions. My program prevents finding rotations of solutions, by excluding the rotations of just one piece. The list of possibilities to try on any position includes this one piece just once, and every other piece four times. You can choose any piece for this, except the duplicated one. Regrettably this approach works only for the 5x5: the 10x10 will probably have to use Don Woods method. - Jan D. de Ruiter