Message #1252

From: Brandon Enright <bmenrigh@ucsd.edu>
Subject: Re: [MC4D] Parity in 12 Colors
Date: Fri, 05 Nov 2010 03:41:31 +0000

—–BEGIN PGP SIGNED MESSAGE—–
Hash: SHA1

On Thu, 04 Nov 2010 19:21:18 -0700
Melinda Green <melinda@superliminal.com> wrote:

> MC4D contains an optimization function that Don wrote, but I
> currently don’t connect it to any commands or controls because it got
> broken at some point; probably by me.
>
> You also just gave me a great idea for a math problem for someone on
> this list: Develop a function that takes a puzzle state and returns a
> hash code that will be identical for all permutations of color codes
> and whole model rotations, and will be different from all other
> states. That may be extremely difficult or even impossible, but if it
> is possible then it would clearly be very valuable.
>
> -Melinda

Hi Melinda, I’ve actually been working on an algorithm to do a subset
of this (just orientations) for a different puzzle. My goal is to be
able to count the number of unique states of one of Gelatinbrain’s
puzzles (3.11.1). There is a very discussion about our attempts to
count the states in this thread.

Starting here:
http://www.twistypuzzles.com/forum/viewtopic.php?p=232563#p232563
and continuing here:
http://www.twistypuzzles.com/forum/viewtopic.php?p=232806#p232806

Since we’ve placed the approximate states at less than 3 * 10 ^ 9 my
plan is to write a program to iterate through them counting the unique
ones. That puzzle has 2 different types of sphere pieces

My 3D and 4D geometry isn’t so great and I get hung up on
implementation specific details but I’ll do my best to describe the
routine anyways. Hopefully my description isn’t too poor!

I encode the state of the puzzle into a 40 bits of a 64 bit integer.
This state encoding can be thought of as a hash. Really what we mean by
"hash" anyways is something that is collision-resistant. My encoding
strategy is such that a state integer *is* the state of the puzzle and
no information is lost. Thus, only identical puzzles will result in
identical hashes – insuring collision resistance.

When I’m encoding the hash, each piece is mapped to a 5-bit number
based on the apparent type of piece and orientation of the piece. For
Gelatinbrain’s 3.11.1 puzzle this is really just the orientation of the
piece since they all look like the same type. I then pack the pieces
together:

<5 bits for piece 1><5 bits for piece 2>[….]<5 bits for piece 8>

The pieces numbers are fixed relative to the view. Re-orienting the
puzzle "moves" different pieces into the 1 … 8 positions.

The only innovative thing about how I encode the hashes is that I do it
in a way that minimizes the hash value. That is, for a 3D cube, there
are 24 redundant orientations so there are 24 hash values possible with
a naive encoding strategy. The simple algorithm can just try all 24
orientations and choose the one with the smallest hash value. This is
pretty un-optimal but it’s still O(1).

To try to find the smallest hash value faster than brute-force
shouldn’t be terribly difficult either. If you hash is just
<MSB … bit 9 … bit 5 … LSB> then you should be able to optimize
one piece at a time.

First select all the pieces that through re-orientation are tied for the
lowest value in the first position. Then of those ties, select only
the states that the second piece is also tied, and so on until there
is only one branch left in the tree. A careful implementation of this
iterative improvement could start to matter for huge puzzles.

Extending to all puzzles in any dimension seems non-trivial but I think
extending to N^4 should be straight-forward. A ctrl+click in MC4D is
just a re-orientation. I guess that means there should be 8 * 24
orientations?

I think this strategy will handle the 4^4 gracefully even though you
can solve different colors into the positions because the hash is
construction from what the puzzle *looks* like from some fixed view.
It should also handle identical pieces for me same reason – they are
encoded into identical bit strings.

So while this algorithm works well for Gelatinbrain’s 3.11.1, this
email doesn’t exactly show that it actually extends to other
puzzle and, certainly doesn’t show that it is fast/efficient.

I’m pretty sure that a general algorithm for encoding different states
of a puzzle to the same hash codes *does exist* though.

Brandon

—–BEGIN PGP SIGNATURE—–
Version: GnuPG v2.0.16 (GNU/Linux)

iEYEARECAAYFAkzTfPcACgkQqaGPzAsl94JxygCeOJoxK/4KDrvOG+sTeYEacleL
ZmgAn007Lh06ZDt/sazSrXjIqLGyttJH
=akEt
—–END PGP SIGNATURE—–