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.
>
>