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