# 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—–