From anandrao@hk.super.net Wed Dec 15 20:14:26 1993 Return-Path: Received: from hk.super.net by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17907; Wed, 15 Dec 93 20:14:26 EST Received: by hk.super.net id AA22615 (5.65c/IDA-1.4.4 for Cube-Lovers@ai.mit.edu); Thu, 16 Dec 1993 09:14:05 +0800 Date: Thu, 16 Dec 1993 09:09:21 +0800 (HKT) From: Mr Anand Rao Subject: Re: Tangle To: Don Woods Cc: Cube-Lovers@ai.mit.edu In-Reply-To: <9312142248.AA22891@colossal.Eng.Sun.COM> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII My method is essentially the same as yours - I have several intermediate tables which cut down the processing required within the innermost loop. I tried the same for 10*10 but it was taking eons. I tried making tables of 2*2 arrangements and solving for 5*5 of these(thereby solving the original 10*10, but the number of 2*2 arrangements makes the problem intractable on my measly little computer. I even trie putting together all possible 5*5 solutions and assembling them in the 10*10 pattern, but the number of 5*5 solutions with the 100 tiles is in millions! Do you have any further insight? On Tue, 14 Dec 1993, Don Woods wrote: > Anand Rao writes: > > The puzzles are similar, except that the extra(25th) > > piece is different in each. The solutions for each puzzle are very > > different and I could not see any pattern. > > Look again. The puzzles are identical except for a remapping of the colors. > For example, if you take Tangle #1 and paint all the Blue ropes Yellow, all > the Red ropes Blue, all the Green ropes Red, and all the (originally) Yellow > ropes Green, you'll have Tangle #2. So you can solve Tangle #1 by imagining > the ropes recolored as above, constructing your solution for #2, and then > restoring the original colors. > > Note: The particular recoloring given above is based on colors given in a > message sent by CCW@eql.caltech.edu (Chris Worrell) to cube-lovers on April > 27, 1992. I own only #1 myself and so cannot confirm or deny the accuracy > of the colors. But the basic idea applies, given that each puzzle (a) has > the same pattern of ropes on all pieces and (b) has each permutation of > colors exactly once except for one permutation which appears twice. > > Solving the 10x10 is another kettle of fish, and I haven't tried it. I do > have a program that solves the 5x5 in about 45 seconds on a SparcStation II, > but I haven't looked into how much longer it would take on the 10x10. > > "Dale I. Newfield" writes: > > Could you explain what your algorithm was? > > Has anyone found a non-brute-force solution scheme? > > My solution was brute-force. I posted to cube-lovers (again, in April '92) > asking if anyone had found a more logical approach to the puzzle, but got no > affirmative responses. > > Dale's method is a little inefficient in the order in which it tries tiles. > Mine used the sequence: Dale's used: > > 1 3 5 7 9 1 2 4 7 11 > > 2 4 6 8 10 3 5 8 12 16 > > 11 12 13 14 15 6 9 13 17 20 > > 16 17 18 19 20 10 14 18 21 23 > > 21 22 23 24 25 15 19 22 24 25 > > The first three tiles in our two methods are equally constrained, but the > next seven in Dale's methods are constrained along 1-2-1-1-2-2-1 edges, > while mine are constrained along 2-1-2-1-2-1-2 edges. So I suspect my > search tree gets trimmed a bit more quickly. Another way in which the > search can be made more efficient is in finding the pieces to try in each > position. For each pair of colors that can appear along an edge, my program > precomputes a table listing all tiles that can match that pair of colors, > including how to rotate the tiles. > > -- Don. > >