Shareware Overload/ShartewareOverload.cdr/games/icosahed.zip/DEWDNEY.DOC

Text File | 1980-01-01 | 16KB | 289 lines

                                                 October,15, 1985

A. K. Dewdney                                   Robert T. Carlson
Department of Computer Science                  18480 Decatur Dr.
University of Western Ontario                   Monte Sereno, California, USA 9503
London, Ontario, Canada 96N5B7                  [408]-395-2134


Re: Carlson's Icosahedron, a Rubiks cube type puzzle  that contains
   Engel's Enigma, Hofstader's Impossiball and Alexander's Star


Dear Mr. Dewdney

As I discussed with you by phone today  I have invented  a Rubiks cube
type puzzle based on the icosahedron (the regular polyhedron built of 20
equilateral triangles). Interestingly, Engels Enigma, the puzzle you mentioned
in your October Scientific American  collumn turns out to be a subset of
my puzzle (for the case where the Engels circles are divided into five sectors).

The iocosahedron has 20 triangular stones (equilataeral triangle faces)
and 30 bones (edges of the icosahedron). There are 12 Enigma like circles
each containing 5 bones and 5 stones. The total number of adjacent pairs
of circles is 12*5/2=30 so you can think of the Icosahedron as containing
30 Engels Enigmas.

The total number of combinations of various cube type puzzles is as follows

puzzle         major pieces         minor pieces         total combination

Icosahedron    20!*3^20= 2.828e27      30!*2^30= 1.424e41     10^  68.6
Alexander                1e0           30!*2^30= 1.424e41     10^  41.2
Impossiball    20!*3^20= 2.828e27                1e0          10^  27.5
Enigma-6       10!*3^10= 7.143e10      11!*2^11= 4.087e10     10^  21.5
Rubik           8!*3^8 = 8.8180e7      12!*2^12= 9.810e11     10^  19.9
Enigma-5        8!*3^8 = 8.8180e7       9!*2^9 = 9.2897e7     10^  15.9
Pyramid                  1e0            6!*2^6 = 2.304e4      10^  4.4

A parenthetical remark
These numbers are very large. 10^68 for example is greater than the number
of seconds since the big bang, as well as greater than the number of cubic
miles in the observable universe. If those numbers give you a headache
take heart (or is it despair) in the fact that 10^63 is size of the primes
used in typical public key encryption systems, 10^ 126 of course the size of
of a product of such primes. And speaking of primes all these numbers are
dwarfed by the large merseinne primes which exceed 2^32,768. And speaking
of encryption schemes icosahedron  scrambling might make a good trap door
function, but I dont see right now how to create a public encoding method
as well as public keys, perhaps someone else does.


Relations between the Icosahedron and the Enigmas
Enigma-5 solutions should give Icosahedron solutions since they can be used
to solve every pair of adjacent circles in the Icosahedron.(In turn of
course the Icosahedron can model Enigma-5 by suppressing all but two adjacent
circles). Enigma solutions for adjacent circles would work perfectly given
two conditions: the adjacent circles contain only pieces that originated
there; the sum of all the pieces twist adds to zero, where twist is
the total angle a piece must twist through to return home in its correct
position.







It is easy to show that Total Twist of any cube type puzzle
remains constant and  equal to zero since  whenever a face is rotated
one click, N major (and minor) pieces have been given 360/N degrees twist
and N*360/N = 0 mod 360, so that total twist is unchanged mod 360.

Since every algorithm is  composed of sequences of clicks
any adjacent pair of the Icosahedron must begin with total twist=0
if you expect an Engels algorithm to restore them to perfect
original condition with 0 twist.

How difficult is the Icosahedron compared with the Enigma.
To measure the relative complexity of cube type puzzles is a thorny
question, since one has  many measures to choose from: initial resistance
to insight; or speed attainable by adept solvers; or ratio of time to
solve over number of pieces .  The measure I prefer however is the
how deep can you go into the forest before you start coming out measure,
the minimum number of moves M needed to create all possible  combinations
which is computed as follows: take the number of possible moves at any
time P then  P^M = total combinations

puzzle         possible moves      minmum needed         total combinations

Icosahedron     12*4   = 48                    ^ 41      =    10^  68.6
Alexander       12*4   = 48                    ^ 24      =    10^  41.2
Impossiball     12*4   = 48                    ^ 16      =    10^  27.5
Enigma-6         2*5   = 10                    ^ 21      =    10^  21.5
Rubik            3*6   = 18                    ^ 16      =    10^  19.9
Enigma-5         2*4   = 8                     ^ 18      =    10^  15.9
Pyramid          4*2   = 8                     ^ 5       =    10^  4.4

Note Enigma-6 gets a higher number than the Impossiball or Rubik because
its possible moves are small.

The optimal solving algorithms would give solutions lengths around these
minimums. A measure of computational difficulty would be current best
average solution length / minimum length. In the case of Rubiks cube this number
is about 150/15= 10. I dont have best average solution lengths for the
Icosahedron or the Enigma, since I dont have algoritrhms for them, although
Doug Engels tells me that in the next issues of  American Mathematical
Monthly Jack Eidswick of the University of Nebraska has an article
giving a general, but inefficient  solution for all cube type puzzles.

Of course Impossiball algorithms leaving edges fixed combined with Alexanders
star algorithms leaving triangles fixed would consitute solutions
for the Icosahedron. Probably the most elegant solutions will be built
this way but I havent seen them yet.

(The Star and Impossiball puzzles can be thought of as the Icosahderon minus
stones-triangles and bones-edges respectively)















puzzle         major    minor    face           lcm

Icosahedron     3        2        5              30
Alexander                2        5              10
Impossiball     3                 5              15
Enigma-6        3        2        6              6
Rubik           3        2        4              12
Enigma-5        3        2        5              30
Pyramid         3                 3              1

Note the high score  of Enigma-5, and the low score of Enigma-6.

Heuristically  we expect transformations which move major (minor)
pieces  but leave minor (major) pieces alone to have period
0 mod lcm(  2 (3) , face symmetry number) since they are acting as
the identity transformation on the unmoved pieces, and an identity
on piece n with symmetry n should have some number k*n clicks.

Ad hoc solving routines use utility transformations that act as
identity on both major and minor pieces  so have period length
0 mod lcm(3,2,face symmetry).  The length of these utility routines
limits the speed of adept solvers, which  is why I am suggesting
this number as a measure of difficulty.


According to Doug Engels Enigma-N can be built for any N by moving the
centers of the circles closer together and taking deeper cuts out of the
circles to make the stones and bones. We would  expect the solving difficulty
to increase with the number of pieces of course but using  the
symmetry lcm as a  guide  we should  expect special difficulty
when N is relatively prime to 2,3, and expect special ease
when N has factors of 2 and 3, exclusively.



Features of my Icosahedron manipulator program:

Although I invented my Icosahedron puzzle shortly after Rubiks cube
came out I could never make a very good mechanical model since it
required a lot of spherical machining and close tolerances. Realising
I probably would never have the 10-20,000  dollars necessary for such
a computer controlled machining job I decided to make Carlson's Magic
Icosahedron work on computer. So I spent a month locked in my room
with a PC and an IBM Basic manual  and wrote this program.

As you look through the code you will see I started with a sphere in
3-space, found the vertexes of the icosahedron on the sphere, regarded
their 3-tuples as vectors and defined a batch of vector addition and
multiplication functions. Then for each triangle  I made a local
coordinate system expressing each point within the triangle as a vector
sum of the 3 vertices around it. In this  system I scribed into
the triangle the cuts along which the  aggregates of 5 stone and 5
bones would slide.








I were to do it again I  might  take the six vectors
for the six axes of symmetry and  make polar coordinates about them
to scribe on the sphere in those systems, but the advantage of using
the local triangular coordinate systems is that the code as it is now
will generate any puzzle based on any regular polyhedron with equilateral
triangle faces, including the tetrahedron (Pyramid puzzle),and  Octahedron
(which is equivalent to Rubik's cube).

At any rate once the scribing  was done I connected all the centers
of all adjacent triangles which drew a dodesahedron over the
icosahedron, which placed a pentagon around every  vertex.

These pentagons were then colored one of six colors, opposite
penatagons having the same color. This results in 20 distinct triangles
but gives 10 pairs of identical bones, so I suppose the puzzle could be
made harder by distinguishing all bones but to see it on screen
you'd need a 16 color display as well as 640 x 200 resolultion
which exceeded the capacity of my machines  at the time, so I blew it off.

Then the whole mess had to be projected on screen.
I wanted to see the entire Icosahedron at once so I chose
a polar projection, that is I projected onto the screen as if I had
placed a sheet of frosted glass on the north pole of the Icosahedron
and a candle at the south pole and was casting shadows onto the glass.
This keeps the northern hemisphere undistorted but smears the southern
hemisphere all over the screen, espescially the south pole  which
appears as a white ring around the outside of the enclosed pictures.

A technical point:
Colors of the parts of the bones and stones are stored in an array
T(12,12,12)  where t(a,b,c) is the a corner of the abc stone where
a,b,c are the vertexes making the  abc triangle. Element t(c,b,a) is
part of the Mirror array holding  latest information while the t(a,b,c)
are being changed under face rotation. Other  elements hold screen
display information: screen addresses of points to be painted using the
PAINT command in  Advanced  Basic.

What its like to use:
Each function key  rotates a face. Shift, Ctrl, Alt simultaneously
with the function key gives -1,2,-2 clicks respectively.

Coming soon:
An inversion function  that switches north and south poles;
Algorithm function that recieves moves generated by your algorithm;
Save current scramble  function, so you can pick up where you left
       off later on
Suppress stones or bones function so you can emulate
              Alexanders star or Hofstaders uniball respectively.
FastmoveN which displays results ater N moves of your choice
Reverse which reverses last 16 moves
and others!




















What is available from me:

A  640 x 200 8 color version  for 80186 machines in GWBasic
A  320 x 200  4 color version for IBM PCs
A 640 x 200 16 color version for IBM AT an XT with
enhanced color graphics card and vdi graphics language (soon)

I am selling unprotected clear code copies for $10.00 each,
             a terrific bargain.


Robert Carlson
319 Lunada Ct.
Los Altos, California,94022
[415]-941-0348

              Happy Solving!




                                  Robert    Carlson