Date: Thu, 02 May 96 13:27:30 -0400
~~~ From: Dale Newfield <din5w@virginia.edu >
~~~ Subject: TripleCross by Binary Arts

I've been investigating for month or so, now the size and shape of the
group represented by this puzzle...There are 18! positions, of course,
although I have yet to do any meaningful investigation in regards to what
interesting sub-groups exist, or even how many orbits there are in that
group, as 18! is a very large number (and I've been doing all of this
work with home-spun tools...I really need to get ahold of GAP and see
what it can do :-). Instead I've been doing most of my investigations
with respect to a fairly arbitrary subgroup--that of distinguishable
positions (On the actual puzzle there are 9 indestinguishable blank
tiles, and 3 indestinguishable tiles that each contain one orange dot).
In this group there are just under 3 billion possible positions:
18!/(9!*3!). One of the things that I am currently trying to do is,
using a breadth first search, simply expand the entire graph from start,
to see how many of these positions are in the same orbit as start, and
thus to find out experimentally how many orbits there are. I have not
really begun the analytical process of looking into these groups yet. I
can encode a position (theoretically ~31.5 bits of information) into a 32
bit unsigned long, along with a 2 bit number representing which direction
to go to get to start. I've gone through many iterations, but now I
believe that I have built a system in which any given position in the
breadth first search queue takes up 4.5 bytes (on average), and in the
hashtable that stores the unique positions that popped out of the queue,
takes up about the same size. This means that the entire graph can be
laid out in less than 13 gig of space. This means that the problem is
solvable with enough money thrown at it, but is just beyond most of our
reaches right now (I have this running on a machine w 512M of memory,
and 1.2 Gig of swap...(Once the job runs into swap it crawls)...so if
there are 12 orbits I should find out before this run is through.)

As well, I have built a java applet that allows one to play with the
device. My goal was to include a "Solve" button that would show a person
a path toward a solved state. Actually my goal was to be able to give up
and "reset" the physical toy back into a start state if I so desired so
that I can play with it without fear... although the ability to put in
macros in the applet was quite useful...

Binary Arts has a site: http://www.puzzles.com/