From:

~~~ ~~~ Subject:

Having done a number of calculations on maximal distances I thought about

getting at newer pastures. The Magic Domino. The results follow in the

next mailing, this post discusses a bit about the information found there.

I added to the next mail also the previous results for the 2x2x2 and the

corners of the 3x3x3 together with some additional results not presented

previously. There are for each puzzle five columns. The first one

enumerates the number of moves, the next two give the results if both

quarter and half turns are accepted as moves, the last two give the

information if only quarter turns are accepted (of course, on the Domino

this distinction is there only for the U and D faces, the others know

half turns only). For each case there are two columns, the first giving the

number of positions requiring the stated number of moves, the second

column gives the number of local maxima (i.e. each move brings you closer

to a solution).

There are three tables for the Domino. The one you want to pick depends

on how you view the puzzle. The first view is that there is only one

solution with on top 1 to 3 running from left back to right back. The

second view is that rotation of the puzzle makes different configurations

indistinguishable, so the total number of configuration is (8!)^2 / 4.

An alternative way to look at it is that there are 4 solutions. One the

standard solution, the others obtained by rotating the domino along the

UD axis. The distinction between the two views is only a factor of four

in the number of configurations for the different path-lengths. Finally,

we can view as a solution the configuration with on top 1 to 3 running from

right back to left back in stead of the other way around. Actually this

solution is not worse than the other, because, if we turn over a solved

Domino we go from one to the other. This view can also be expressed by saying

there are 8 solutions. I give results for all three cases. The numbers upto

(and including) path-length 2 have been checked by hand.

Some remarkable observations.

When we compare the tables for 1 solution and those for 4 solutions we see

that for short path-lengths the number of configurations is multiplied by

4. On the other hand, for long path-lengths the number of configurations

is equal! We can say that rotation of the Domino has only a short range

effect.

On the other hand, if we compare both with the 8-solutions tables we see that

the latter allows shorter solutions in general, so mirroring has a long

range effect.

Each of the 6 calculations on the Magic Domino took 2 to 2.5 hours on one

processor of an SGI 4D-420S. The program is completely memory bound (and

the cache does not help). It needs at least 31 MByte of core (and must be

resident) otherwise you will get no results at all in reasonable time. I

tried it on the 32 MByte FPS; while it will happily give results initially

at some stage it will not longer run. Not only that it will not walk either,

and also not crawl. It is just sitting there paging in and paging out (a

phenomenon known as page thrashing). I found that the program would get

less than 0.005 % of the CPU on an otherwise unloaded machine.

The program would enable me to write a 27901440 byte file that would assist

in an optimal solver for the Domino.

dik