Message #487

From: Roice Nelson <roice3@gmail.com>
Subject: Re: [MC4D] Introduction to the 4D_Cubing Group
Date: Fri, 02 May 2008 00:48:14 -0500

Hi David,

I’m afraid I’m not going to be as much help as I would like since I haven’t
been through the process of trying to write a solver yet. But I had a few
short thoughts on how one would do it on the way home from work today.

A dumb brute force solver could theoretically verify any given state as
valid or not, but that is intractable because the state spaces are so
unbelievable huge.

That means the solver must be smart, and to write such a program one would
have to code a toolkit of sequences to place pieces and the knowledge of how
to apply the sequences in various situations. If I were attacking this
then, I would literally try to code in the sequences I use to solve MC4D.
Until the toolkit is verified to be complete, the solver will not be good at
being sure if a puzzle state is unsolvable (maybe it was, but maybe the
toolkit was just incomplete or maybe the code wasn’t smart enough to handle
troublesome situation like parities in the 4^4). But it still could be
useful to verify solvable puzzle states, and if you had an enumeration of
all the sets of groups that needed to be checked and it could solve all of
them, you would know it was a complete solver (this must be what Keane and
Kamack did). Only at that point then could the program confidently be used
to verify unsolvable states.

In fact, even though I have solved MC4D a number of times now, this forces
me to admit that my personal toolkit is not proven complete in the
mathematical sense. All I can say for sure right now is that it is highly
effective since I have never rigorously verified my sequences can solve all
the subgroups.

The enumeration proof could be done without a computer too I bet, and I
figure someone who has become intimate enough with the mathematics to prove
the number of permutation states by coming up with a provably complete set
of sequences may not need a computer solver to investigate certain puzzle
states (I’m sure this person could have reached my checkerboard conclusions
in this way, and would have been more sure of the answers!). Anyway, hope
this was helpful, even if just a little…

Take Care,

Roice

On Wed, Apr 30, 2008 at 6:11 PM, David Smith <djs314djs314@yahoo.com> wrote:

> Hi Roice,
>
> Thank you very much for pointing me to that website! I had
> not seen that website before. As for my program, it is not
> going well; I have very limited coding experience. For one
> thing, the program works but the data it generates is
> incorrect. It is overly complicated. It is currently specific to the
> 4^4 cube. And when I run it and generate the data, it takes GAP over 5
> hours to process the data! In short, I need to find a way
> to either write a program that tests whether a specific
> position is possible, for a 4D (preferably, N-D) cube of any size,
> or do the same with an existing program. I have tried to analyze
> the code for Don’s N-dimensional Rubik’s Cube solver, but
> it is beyond me.
>
> I would be extremely grateful if you or any others in
> this group could help me understand the algorithms involved
> when testing whether a position is possible for higher-dimensional
> cubes. The reason I can’t simply use Don’s program is that
> I need to study larger cubes of 4 (preferably any) dimensions.
> I definitely need to study 4^4, and perhaps 5^4, I am not
> sure yet. And eventually I hope to tackle cubes of more
> than four dimensions. As I said, I tried to understand Don’s
> code for 2^k and 3^k cubes, but could not understand it.
>
> The only functionality of my program that I need is
> the ability to test whether a position is solvable. Any
> help you provide, no matter how little, would be greatly
> appreciated. I hope I’m not asking for too much. If
> there is anything I could do to reciprocate your kindness,
> please let me know. Of course if I find the answers I am
> looking for, this group would be the first to know!
>
> Once again, thank you for all of your help. I will let
> you know if I make any more progress.
>
> Best Regards,
>
> David
>
> PS: I just recently realized that you helped write the code for the
> 5-dimensional Rubiks Cube program. Amazing!
> Recent Activity
>
> - 1
> New Members<http://groups.yahoo.com/group/4D_Cubing/members;_ylc=X3oDMTJnaW1sdmNiBF9TAzk3MzU5NzE0BGdycElkAzEwNzE0OTI1BGdycHNwSWQDMTcwNTkyOTE0NwRzZWMDdnRsBHNsawN2bWJycwRzdGltZQMxMjA5NTk3MDg2>
>
> Visit Your Group
> <http://groups.yahoo.com/group/4D_Cubing;_ylc=X3oDMTJmN3RzNDdxBF9TAzk3MzU5NzE0BGdycElkAzEwNzE0OTI1BGdycHNwSWQDMTcwNTkyOTE0NwRzZWMDdnRsBHNsawN2Z2hwBHN0aW1lAzEyMDk1OTcwODY->
> Change your life
>
> with Yahoo! Groups<http://us.ard.yahoo.com/SIG=13o6qideu/M=493064.12016238.12823558.8674578/D=groups/S=1705929147:NC/Y=YAHOO/EXP=1209604286/L=/B=2yZIB0LaX98-/J=1209597086725579/A=5286672/R=0/SIG=11in3uvr5/*http://new.groups.yahoo.com/planforabalancedlife>
>
> balance nutrition,
>
> activity & well-being.
> Earth Day 2008
>
> Get things and<http://us.ard.yahoo.com/SIG=13ohuh6ju/M=493064.12016272.12948931.8674578/D=groups/S=1705929147:NC/Y=YAHOO/EXP=1209604286/L=/B=3CZIB0LaX98-/J=1209597086725579/A=5327832/R=0/SIG=1129o14gc/*http://green.yahoo.com/earth-day>
>
> get things for free.
>
> Find out how.
> Popular Y! Groups
>
> Is your group one?<http://us.ard.yahoo.com/SIG=13o16k0ah/M=493064.12016306.12445698.8674578/D=groups/S=1705929147:NC/Y=YAHOO/EXP=1209604286/L=/B=3SZIB0LaX98-/J=1209597086725579/A=4763761/R=0/SIG=11ou7otip/*http://advision.webevents.yahoo.com/bestofyahoogroups/>
>
> Check it out and
>
> see.
> .
>
>
>