From Don.Woods@eng.sun.com Wed Dec 15 06:04:15 1993 Return-Path: Received: from Sun.COM by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07720; Wed, 15 Dec 93 06:04:15 EST Received: from Eng.Sun.COM (zigzag.Eng.Sun.COM) by Sun.COM (4.1/SMI-4.1) id AA22455; Tue, 14 Dec 93 14:48:16 PST Received: from colossal.Eng.Sun.COM by Eng.Sun.COM (4.1/SMI-4.1) id AA21191; Tue, 14 Dec 93 14:47:01 PST Received: by colossal.Eng.Sun.COM (5.0/SMI-SVR4) id AA22891; Tue, 14 Dec 93 14:48:17 PST Date: Tue, 14 Dec 93 14:48:17 PST From: Don.Woods@eng.sun.com (Don Woods) Message-Id: <9312142248.AA22891@colossal.Eng.Sun.COM> To: Cube-Lovers@ai.mit.edu Subject: Re: Tangle X-Sun-Charset: US-ASCII Content-Length: 2501 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.