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 <email@example.com> 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" <firstname.lastname@example.org> 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
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 1611 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.