Message #1249

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Parity in 12 Colors
Date: Thu, 04 Nov 2010 14:33:22 -0700

On 11/4/2010 2:12 PM, Brandon Enright wrote:
> —–BEGIN PGP SIGNED MESSAGE—–
> Hash: SHA1
>
> On Thu, 04 Nov 2010 14:01:30 -0700
> Melinda Green<melinda@superliminal.com> wrote:
>
> […]
>> I’d really
>> like to take that to it’s ultimate extreme and prune out any move
>> sequences that loop back to any previous state, regardless of the
>> number of moves involved. With the exception of returning to the
>> solved state of course. :-)
> This would be great and easy to do at the expense of a bit of memory.
> Puzzle state is small though so storing 10,000+ puzzle states is no big
> deal for modern computers. We could stuff the states into a tree for
> faster searching.
>
> I think it is important though that the state is truly identical
> rather than just apparently identical. That is – shuffling around
> some identical 1c pieces should count as a different state.

Well to do that right does not seem easy to me, at least not with the
definition of puzzle state that I’m thinking about. I feel that the
ideal implementation wouldn’t distinguish between states that are
identical except for color swapping, or state changes that amount to 4D
rotations or both. For example, if you got to within a single 90 degree
twist of being fully solved but then took a detour that eventually
brought you to another state that has a different face that’s also one
90 degree twist from being solved, I would want to "subtract" all the
moves in that detour. The trouble is that I’m not at all sure how to
efficiently detect those sorts of cases. At the very least I’d love to
turn any consecutive sequence of twists of a single face into a single
twist, whenever possible. For example, four identical 90 degree twists
should simply vanish from the history, or at least there should be an
option to have that happen, and solutions that used that sort of pruning
should count towards shortest records.

-Melinda