Thread: "Parity in 12 Colors"

When I almost solved 12 Colors puzzle I found unexpected parity problem: on=
e 3C piece had wrong orientation (transposition) and two 4Cs were swapped. =
I've never seen anything like that before (close situation is on 4^3, but t=
here is transposition of 2Cs instead of flipping, so it's different). Close=
r inspection shown that the problem is in the number of 3Cs in one cell: it=
's odd (27). So 60-deg rotation had chance to flip orientation of odd numbe=
r of 3Cs. On other hand, this rotation gives even permutation of 2Cs (6+2+1=
cycles), and parity error can't be detected on the first stage.=20
This problem took about 500 extra twists, and puzzle was solved... in 419=
6 twists (no macros!) and 12h 00m 00s.345 (by timer) :) A little long - bu=
t I'm not sure in Undo/Redo operations and used to make back twist instead =
of Ctrl-Z.
My solving method is close to speedsolving 3^4 algorithm - it uses the fa=
ct that there are two cells with no common pieces. So for 8Color and 14Colo=
r this method doesn't work.

It looks like 1.0 version will be not very soon :( - mathematics in MHT i=
s very complicated (mixed Complex-Modular arithmetics) and some hidden bugs=
may remain hidden for a long time :(

Good luck!
Andrey

--001636c5a4af26e9c5049402c079
Content-Type: text/plain; charset=ISO-8859-1

Cool, nicely done :) I played around with the 12 colors puzzle some this
weekend too, but am only at the point of finishing up the 2C pieces, and my
timer is about to hit 2 hours (I currently have all 2Cs solved but two,
which are positioned but flipped - possibly a parity problem, not sure). I
bet my timer will read much higher than 12 hours if I ever go the entire way
- I spend too much time tripping out on the visualization :D

I found the way this puzzle is connected up beautiful, of course. One
property is that it is reminiscent of 2D Klein's Quartic puzzle, with "two
bottoms". Each cell has two cells that are not adjacent to it and
unaffected by its twists. And if you pick a cell and start solving outward
from there, as I was in my approach, you end up with two disjoint, unsolved
cells at the end. This is what happened with me for the 2C pieces.

Also, certain sets of 6 cells makes a ring, each ring containing two of
these groups of 3 "opposite" cells. Two disjoint rings can account for the
12 colors of the puzzle, slightly reminiscent of the {6}x{6} duoprism. It's
different though, because you can mentally select the two disjoint rings in
many different ways, whereas on the duoprism there is only one way to do so.

Roice

On Mon, Nov 1, 2010 at 12:51 PM, Andrey wrote:

> When I almost solved 12 Colors puzzle I found unexpected parity problem:
> one 3C piece had wrong orientation (transposition) and two 4Cs were swapped.
> I've never seen anything like that before (close situation is on 4^3, but
> there is transposition of 2Cs instead of flipping, so it's different).
> Closer inspection shown that the problem is in the number of 3Cs in one
> cell: it's odd (27). So 60-deg rotation had chance to flip orientation of
> odd number of 3Cs. On other hand, this rotation gives even permutation of
> 2Cs (6+2+1 cycles), and parity error can't be detected on the first stage.
> This problem took about 500 extra twists, and puzzle was solved... in 4196
> twists (no macros!) and 12h 00m 00s.345 (by timer) :) A little long - but
> I'm not sure in Undo/Redo operations and used to make back twist instead of
> Ctrl-Z.
> My solving method is close to speedsolving 3^4 algorithm - it uses the
> fact that there are two cells with no common pieces. So for 8Color and
> 14Color this method doesn't work.
>
> It looks like 1.0 version will be not very soon :( - mathematics in MHT is
> very complicated (mixed Complex-Modular arithmetics) and some hidden bugs
> may remain hidden for a long time :(
>
> Good luck!
> Andrey
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>

--001636c5a4af26e9c5049402c079
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Andrey,

Performing opposite twists instead of using undo shouldn't count against
move totals. In MC4D I detect those and turn them into undos for just
that reason. It may seem slightly odd that users can't undo such moves
but I don't know that anyone even noticed that. 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. :-) At
the very least I think that an option to do this sort of pruning should
be available when saving to a log file, or even as a post-process on
those log files.

Regarding your math, I was rather surprised to learn that you use
Complex arithmetic. I've never really understood why they are so useful
in a number of sciences. What do you use them for?

Thanks for another wonderful puzzle, and congratulations on another
amazing first solve,
-Melinda

On 11/1/2010 10:51 AM, Andrey wrote:
> When I almost solved 12 Colors puzzle I found unexpected parity problem: one 3C piece had wrong orientation (transposition) and two 4Cs were swapped. I've never seen anything like that before (close situation is on 4^3, but there is transposition of 2Cs instead of flipping, so it's different). Closer inspection shown that the problem is in the number of 3Cs in one cell: it's odd (27). So 60-deg rotation had chance to flip orientation of odd number of 3Cs. On other hand, this rotation gives even permutation of 2Cs (6+2+1 cycles), and parity error can't be detected on the first stage.
> This problem took about 500 extra twists, and puzzle was solved... in 4196 twists (no macros!) and 12h 00m 00s.345 (by timer) :) A little long - but I'm not sure in Undo/Redo operations and used to make back twist instead of Ctrl-Z.
> My solving method is close to speedsolving 3^4 algorithm - it uses the fact that there are two cells with no common pieces. So for 8Color and 14Color this method doesn't work.
>
> It looks like 1.0 version will be not very soon :( - mathematics in MHT is very complicated (mixed Complex-Modular arithmetics) and some hidden bugs may remain hidden for a long time :(

LS0tLS1CRUdJTiBQR1AgU0lHTkVEIE1FU1NBR0UtLS0tLQ0KSGFzaDogU0hBMQ0KDQpPbiBU
aHUsIDA0IE5vdiAyMDEwIDE0OjAxOjMwIC0wNzAwDQpNZWxpbmRhIEdyZWVuIDxtZWxpbmRh
QHN1cGVybGltaW5hbC5jb20+IHdyb3RlOg0KDQpbLi4uXSANCj4gSSdkIHJlYWxseQ0KPiBs
aWtlIHRvIHRha2UgdGhhdCB0byBpdCdzIHVsdGltYXRlIGV4dHJlbWUgYW5kIHBydW5lIG91
dCBhbnkgbW92ZQ0KPiBzZXF1ZW5jZXMgdGhhdCBsb29wIGJhY2sgdG8gYW55IHByZXZpb3Vz
IHN0YXRlLCByZWdhcmRsZXNzIG9mIHRoZQ0KPiBudW1iZXIgb2YgbW92ZXMgaW52b2x2ZWQu
IFdpdGggdGhlIGV4Y2VwdGlvbiBvZiByZXR1cm5pbmcgdG8gdGhlDQo+IHNvbHZlZCBzdGF0
ZSBvZiBjb3Vyc2UuIDotKQ0KDQpUaGlzIHdvdWxkIGJlIGdyZWF0IGFuZCBlYXN5IHRvIGRv
IGF0IHRoZSBleHBlbnNlIG9mIGEgYml0IG9mIG1lbW9yeS4NClB1enpsZSBzdGF0ZSBpcyBz
bWFsbCB0aG91Z2ggc28gc3RvcmluZyAxMCwwMDArIHB1enpsZSBzdGF0ZXMgaXMgbm8gYmln
DQpkZWFsIGZvciBtb2Rlcm4gY29tcHV0ZXJzLiAgV2UgY291bGQgc3R1ZmYgdGhlIHN0YXRl
cyBpbnRvIGEgdHJlZSBmb3INCmZhc3RlciBzZWFyY2hpbmcuDQoNCkkgdGhpbmsgaXQgaXMg
aW1wb3J0YW50IHRob3VnaCB0aGF0IHRoZSBzdGF0ZSBpcyB0cnVseSBpZGVudGljYWwNCnJh
dGhlciB0aGFuIGp1c3QgYXBwYXJlbnRseSBpZGVudGljYWwuICBUaGF0IGlzIC0tIHNodWZm
bGluZyBhcm91bmQNCnNvbWUgaWRlbnRpY2FsIDFjIHBpZWNlcyBzaG91bGQgY291bnQgYXMg
YSBkaWZmZXJlbnQgc3RhdGUuDQoNCkJyYW5kb24NCg0KLS0tLS1CRUdJTiBQR1AgU0lHTkFU
VVJFLS0tLS0NClZlcnNpb246IEdudVBHIHYyLjAuMTYgKEdOVS9MaW51eCkNCg0KaUVZRUFS
RUNBQVlGQWt6VElid0FDZ2tRcWFHUHpBc2w5NEpTQlFDZUpFelBCL1hKNzBHRURxQ0tsdUJ6
MGdjbg0KN1VJQW9JTllKenFxa2pLS3JONjAxckc5QjBwaktvdTINCj1jblBqDQotLS0tLUVO
RCBQR1AgU0lHTkFUVVJFLS0tLS0NCg==

--------------000606010506060003020602
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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 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

--------------000606010506060003020602
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit




http-equiv="Content-Type">

Sometimes I had a trouble with undo after removing of a pair of twists. Usu=
ally it happens when you make wrong operation sequence that is started with=
the removed twist, find that it was wrong sequence (in wrong direction, or=
on wrong faces), undo it (by the proper number of Ctrl-Z) and find yoursel=
f in couple of twists from where you started. And no way to return back. Th=
at was a reason why I removed this feature from MC7D. Another reason was wi=
th F1-F4 commands: you need extra marks to make start and end of the "setup=
" sequence unremovable. And I thought that it will be better solution to wr=
ite optimization command one day... but didn't do it in MC7D. May be MHT wi=
ll be more lucky.
I'm not sure that it will be easy and good idea to optimize movements of =
one cell: if user can't find two twist sequence that sets cell in the desir=
ed position and makes eigth twists instead - why should the program think f=
or him? But remove parts of sequence between identical positions is a good =
idea. We don't need to keep complete positions for it - it's enough to reme=
mber some 64-bit hash codes for positions (and probably check that position=
s with equal codes are identical indeed). And I agree that we don't need to=
check orientations of 1C stickers: if the program considers some position =
as solved one then it's identical to the starting position.

Andrey


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

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

On 11/4/2010 6:07 PM, Andrey wrote:
> Sometimes I had a trouble with undo after removing of a pair of twists. Usually it happens when you make wrong operation sequence that is started with the removed twist, find that it was wrong sequence (in wrong direction, or on wrong faces), undo it (by the proper number of Ctrl-Z) and find yourself in couple of twists from where you started. And no way to return back. That was a reason why I removed this feature from MC7D. Another reason was with F1-F4 commands: you need extra marks to make start and end of the "setup" sequence unremovable. And I thought that it will be better solution to write optimization command one day... but didn't do it in MC7D. May be MHT will be more lucky.
> I'm not sure that it will be easy and good idea to optimize movements of one cell: if user can't find two twist sequence that sets cell in the desired position and makes eigth twists instead - why should the program think for him? But remove parts of sequence between identical positions is a good idea. We don't need to keep complete positions for it - it's enough to remember some 64-bit hash codes for positions (and probably check that positions with equal codes are identical indeed). And I agree that we don't need to check orientations of 1C stickers: if the program considers some position as solved one then it's identical to the starting position.
>
> Andrey
>
>
> --- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
>> 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 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
>>
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>

LS0tLS1CRUdJTiBQR1AgU0lHTkVEIE1FU1NBR0UtLS0tLQ0KSGFzaDogU0hBMQ0KDQpPbiBU
aHUsIDA0IE5vdiAyMDEwIDE5OjIxOjE4IC0wNzAwDQpNZWxpbmRhIEdyZWVuIDxtZWxpbmRh
QHN1cGVybGltaW5hbC5jb20+IHdyb3RlOg0KDQo+IE1DNEQgY29udGFpbnMgYW4gb3B0aW1p
emF0aW9uIGZ1bmN0aW9uIHRoYXQgRG9uIHdyb3RlLCBidXQgSQ0KPiBjdXJyZW50bHkgZG9u
J3QgY29ubmVjdCBpdCB0byBhbnkgY29tbWFuZHMgb3IgY29udHJvbHMgYmVjYXVzZSBpdCBn
b3QNCj4gYnJva2VuIGF0IHNvbWUgcG9pbnQ7IHByb2JhYmx5IGJ5IG1lLg0KPiANCj4gWW91
IGFsc28ganVzdCBnYXZlIG1lIGEgZ3JlYXQgaWRlYSBmb3IgYSBtYXRoIHByb2JsZW0gZm9y
IHNvbWVvbmUgb24gDQo+IHRoaXMgbGlzdDogRGV2ZWxvcCBhIGZ1bmN0aW9uIHRoYXQgdGFr
ZXMgYSBwdXp6bGUgc3RhdGUgYW5kIHJldHVybnMgYSANCj4gaGFzaCBjb2RlIHRoYXQgd2ls
bCBiZSBpZGVudGljYWwgZm9yIGFsbCBwZXJtdXRhdGlvbnMgb2YgY29sb3IgY29kZXMNCj4g
YW5kIHdob2xlIG1vZGVsIHJvdGF0aW9ucywgYW5kIHdpbGwgYmUgZGlmZmVyZW50IGZyb20g
YWxsIG90aGVyDQo+IHN0YXRlcy4gVGhhdCBtYXkgYmUgZXh0cmVtZWx5IGRpZmZpY3VsdCBv
ciBldmVuIGltcG9zc2libGUsIGJ1dCBpZiBpdA0KPiBpcyBwb3NzaWJsZSB0aGVuIGl0IHdv
dWxkIGNsZWFybHkgYmUgdmVyeSB2YWx1YWJsZS4NCj4gDQo+IC1NZWxpbmRhDQoNCkhpIE1l
bGluZGEsIEkndmUgYWN0dWFsbHkgYmVlbiB3b3JraW5nIG9uIGFuIGFsZ29yaXRobSB0byBk
byBhIHN1YnNldA0Kb2YgdGhpcyAoanVzdCBvcmllbnRhdGlvbnMpIGZvciBhIGRpZmZlcmVu
dCBwdXp6bGUuICBNeSBnb2FsIGlzIHRvIGJlDQphYmxlIHRvIGNvdW50IHRoZSBudW1iZXIg
b2YgdW5pcXVlIHN0YXRlcyBvZiBvbmUgb2YgR2VsYXRpbmJyYWluJ3MNCnB1enpsZXMgKDMu
MTEuMSkuIFRoZXJlIGlzIGEgdmVyeSBkaXNjdXNzaW9uIGFib3V0IG91ciBhdHRlbXB0cyB0
bw0KY291bnQgdGhlIHN0YXRlcyBpbiB0aGlzIHRocmVhZC4NCg0KU3RhcnRpbmcgaGVyZToN
Cmh0dHA6Ly93d3cudHdpc3R5cHV6emxlcy5jb20vZm9ydW0vdmlld3RvcGljLnBocD9wPTIz
MjU2MyNwMjMyNTYzDQphbmQgY29udGludWluZyBoZXJlOg0KaHR0cDovL3d3dy50d2lzdHlw
dXp6bGVzLmNvbS9mb3J1bS92aWV3dG9waWMucGhwP3A9MjMyODA2I3AyMzI4MDYNCg0KU2lu
Y2Ugd2UndmUgcGxhY2VkIHRoZSBhcHByb3hpbWF0ZSBzdGF0ZXMgYXQgbGVzcyB0aGFuIDMg
KiAxMCBeIDkgbXkNCnBsYW4gaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGl0ZXJhdGUgdGhy
b3VnaCB0aGVtIGNvdW50aW5nIHRoZSB1bmlxdWUNCm9uZXMuICBUaGF0IHB1enpsZSBoYXMg
MiBkaWZmZXJlbnQgdHlwZXMgb2Ygc3BoZXJlIHBpZWNlcw0KDQpNeSAzRCBhbmQgNEQgZ2Vv
bWV0cnkgaXNuJ3Qgc28gZ3JlYXQgYW5kIEkgZ2V0IGh1bmcgdXAgb24NCmltcGxlbWVudGF0
aW9uIHNwZWNpZmljIGRldGFpbHMgYnV0IEknbGwgZG8gbXkgYmVzdCB0byBkZXNjcmliZSB0
aGUNCnJvdXRpbmUgYW55d2F5cy4gIEhvcGVmdWxseSBteSBkZXNjcmlwdGlvbiBpc24ndCB0
b28gcG9vciENCg0KSSBlbmNvZGUgdGhlIHN0YXRlIG9mIHRoZSBwdXp6bGUgaW50byBhIDQw
IGJpdHMgb2YgYSA2NCBiaXQgaW50ZWdlci4NClRoaXMgc3RhdGUgZW5jb2RpbmcgY2FuIGJl
IHRob3VnaHQgb2YgYXMgYSBoYXNoLiBSZWFsbHkgd2hhdCB3ZSBtZWFuIGJ5DQoiaGFzaCIg
YW55d2F5cyBpcyBzb21ldGhpbmcgdGhhdCBpcyBjb2xsaXNpb24tcmVzaXN0YW50LiAgTXkg
ZW5jb2RpbmcNCnN0cmF0ZWd5IGlzIHN1Y2ggdGhhdCBhIHN0YXRlIGludGVnZXIgKmlzKiB0
aGUgc3RhdGUgb2YgdGhlIHB1enpsZSBhbmQNCm5vIGluZm9ybWF0aW9uIGlzIGxvc3QuICBU
aHVzLCBvbmx5IGlkZW50aWNhbCBwdXp6bGVzIHdpbGwgcmVzdWx0IGluDQppZGVudGljYWwg
aGFzaGVzIC0tIGluc3VyaW5nIGNvbGxpc2lvbiByZXNpc3RhbmNlLg0KDQpXaGVuIEknbSBl
bmNvZGluZyB0aGUgaGFzaCwgZWFjaCBwaWVjZSBpcyBtYXBwZWQgdG8gYSA1LWJpdCBudW1i
ZXINCmJhc2VkIG9uIHRoZSBhcHBhcmVudCB0eXBlIG9mIHBpZWNlIGFuZCBvcmllbnRhdGlv
biBvZiB0aGUgcGllY2UuICBGb3INCkdlbGF0aW5icmFpbidzIDMuMTEuMSBwdXp6bGUgdGhp
cyBpcyByZWFsbHkganVzdCB0aGUgb3JpZW50YXRpb24gb2YgdGhlDQpwaWVjZSBzaW5jZSB0
aGV5IGFsbCBsb29rIGxpa2UgdGhlIHNhbWUgdHlwZS4gIEkgdGhlbiBwYWNrIHRoZSBwaWVj
ZXMNCnRvZ2V0aGVyOg0KDQo8NSBiaXRzIGZvciBwaWVjZSAxPjw1IGJpdHMgZm9yIHBpZWNl
IDI+Wy4uLi5dPDUgYml0cyBmb3IgcGllY2UgOD4NCg0KVGhlIHBpZWNlcyBudW1iZXJzIGFy
ZSBmaXhlZCByZWxhdGl2ZSB0byB0aGUgdmlldy4gIFJlLW9yaWVudGluZyB0aGUNCnB1enps
ZSAibW92ZXMiIGRpZmZlcmVudCBwaWVjZXMgaW50byB0aGUgMSAuLi4gOCBwb3NpdGlvbnMu
DQoNClRoZSBvbmx5IGlubm92YXRpdmUgdGhpbmcgYWJvdXQgaG93IEkgZW5jb2RlIHRoZSBo
YXNoZXMgaXMgdGhhdCBJIGRvIGl0DQppbiBhIHdheSB0aGF0IG1pbmltaXplcyB0aGUgaGFz
aCB2YWx1ZS4gIFRoYXQgaXMsIGZvciBhIDNEIGN1YmUsIHRoZXJlDQphcmUgMjQgcmVkdW5k
YW50IG9yaWVudGF0aW9ucyBzbyB0aGVyZSBhcmUgMjQgaGFzaCB2YWx1ZXMgcG9zc2libGUg
d2l0aA0KYSBuYWl2ZSBlbmNvZGluZyBzdHJhdGVneS4gIFRoZSBzaW1wbGUgYWxnb3JpdGht
IGNhbiBqdXN0IHRyeSBhbGwgMjQNCm9yaWVudGF0aW9ucyBhbmQgY2hvb3NlIHRoZSBvbmUg
d2l0aCB0aGUgc21hbGxlc3QgaGFzaCB2YWx1ZS4gIFRoaXMgaXMNCnByZXR0eSB1bi1vcHRp
bWFsIGJ1dCBpdCdzIHN0aWxsIE8oMSkuDQoNClRvIHRyeSB0byBmaW5kIHRoZSBzbWFsbGVz
dCBoYXNoIHZhbHVlIGZhc3RlciB0aGFuIGJydXRlLWZvcmNlDQpzaG91bGRuJ3QgYmUgdGVy
cmlibHkgZGlmZmljdWx0IGVpdGhlci4gIElmIHlvdSBoYXNoIGlzIGp1c3QNCjxNU0IgLi4u
IGJpdCA5IC4uLiBiaXQgNSAuLi4gTFNCPiB0aGVuIHlvdSBzaG91bGQgYmUgYWJsZSB0byBv
cHRpbWl6ZQ0Kb25lIHBpZWNlIGF0IGEgdGltZS4NCg0KRmlyc3Qgc2VsZWN0IGFsbCB0aGUg
cGllY2VzIHRoYXQgdGhyb3VnaCByZS1vcmllbnRhdGlvbiBhcmUgdGllZCBmb3IgdGhlDQps
b3dlc3QgdmFsdWUgaW4gdGhlIGZpcnN0IHBvc2l0aW9uLiAgVGhlbiBvZiB0aG9zZSB0aWVz
LCBzZWxlY3Qgb25seQ0KdGhlIHN0YXRlcyB0aGF0IHRoZSBzZWNvbmQgcGllY2UgaXMgYWxz
byB0aWVkLCBhbmQgc28gb24gdW50aWwgdGhlcmUNCmlzIG9ubHkgb25lIGJyYW5jaCBsZWZ0
IGluIHRoZSB0cmVlLiBBIGNhcmVmdWwgaW1wbGVtZW50YXRpb24gb2YgdGhpcw0KaXRlcmF0
aXZlIGltcHJvdmVtZW50IGNvdWxkIHN0YXJ0IHRvIG1hdHRlciBmb3IgaHVnZSBwdXp6bGVz
Lg0KDQpFeHRlbmRpbmcgdG8gYWxsIHB1enpsZXMgaW4gYW55IGRpbWVuc2lvbiBzZWVtcyBu
b24tdHJpdmlhbCBidXQgSSB0aGluaw0KZXh0ZW5kaW5nIHRvIE5eNCBzaG91bGQgYmUgc3Ry
YWlnaHQtZm9yd2FyZC4gIEEgY3RybCtjbGljayBpbiBNQzREIGlzDQpqdXN0IGEgcmUtb3Jp
ZW50YXRpb24uICBJIGd1ZXNzIHRoYXQgbWVhbnMgdGhlcmUgc2hvdWxkIGJlIDggKiAyNA0K
b3JpZW50YXRpb25zPw0KDQpJIHRoaW5rIHRoaXMgc3RyYXRlZ3kgd2lsbCBoYW5kbGUgdGhl
IDReNCBncmFjZWZ1bGx5IGV2ZW4gdGhvdWdoIHlvdQ0KY2FuIHNvbHZlIGRpZmZlcmVudCBj
b2xvcnMgaW50byB0aGUgcG9zaXRpb25zIGJlY2F1c2UgdGhlIGhhc2ggaXMNCmNvbnN0cnVj
dGlvbiBmcm9tIHdoYXQgdGhlIHB1enpsZSAqbG9va3MqIGxpa2UgZnJvbSBzb21lIGZpeGVk
IHZpZXcuDQpJdCBzaG91bGQgYWxzbyBoYW5kbGUgaWRlbnRpY2FsIHBpZWNlcyBmb3IgbWUg
c2FtZSByZWFzb24gLS0gdGhleSBhcmUNCmVuY29kZWQgaW50byBpZGVudGljYWwgYml0IHN0
cmluZ3MuDQoNClNvIHdoaWxlIHRoaXMgYWxnb3JpdGhtIHdvcmtzIHdlbGwgZm9yIEdlbGF0
aW5icmFpbidzIDMuMTEuMSwgdGhpcw0KZW1haWwgZG9lc24ndCBleGFjdGx5IHNob3cgdGhh
dCBpdCBhY3R1YWxseSBleHRlbmRzIHRvIG90aGVyDQpwdXp6bGUgYW5kLCBjZXJ0YWlubHkg
ZG9lc24ndCBzaG93IHRoYXQgaXQgaXMgZmFzdC9lZmZpY2llbnQuDQoNCkknbSBwcmV0dHkg
c3VyZSB0aGF0IGEgZ2VuZXJhbCBhbGdvcml0aG0gZm9yIGVuY29kaW5nIGRpZmZlcmVudCBz
dGF0ZXMNCm9mIGEgcHV6emxlIHRvIHRoZSBzYW1lIGhhc2ggY29kZXMgKmRvZXMgZXhpc3Qq
IHRob3VnaC4NCg0KQnJhbmRvbg0KDQotLS0tLUJFR0lOIFBHUCBTSUdOQVRVUkUtLS0tLQ0K
VmVyc2lvbjogR251UEcgdjIuMC4xNiAoR05VL0xpbnV4KQ0KDQppRVlFQVJFQ0FBWUZBa3pU
ZlBjQUNna1FxYUdQekFzbDk0Snh5Z0NlT0pveEsvNEtEcnZPRytzVGVZRWFjbGVMDQpabWdB
bjAwN0xoMDZaRHQvc2F6U3JYaklxTEd5dHRKSA0KPWFrRXQNCi0tLS0tRU5EIFBHUCBTSUdO
QVRVUkUtLS0tLQ0K

Melinda,
there is no problem in this hash function.
Suppose that you know the symmetric group of your puzzle body. It my be t=
esseract (192 states), 100x100 duoprism (20000 states), 3^7 (64*5040=3D3225=
60 states) and so on. You take the state of the puzzle in the form of array=
of sticker colors. Then perform the loop for all orientations of the puzzl=
e:
- build array of sticker colors for this orientation;
- renumerate colors so that first color in array has number 0, second dif=
ferent of it has numer 1 and so on...
- select the minimal colors array (in lexicographis order) for all states=
.
This array will be the "canonical form" of the puzzle state. For the hash=
value just code it in the best numeric system (like 3 bits per color for 3=
^4). Of course, it will be longer then the shortest possible representation=
, but not much.

Andrey

--- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
>
> MC4D contains an optimization function that Don wrote, but I currently=20
> don't connect it to any commands or controls because it got broken at=20
> some point; probably by me.
>=20
> You also just gave me a great idea for a math problem for someone on=20
> this list: Develop a function that takes a puzzle state and returns a=20
> hash code that will be identical for all permutations of color codes and=
=20
> whole model rotations, and will be different from all other states. That=
=20
> may be extremely difficult or even impossible, but if it is possible=20
> then it would clearly be very valuable.
>=20
> -Melinda
>=20
> On 11/4/2010 6:07 PM, Andrey wrote:
> > Sometimes I had a trouble with undo after removing of a pair of twists.=
Usually it happens when you make wrong operation sequence that is started =
with the removed twist, find that it was wrong sequence (in wrong direction=
, or on wrong faces), undo it (by the proper number of Ctrl-Z) and find you=
rself in couple of twists from where you started. And no way to return back=
. That was a reason why I removed this feature from MC7D. Another reason wa=
s with F1-F4 commands: you need extra marks to make start and end of the "s=
etup" sequence unremovable. And I thought that it will be better solution t=
o write optimization command one day... but didn't do it in MC7D. May be MH=
T will be more lucky.
> > I'm not sure that it will be easy and good idea to optimize movement=
s of one cell: if user can't find two twist sequence that sets cell in the =
desired position and makes eigth twists instead - why should the program th=
ink for him? But remove parts of sequence between identical positions is a =
good idea. We don't need to keep complete positions for it - it's enough to=
remember some 64-bit hash codes for positions (and probably check that pos=
itions with equal codes are identical indeed). And I agree that we don't ne=
ed to check orientations of 1C stickers: if the program considers some posi=
tion as solved one then it's identical to the starting position.
> >
> > Andrey
> >
> >
> > --- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
> >> 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 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 b=
ig
> >>> 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 4=
D
> >> rotations or both. For example, if you got to within a single 90 degre=
e
> >> 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 pruni=
ng
> >> should count towards shortest records.
> >>
> >> -Melinda
> >>
> >
> >
> >
> > ------------------------------------
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
>

--001636c599154ecfa404945b0dac
Content-Type: text/plain; charset=ISO-8859-1

On Thu, Nov 4, 2010 at 4:01 PM, Melinda Green wrote:

>
> Regarding your math, I was rather surprised to learn that you use
> Complex arithmetic. I've never really understood why they are so useful
> in a number of sciences. What do you use them for?
>

I had hoped to see more on this, because it is thoroughly magical how
complex arithmetic is behind all this geometry (and how it fits into other
areas of science). I've mentioned the first 6 chapters of Visual Complex
Analysis. The book is about complex numbers, yet those chapters are
simultaneously an introduction to non-Euclidean geometry, which shows how
intertwined they are.

Complex arithmetic also made MagicTile possible, and it uses the same kinds
of calculations as in MHT633 (described below) to do its twisting in all
three of the geometries. Ironically, complex numbers simplify the scenarios
immensely. Though I don't have experience applying them one dimension up, I
have the impression things are similar. After all, you can take an H2 slice
of H3, an R2 slice of R3, or an S2 slice of S3, and the 2D behaviors are
connected to the 3D behaviors.

The core of things are the "linear fractional transformations" or "Mobius
Transformations
". A Mobius
Transformation
is a simple looking function of a complex variable z.

f(z) = (az+b)/(cz+d)

The a,b,c,d coefficients are complex numbers as well, and you get
differently behaving functions depending on how they are chosen. (To be
complete for those who might not know, a complex number has two components
and so can be interpreted as a point in a plane, so these functions
transform point locations in a plane.)

To get a sense of how they can transform points in a plane and some cool
geometric insight, watch this short YouTube
video.
In the video, you see how the functions can represent the "isometry"
movements (distance preserving) of a stereographically projected sphere, but
they can represent more. Selecting certain coefficients allows you to
describe all the movements of H2 in the Poincare disk model as well! Don
used these functions for his tessellation applet. In fact, the simple
formula above can be used to describe isometries in all three standard
geometries (stereographically projected S2, R2, and the Poincare disk model
of H2), which is crazy to me.

As if that's not enough, Tristan Needham writes in Visual Complex Analysis:


> ...we explain how we may set up a one-to-one correspondence between these
> light rays and complex numbers. Thus each Lorentz transformation of
> space-time induces a definite mapping of the complex plane. What kinds of
> complex mappings do we obtain in this way? The miraculous answer turns out
> to be this: The complex mappings that correspond to the Lorentz
> transformations are the Mobius transformations! Conversely, every Mobius
> transformation of *C* yields a unique Lorentz transformation of
> space-time. Even among professional physicists, this "miracle" is not as
> well known as it should be.


So there you have it, these transforms are also intimately related to
special relativity!

If anyone wants to dig deeper, all the details of the possibilities for
the a,b,c,d coefficients and the classes of behavior they lead to are in
Visual Complex Analysis. It's safe to say the Mobius Transformations are
all over the place in the models of H3 geometry (I know Andrey used them in
his implementation, though he could provide more insight about what it takes
to fully jump to the 3D geometry from 2D).

All the best,
Roice

--001636c599154ecfa404945b0dac
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable