Thread: "Hi everyone, I'm back!"

David,

=A0

I for one am actually enjoying your outbursts of mathematical talk, er=
roneous or not, and even when you do make mistakes or hasty conclusions, I =
feel like we can all learn from them.

=A0

Some time ago, I was doing research into God's Algorithm/God's=
Number for the Rubik's Cube. I came across a discussion of the first l=
ower bounds set on God's Number before Michael Reed's work. Althoug=
h it is a very crude proof and seems to be guaranteed to not get the right =
answer (having applied this idea to several puzzles), the argument does giv=
e a concrete proof of the lower bounds of God's Number for any puzzle a=
nd can be calculated in seconds.

=A0

My apologies if you are familiar with this work already, but in case y=
ou (or anyone else!) aren't (/isn't)=A0allow me to run through it q=
uickly:

=A0

The basic argument is as follows: Assume we are operating in the free =
group on the generators formed by the available moves of the Rubik's Cu=
be. What this essentially means is every possible sequence of moves is cons=
idered different even if they lead to the same position: for example UD is =
considered different from DU, even though they result in the same position.=
Clearly, the number of positions reachable in n moves is less than or equa=
l to the number of states in the free group reachable in n moves (i.e. the =
number of unique sequences of moves of length less than or equal to n; actu=
ally, I think I will just drop the free group perspective here, it isn'=
t really necessary). However, counting the number of sequences you can make=
in n moves is much easier than counting the number of states reachable in =
n moves. For a Rubik's cube, there are 18 choices for the first move. A=
fter that, there are only 15 choices because if you move the same face agai=
n, it could have been reached in only one move (using FTM). So, the number =
of sequences you could form in say, 3 moves or less is:

=A0

1+18+18*15+18*15*15 =3D 4339.

=A0

Now if we try to calculate the number of sequences you could form in 1=
6 moves or less, we get

=A0

1+18+18*15+18*15*15 +... =3D=A01 + 18*sum as n goes from=A00 to 15 of =
(15^n) =3D 1 + 18*((1-15^16)/(1-16)) [using the partial=A0sum of a=A0geomet=
ric series]

=A0

which is about 7.88x10^18. Now the main point here is:

=A0

number of positions reachable in 16 moves <=3D number of sequences =
of 16 moves or less < total number of states to a Rubik's Cube.>































=



--00032555f472bdc1b204a25b516d--

---

From: David Smith <djs314djs314@yahoo.com>
Date: Tue, 3 May 2011 06:05:04 -0700 (PDT)
Subject: Re: [MC4D] Hi everyone, I'm back!

=C2=A0



=20=20


=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
David,
=C2=A0
I for one am actually enjoying your outbursts of mathematical talk, erroneo=
us or not, and even when you do make mistakes or hasty conclusions, I feel =
like we can all learn from them.
=C2=A0
Some time ago, I was doing research into God's Algorithm/God's Number for t=
he Rubik's Cube. I came across a discussion of the first lower bounds set o=
n God's Number before Michael Reed's work. Although it is a very crude proo=
f and seems to be guaranteed to not get the right answer (having applied th=
is idea to several puzzles), the argument does give a concrete proof of the=
lower bounds of God's Number for any puzzle and can be calculated in secon=
ds.

=C2=A0
My apologies if you are familiar with this work already, but in case you (o=
r anyone else!) aren't (/isn't)=C2=A0allow me to run through it quickly:
=C2=A0
The basic argument is as follows: Assume we are operating in the free group=
on the generators formed by the available moves of the Rubik's Cube. What =
this essentially means is every possible sequence of moves is considered di=
fferent even if they lead to the same position: for example UD is considere=
d different from DU, even though they result in the same position. Clearly,=
the number of positions reachable in n moves is less than or equal to the =
number of states in the free group reachable in n moves (i.e. the number of=
unique sequences of moves of length less than or equal to n; actually, I t=
hink I will just drop the free group perspective here, it isn't really nece=
ssary). However, counting the number of sequences you can make in n moves i=
s much easier than counting the number of states reachable in n moves. For =
a Rubik's cube, there are 18 choices for the first move. After that, there =
are only 15 choices because if you move the same face again, it
could have been reached in only one move (using FTM). So, the number of se=
quences you could form in say, 3 moves or less is:

=C2=A0
1+18+18*15+18*15*15 =3D 4339.
=C2=A0
Now if we try to calculate the number of sequences you could form in 16 mov=
es or less, we get
=C2=A0
1+18+18*15+18*15*15 +... =3D=C2=A01 + 18*sum as n goes from=C2=A00 to 15 of=
(15^n) =3D 1 + 18*((1-15^16)/(1-16)) [using the partial=C2=A0sum of a=C2=
=A0geometric series]
=C2=A0
which is about 7.88x10^18. Now the main point here is:
=C2=A0
number of positions reachable in 16 moves <=3D number of sequences of 16 mo=
ves or less < total number of states to a Rubik's Cube.
=C2=A0
So the above is a simple proof that the lower bound for the Rubik's Cube is=
greater than 16. In fact you can make some more arguments that will allow =
you to push the limit above 17, but that isn't really necessary for my poin=
t.

=C2=A0
On to what I wanted to share:
What I did was apply this same idea to many, many other twisty puzzles to g=
et a decent guess at God's Number for different puzzles. (One funny result =
is that this analysis gives a lower bound of 42 for the megaminx). I discov=
ered something VERY interesting when I applied this to the 120Cell, though =
the numbers are significantly huger!

=C2=A0
The 120 Cell has 120 faces that can each be in one of 60 orientations. If t=
he 120Cell program used the equivalent of FTM, there would be 120*59=3D7080=
possibilities for the=C2=A01st move and 119*59=3D7021 possibilities for=C2=
=A0every move after that. However, the program uses the equivalent of QTM w=
hich means any 2/5 rotation around a pentagonal face of any cell cannot be =
achieved in 1 move. As there are 6 axes in one face about which this type o=
f rotation can happen, and 2 directions per axis, there are 6*2=3D12 orient=
ations of a cell that are not reachable in a single click. However, all oth=
er orientations are reachable in a single click. Thus, for this program the=
re are 120*(59-12)=3D5640 possibilities for the 1st move and 119*(59-12)=3D=
5593 possibilities for every move after that.

=C2=A0
To simplify things, let's only consider the last term in our sum. When you =
consider the geometric growth of the number of sequences of length=C2=A0n a=
nd the fact that countless sequences will return you to solved in less than=
those n moves (once n>3), it is fairly easy to see that in all likelihood,=
the last term alone is sufficient to GROSSLY overestimate the number of po=
sitions reachable in n moves. So, the question becomes what is the smallest=
n such that the number of sequences of length n (just exactly, not less th=
an or equal to) is greater than the number of positions of the 120Cell, whi=
ch we all know is 2.3*10^8126 thanks to you! In other words, what is the sm=
allest value of n such that

=C2=A0
5640*5593^(n-1)>2.3*10^8126.
=C2=A0
With some clever logarithmic manipulation, you can find this value on even =
a simple scientific calculator: n=3D2169. Although there is a small hole in=
this proof as I have presented it,=C2=A0I can say with 100% confidence tha=
t the 120Cell requires at least 2169 moves (and probably many more!) to eve=
n REACH every possible state, let alone reach them with a degree of equal l=
ikelihood. As far as I am aware, the stored scramble is only 1000 random mo=
ves, less than half of the number of the lower bounds for God's Number for =
the 120Cell.

=C2=A0
Not that I think it helps ANYONE, but this means that, strictly speaking, t=
he Magic 120Cell has NEVER been FULLY scrambled.... ;)
=C2=A0
I just wanted to reassure you that there is some truth in your concern over=
the insufficient number of scrambling moves for the 120Cell. I unfortunate=
ly discovered this near the very end of my solve, so as you can probably im=
agine, I wasn't terribly thrilled at the result because, again strictly spe=
aking, none of the 120Cell solves can really be considered legitimate... :(=
=C2=A0=C2=A0=C2=A0 (but again, I don't see how a solver can benefit from th=
e less than sufficient scramble)

=C2=A0
Think nothing of correcting yourself multiple times! I for one enjoy follow=
ing your work even in its mistakes. I am of the opinion that if the mistake=
is caught by the same person who made it, it was never a mistake at all, j=
ust an equation that hadn't been proofread. Many writers and editors would =
call such a thing a typo! ;)=20

=C2=A0
Enjoy,
Matt Galla
=C2=A0

PS: My best guess for the actual God's Number to the 120Cell is somewhere b=
etween 2450 and 2550, if anyone was curious. I by no means have any proof, =
just a guess based on extrapolation from puzzles with known God's Numbers.


On Sat, Apr 30, 2011 at 9:58 PM, David Smith wrote=
:


=C2=A0=20







Hello all,

I've given the matter below some more careful and serious thought, and real=
ize that I was a bit hasty to say that Magic120Cell would theoretically req=
uire 'millions' of twists to randomize it - that is probably far, far too h=
igh.=C2=A0 Also, I had made an implicit assumption without first checking t=
he facts.=C2=A0 Having revisited MagicTile and MC4D 4.0, I see that you are=
giving the puzzle many more twists that I had remembered.=C2=A0 My apologi=
es!=C2=A0 So, it seems my analysis below was more than a bit flawed.=C2=A0 =
At least I was trying to help, but next time I'll give the matter more care=
ful thought.=C2=A0 It's actually a bit humorous to read, given that I was s=
uggesting to consider we rewrite all of the scrambling code. :)


I'm certain Melinda, Don, Roice, and Jay are far more qualified than I am t=
o evaluate the number of twists needed to randomize a particular puzzle, si=
mply through experience.=C2=A0 I don't think I am capable of providing an a=
dequate 'Goldilocks' function; sorry for that.=C2=A0 The mathematics is far=
too heavy, and I wouldn't even know where to begin, given that I cannot ba=
se my answer on the optimal or near-optimal number of moves it takes to sol=
ve a particular puzzle.=C2=A0 I'm betting that the current scrambling metho=
ds being used are more than adequate.


I apologize, but hopefully this was a good laugh for some of you. :)

All the best,
David

--- On Sat, 4/30/11, David Smith wrote:



From: David Smith =20

Subject: Re: [MC4D] Hi everyone, I'm back!
To: 4D_Cubing@yahoogroups.com
Date: Saturday, April 30, 2011, 8:22 AM=20





=C2=A0=20





Thank you so much Melinda!=C2=A0 You are very gracious. :)

I haven't browsed most of the messages I've missed (obviously there are a l=
ot!), but after my reintroduction, I was immediately astounded by all of th=
e new programs!=C2=A0 7-dimensional Rubik's Cubes? Magic Hyperbolic Tile?=
=C2=A0 5-dimensional Pac-man?=C2=A0 4-dimensional Tetris?!=C2=A0 Incredible=
!=C2=A0 I think Andrey deserves an award for being one of the talented prog=
rammers in the world, in the 'Creative Genius' category!=C2=A0 And Roice pr=
ovided the inspiration, being the first person to ever program a 5D Cube an=
d Tile-based puzzles! (I'm sure he could do even more, but he is very busy!=
)=C2=A0 And you and Don provided the inspiration for Roice, and this group.=
:)


I feel so bad I missed out sharing the good times.=C2=A0 But, it seems ther=
e are still plenty to be had!=C2=A0 The only computer program I have writte=
n recently simulates Ulam's Game, a mathematical thought experiment.=C2=A0 =
I believe it is the only one of its kind.=C2=A0 But it was trivial to creat=
e; nothing even remotely close to what all of you have accomplished.=C2=A0 =
I'm constantly inspired by your intelligence!=C2=A0 And I forgot to mention=
that one day I do intend to work out solving these puzzles for myself.


I've done some research into the Goldilocks function problem, and I have so=
me bad news, and some worse news. :(=C2=A0 The implications could be unfort=
unate, and you may wish I had never looked into it.=C2=A0 It's up to all of=
you as to how you would like to proceed.=C2=A0 I'm fine with keeping thing=
s as they are, and that what I am about to say may be considered questionab=
le and irrelevant to our current scrambling methods.


First, the bad news: This Goldilocks function is almost certainly beyond my=
capabilities.=C2=A0 I'm betting a mathematician would have much trouble.=
=C2=A0 The problem is that the number of moves it takes to produce a 'suffi=
ciently random' position (which is already a subjective term; it can be mad=
e more precise mathematically, in a way that is somewhat above my head), va=
ries from puzzle to puzzle.=C2=A0 I doubt there is a general solution.=C2=
=A0 Also, I doubt that it is practical to answer this question for any part=
icular puzzle by purely mathematical methods, given the extreme difficulty.=
=C2=A0 Computer tests need to be performed, i.e. scrambles need to be done =
repeatedly and analyzed with statistics.


Here is the worse news: Such statistical analyses have already been perform=
ed for the 3^3 Cube and Megaminx.=C2=A0 You can see the report on this page=
:

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/41005


It is true that the results are not the work of a mathematician, and the an=
alyses could have been simplified and improved upon, but I've studied the p=
aper and there appear to be no errors.=C2=A0 I believe that the results are=
accurate enough for our purposes.


I originally conjectured that 20 moves would suffice to scramble the Rubik'=
s Cube, since every position can be solved in at most 20 moves.=C2=A0 This =
turns out to be a very naive and flawed assumption.=C2=A0 According to the =
report, it takes around 45 moves to scramble a Rubik's Cube so that it is s=
ufficiently random.


Now, he also studied the megaminx.=C2=A0 This is where things begin to get =
depressing.=C2=A0 According to the page, it takes around 250 moves for the =
megaminx to begin to become randomly mixed.=C2=A0 We can see the number of =
moves rapidly increasing with the complexity of the puzzle.=C2=A0 The megam=
inx is simpler than even the standard 3^4 cube.=C2=A0 So, I'm very roughly =
estimating that for a puzzle such as Magic120Cell, which is hugely complex,=
the number of moves required to generate a sufficiently random position co=
uld be in the hundred thousands, millions, or even higher!


So, I feel that for the more complex puzzles, and perhaps even for the simp=
ler ones, we have not performed anywhere near the necessary number of scram=
bling moves required.=C2=A0 The solution to the question you asked me, i.e.=
how many moves it takes to generate sufficiently random positions on vario=
us puzzles, may be much, much higher than any of us previously thought, eve=
n for the puzzles we have all been enjoying for years now.=C2=A0 I only see=
two solutions to this problem, and the second is my recommendation.


First, we could reexamine the entire way we have been generating random pos=
itions.=C2=A0 We could find a way to do so that does not involve twisting a=
random puzzle a certain number of times from the solved state, but rather =
generating a random permutation and orientation of all of the pieces.=C2=A0=
We then check (this is where my formulas would actually come in handy!) if=
each particular type of piece (they would be the 'families' in my NxNxNxN =
Cube permutation paper) satisfies the mathematical criteria for producing a=
solvable cube.=C2=A0 If not, then we twist one of the pieces or swap two o=
f them or both, depending on the situation.


This method, however, has several obvious and significant drawbacks:

1. We would need to reprogram all of the scrambling mechanisms for every pr=
ogram (depending on who would accept to do so), which would be an arduous, =
lengthy and painstaking task.


2. The algorithm for doing so would be enormously complicated.

3. We would need to find the mathematical restrictions on the pieces of eve=
ry type of puzzle available.=C2=A0 This would involve a huge mathematical e=
ffort on my part, making us all very busy for months.=C2=A0 Also, the 'crea=
te a puzzle' feature in MC4D 4.0 might have to be discarded.


Now, here is the second option: we do nothing.=C2=A0 Or, to put it in more =
optimistic terms, we reevaluate what 'sufficiently random' means to us, not=
what it means technically.=C2=A0 We have all been enjoying all of your col=
lective creations for many years now.=C2=A0 We never realized the possibili=
ty that the scrambles are *technically* not close to random.=C2=A0 From our=
point of view, it appears as if it is random.=C2=A0 And maybe that's good =
enough for us.=C2=A0 I'm betting that no one will have a problem with accep=
ting that our puzzles, especially the more complex ones, may not be technic=
ally even close to random as we once thought, but that this knowledge in no=
way affects our enjoyment of solving the puzzle, or the difficulty we perc=
eive.=C2=A0 Indeed, we could probably never recognize the difference betwee=
n 'technically sufficiently random' and 'practically sufficiently random' i=
f we were presented with both.=C2=A0 So, I would suggest simply using the m=
aximum number of
scrambles you feel you can reasonably employ, taking into consideration th=
e sizes of the log files, for each puzzle.=C2=A0 Maybe the puzzles with two=
pieces per edge could be less than the maximum.=C2=A0 Of course, this maxi=
mum should vary for the complexity of each puzzle.=C2=A0 It will be the bes=
t we can do, and it should certainly be sufficient.


So, hopefully we can consider the Goldilocks function to not be of too much=
importance.=C2=A0 You have already said yourself that it was of very low p=
riority, so perhaps this lengthy dialogue was unnecessary.=C2=A0 But I thou=
ght I would go into as much detail as possible, for the benefit of everyone=
.


Thanks again for welcoming me back!=C2=A0 It's good to be back. :)=C2=A0 I =
now belong to many yahoo groups, but this was the first, and all of you wer=
e really my first true friends, honestly.=C2=A0 It's a shame I made such a =
poor decision in leaving, and I regret it, but at least I've summoned the c=
ourage to come back and repair my mistake.


Anyway, I hope my Goldilocks discussion was helpful, and I'm confident we d=
on't need to modify the algorithms, as you most likely are as well.=C2=A0 H=
ave a great weekend, everyone!=C2=A0 I'll be keeping in touch. :)


All the best,
David



--- On Sat, 4/30/11, Melinda Green wrote:


From: Melinda Green
Subject: Re: [MC4D] Hi everyone, I'm back!

To: 4D_Cubing@yahoogroups.com
Date: Saturday, April 30, 2011, 1:17 AM


=C2=A0=20

Hello David, and welcome home! :-)

I was sad when you left, but mostly I was worried that you felt badly=20
about somehow letting anybody down. So far as I know, you did nothing=20
wrong nor let anybody down when you left. I don't need any explanations.=20

Since you ask, the only thing that I could have made use of was the=20
Goldilocks function we discussed but I never depended on you for that=20
and it is of such low priority as to not matter. Please don't even think=20

about it unless you want to do that for your own satisfaction. Everyone=20
can come and go from this group as they please, and contribute what they=20
like and change their mind at any time. As long as people are nice to=20

each other and keep the discussions even vaguely on-topic, I'm perfectly=20
happy. Of course I'm thrilled that you are back because you have been=20
such a helpful resource in the past! Roice is perfectly correct. You are=20

among friends.

Have fun catching up! :-D
-Melinda

On 4/29/2011 3:47 PM, djs314djs314 wrote:
> Hello my friends,
>
> First of all, I very deeply apologize for my inexplicable behavior when I=
suddenly and mysteriously left this group of very close friends over half =
a year ago. I have had some very serious issues going on in my life. In Nov=
ember I was hospitalized for a couple of weeks. To be a bit further ambiguo=
us (sorry!), my departure was related to a symptom of my multiple illnesses=
. Of course, I can't blame a foolish, consciousness decision entirely on a =
symptom, and don't intend to. If any of you really want to know the whole s=
tory, I'll share it, but with some hesitation! :) Melinda, you probably des=
erve an explanation, so I will send one to you privately at your request. A=
gain, I apologize for my behavior, but am very much looking forward to bein=
g an active member again, if you will have me.

>
> A very meaningful conversation with my good friend Roice inspired me to r=
ejoin this group. I have wanted to for a while, but was honestly afraid of =
how everyone would respond. Roice helped me realize that I am among friends=
, and don't need to worry about such things.

>
> Well, I'm honestly thrilled to be back! :D I have so much to catch up on!=
I've only briefly scanned some of the recent messages, but I see that Magi=
c120Cell and Klein's Quartic have some new solvers! And of course, there ha=
ve been contests (blindfold solving?!) and new programs. I'll have to check=
out all that!

>
> Hopefully my reintroduction will inspire me to help out and contribute wh=
erever I can. I would like to get back into the combinatorics of the puzzle=
s. Specifically, I've been promising myself for quite a while to find the o=
rder of the 'n^d super-superhypercube group' (at least that is what I call =
it! :) ). A super-supercube is like a Rubik's Cube of any size in which eve=
ry cubie is either on the surface or on the inside of the cube; the cube is=
solid. Any layer can be twisted. Also, each cubie has a unique identity an=
d orientation (imagine that each face of each cubie has a unique integer as=
sociated to it). Obviously I don't need to expalin how this extends to high=
er dimensions. My goal is to find a formula for the number of visually diti=
nguishable permutations of a cube of arbitrary size,>=3D 2, and arbitrary d=
imension,>=3D 3, that can be produced by a sequence of legal moves from the=
solved position

>
> Also, there are so many other areas I could investigate. If Andrey would =
like, I can supply an explicit 7-dimensional formula for counting cube perm=
utations, but that probably isn't necessary. (My general formula handles al=
l dimensions, and who needs such a formula anyway? ;) ) There is also Klein=
's Quartic (if you guys haven't figured it out already), general MagicTile =
puzzles, general MagicCube4D 2.0 puzzles, etc. I know such efforts are not =
terribly important to the group, but they do provide me some satisfaction a=
nd I would be happy to provide any new formulas I find.

>
> My page of research has moved again, by the way, it is now here:
>
> http://seti.weebly.com/channel.html
>

> Amongst the materials are formulas for n^4, n^5, n^6, and n^d permutation=
s, my Magic120Cell paper, my paper deriving the n^4 formula, and a coloring=
result for Magic120Cell.
>
> I would also like to wish a warm welcome to any members who may have join=
ed since my unfortunate departure. I wish you the best, and look forward to=
meeting you!

>
> And Melinda, I had previously promised to help you with some research for=
MagicCube4D 2.0. If you still require my assistance, I am ready to help as=
soon as possible.
>
> Thank you everyone so much for your understanding and patience. :) It's t=
ime for me to browse the messages and download some programs! I'll be writi=
ng again soon, and have a great day!

>
> All the best,
> David








=20=20=20=20
=20=20=20=20=20

=20=20=20=20
=20=20=20=20


=20



=20=20




--0-1233418093-1304427904=:32307
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">Hi Matt, This is obviously very late, = but I'm glad you joined the cubing group!  When I first met you, I = believe you hadn't yet joined.  Again, thank you for your Magic120Cell= algorithms as well! With regards to my mathematical observations= and corrections, both you and Brandon have said that you appreciate my = results, and that it is insightful and helpful to see my mistakes. = However, I don't know how many more posts all of you are going to want = to hear from me - I have a lot of ground to cover!  So, I'm working= on a new collection of pages on the wiki, as Roice suggested I attempt.>There is now a Permutations section of the main page.  From there, on= e can go to the Puzzle Index page or the Notation page.  The Puzzle= Index page has not yet been created, but it will contain a link to a unique page for every puzzle in existence.  They will be sorted by= the program(s) they appear in. Each puzzle's page will contain a pictur= e, description, permutation equation and number, and as complete of an e= xplanation I can give without going too far into the mathematical detail= s.  Basically, the explanations will consist of a list of each type= of piece in the puzzle, accompanied by a count of the number of such pi= eces in the puzzle, and how many permutations and orientations they can = achieve, also giving the restrictions for those counts and the reasoning= behind them (for example, the orientation of the last corner piece is d= etermined by the orientations of the others, thus we must divide our res= ult by 3). I have completed the Notation page, which should be inter= esting reading for some of you.  In it, I describe a way to name th= e pieces of any puzzle, including MagicTile, and likely any future puzzle of any dimension, via a single system.  I could have= chosen to be more specific in some places with my method (i.e. further = distinguishing different types of pieces than I currently do), but my fo= cus was on to classify groups of pieces that have the same permutation a= nd orientation counts.  This method is generalized from my n^4 form= ula and proof paper, available in the files section of the yahoo group.&= nbsp; Some years ago there was a discussion of how to name pieces of a c= ube of any dimension, so I humbly consider it a significant acheivement = that I have come up with a way to name any piece of any possible puzzle = with a single, precise method. I very much enjoyed reading your expl= anation of determining the lower bound of God's algorithm of any puzzle!=   You are right, Magic120Cell most likely has a very large God's nu= mber.  And the page I previously pointed out showed that to make a puzzle random, you must scramble it a number of moves which is m= any orders of magnitude larger than God's number, as you observed as wel= l.  I just thought I went a bit too far with claiming this number c= ould be in the millions (although I honestly don't know.) I hope = that my Notation section will be interesting to take a look at for some = of you, though of course there is no need to do so.  It's just another= of my odd contributions. :)  By the way, as most of you probably k= now, Roice has shown how to count the number of k-colored pieces on an n= -dimensional cube, which has been very helpful to me.  After much r= esearch, and with credit to many others (the authors of The Rubik Tesser= act and An n-dimensional Rubik Cube), I have done something similar with= counting orientations of any family ('family' is defined in the Notatio= n page) of pieces.  Furthermore, my result is very general, such that it applies to virtually any puzzle.  The conditions for = its application are very minimal.  Roice suggested I share it with the= group, so I might do that soon. Thanks for writing and welcoming= me back!  I look forward to further contributing to this wonderful= community. All the best, David --- On Tue, 5/3/11, Mat= thew Galla <mgalla@trinity.edu> wrote: e=3D"border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-lef= t: 5px;"> From: Matthew Galla <mgalla@trinity.edu> Subject: Re:= [MC4D] Hi everyone, I'm back! To: 4D_Cubing@yahoogroups.com Date: Tu= esday, May 3, 2011, 4:56 AM   =20=20=20=20=20=20 =20=20=20=20=20=20 David,   I for one am actually enjoying your outbursts of mathematical talk, er= roneous or not, and even when you do make mistakes or hasty conclusions, I = feel like we can all learn from them.   Some time ago, I was doing research into God's Algorithm/God's Number = for the Rubik's Cube. I came across a discussion of the first lower bounds = set on God's Number before Michael Reed's work. Although it is a very crude= proof and seems to be guaranteed to not get the right answer (having appli= ed this idea to several puzzles), the argument does give a concrete proof o= f the lower bounds of God's Number for any puzzle and can be calculated in = seconds.   My apologies if you are familiar with this work already, but in case y= ou (or anyone else!) aren't (/isn't) allow me to run through it quickl= y:   The basic argument is as follows: Assume we are operating in the free = group on the generators formed by the available moves of the Rubik's Cube. = What this essentially means is every possible sequence of moves is consider= ed different even if they lead to the same position: for example UD is cons= idered different from DU, even though they result in the same position. Cle= arly, the number of positions reachable in n moves is less than or equal to= the number of states in the free group reachable in n moves (i.e. the numb= er of unique sequences of moves of length less than or equal to n; actually= , I think I will just drop the free group perspective here, it isn't really= necessary). However, counting the number of sequences you can make in n mo= ves is much easier than counting the number of states reachable in n moves.= For a Rubik's cube, there are 18 choices for the first move. After that, t= here are only 15 choices because if you move the same face again, it could have been reached in only one move (using FTM). So, the number of se= quences you could form in say, 3 moves or less is:   1+18+18*15+18*15*15 =3D 4339.   Now if we try to calculate the number of sequences you could form in 1= 6 moves or less, we get   1+18+18*15+18*15*15 +... =3D 1 + 18*sum as n goes from 0 to = 15 of (15^n) =3D 1 + 18*((1-15^16)/(1-16)) [using the partial sum of a=  geometric series]   which is about 7.88x10^18. Now the main point here is:   number of positions reachable in 16 moves <=3D number of sequences = of 16 moves or less < total number of states to a Rubik's Cube.   So the above is a simple proof that the lower bound for the Rubik's Cu= be is greater than 16. In fact you can make some more arguments that will a= llow you to push the limit above 17, but that isn't really necessary for my= point.   On to what I wanted to share: What I did was apply this same idea to many, many other twisty puzzles= to get a decent guess at God's Number for different puzzles. (One funny re= sult is that this analysis gives a lower bound of 42 for the megaminx). I d= iscovered something VERY interesting when I applied this to the 120Cell, th= ough the numbers are significantly huger!   The 120 Cell has 120 faces that can each be in one of 60 orientations.= If the 120Cell program used the equivalent of FTM, there would be 120*59= =3D7080 possibilities for the 1st move and 119*59=3D7021 possibilities= for every move after that. However, the program uses the equivalent o= f QTM which means any 2/5 rotation around a pentagonal face of any cell can= not be achieved in 1 move. As there are 6 axes in one face about which this= type of rotation can happen, and 2 directions per axis, there are 6*2=3D12= orientations of a cell that are not reachable in a single click. However, = all other orientations are reachable in a single click. Thus, for this prog= ram there are 120*(59-12)=3D5640 possibilities for the 1st move and 119*(59= -12)=3D5593 possibilities for every move after that.   To simplify things, let's only consider the last term in our sum. When= you consider the geometric growth of the number of sequences of length&nbs= p;n and the fact that countless sequences will return you to solved in less= than those n moves (once n>3), it is fairly easy to see that in all lik= elihood, the last term alone is sufficient to GROSSLY overestimate the numb= er of positions reachable in n moves. So, the question becomes what is the = smallest n such that the number of sequences of length n (just exactly, not= less than or equal to) is greater than the number of positions of the 120C= ell, which we all know is 2.3*10^8126 thanks to you! In other words, what i= s the smallest value of n such that   5640*5593^(n-1)>2.3*10^8126.   With some clever logarithmic manipulation, you can find this value on = even a simple scientific calculator: n=3D2169. Although there is a small ho= le in this proof as I have presented it, I can say with 100% confidenc= e that the 120Cell requires at least 2169 moves (and probably many more!) t= o even REACH every possible state, let alone reach them with a degree of eq= ual likelihood. As far as I am aware, the stored scramble is only 1000 rand= om moves, less than half of the number of the lower bounds for God's Number= for the 120Cell.   Not that I think it helps ANYONE, but this means that, strictly speaki= ng, the Magic 120Cell has NEVER been FULLY scrambled.... ;)   I just wanted to reassure you that there is some truth in your concern= over the insufficient number of scrambling moves for the 120Cell. I unfort= unately discovered this near the very end of my solve, so as you can probab= ly imagine, I wasn't terribly thrilled at the result because, again strictl= y speaking, none of the 120Cell solves can really be considered legitimate.= .. :(    (but again, I don't see how a solver can benefit fr= om the less than sufficient scramble)   Think nothing of correcting yourself multiple times! I for one enjoy f= ollowing your work even in its mistakes. I am of the opinion that if the mi= stake is caught by the same person who made it, it was never a mistake at a= ll, just an equation that hadn't been proofread. Many writers and editors w= ould call such a thing a typo! ;)   Enjoy, Matt Galla   PS: My best guess for the actual God's Number to the 120Cell is so= mewhere between 2450 and 2550, if anyone was curious. I by no means have an= y proof, just a guess based on extrapolation from puzzles with known God's = Numbers. On Sat, Apr 30, 2011 at 9:58 PM, David = Smith <314@yahoo.com" target=3D"_blank" href=3D"/mc/compose?to=3Ddjs314djs314@yaho= o.com">djs314djs314@yahoo.com> wrote: iv982473gmail_quote">  =20 Hello all, I've given the matter below some more = careful and serious thought, and realize that I was a bit hasty to say that= Magic120Cell would theoretically require 'millions' of twists to randomize= it - that is probably far, far too high.  Also, I had made an implici= t assumption without first checking the facts.  Having revisited Magic= Tile and MC4D 4.0, I see that you are giving the puzzle many more twists th= at I had remembered.  My apologies!  So, it seems my analysis bel= ow was more than a bit flawed.  At least I was trying to help, but nex= t time I'll give the matter more careful thought.  It's actually a bit= humorous to read, given that I was suggesting to consider we rewrite all o= f the scrambling code. :) I'm certain Melinda, Don, Roice, and Jay are far more qualified than I = am to evaluate the number of twists needed to randomize a particular puzzle= , simply through experience.  I don't think I am capable of providing = an adequate 'Goldilocks' function; sorry for that.  The mathematics is= far too heavy, and I wouldn't even know where to begin, given that I canno= t base my answer on the optimal or near-optimal number of moves it takes to= solve a particular puzzle.  I'm betting that the current scrambling m= ethods being used are more than adequate. I apologize, but hopefully this was a good laugh for some of you. :)> All the best, David --- On Sat, 4/30/11, David Smith &= lt;_blank" href=3D"/mc/compose?to=3Ddjs314djs314@yahoo.com">djs314djs314@yahoo= .com> wrote: From: Da= vid Smith < target=3D"_blank" href=3D"/mc/compose?to=3Ddjs314djs314@yahoo.com">djs314d= js314@yahoo.com>=20 Subject: Re: [MC4D] Hi everyone, I'm back!r>To: et=3D"_blank" href=3D"/mc/compose?to=3D4D_Cubing@yahoogroups.com">4D_Cubing= @yahoogroups.com Date: Saturday, April 30, 2011, 8:22 AM=20  =20 Thank you so much Melinda!  You are very gracious. = :) I haven't browsed most of the messages I've missed (obviously the= re are a lot!), but after my reintroduction, I was immediately astounded by= all of the new programs!  7-dimensional Rubik's Cubes? Magic Hyperbol= ic Tile?  5-dimensional Pac-man?  4-dimensional Tetris?!  In= credible!  I think Andrey deserves an award for being one of the talen= ted programmers in the world, in the 'Creative Genius' category!  And = Roice provided the inspiration, being the first person to ever program a 5D= Cube and Tile-based puzzles! (I'm sure he could do even more, but he is ve= ry busy!)  And you and Don provided the inspiration for Roice, and thi= s group. :) I feel so bad I missed out sharing the good times.  But, it seems = there are still plenty to be had!  The only computer program I have wr= itten recently simulates Ulam's Game, a mathematical thought experiment.&nb= sp; I believe it is the only one of its kind.  But it was trivial to c= reate; nothing even remotely close to what all of you have accomplished.&nb= sp; I'm constantly inspired by your intelligence!  And I forgot to men= tion that one day I do intend to work out solving these puzzles for myself.= I've done some research into the Goldilocks function problem, and I hav= e some bad news, and some worse news. :(  The implications could be un= fortunate, and you may wish I had never looked into it.  It's up to al= l of you as to how you would like to proceed.  I'm fine with keeping t= hings as they are, and that what I am about to say may be considered questi= onable and irrelevant to our current scrambling methods. First, the bad news: This Goldilocks function is almost certainly beyon= d my capabilities.  I'm betting a mathematician would have much troubl= e.  The problem is that the number of moves it takes to produce a 'suf= ficiently random' position (which is already a subjective term; it can be m= ade more precise mathematically, in a way that is somewhat above my head), = varies from puzzle to puzzle.  I doubt there is a general solution.&nb= sp; Also, I doubt that it is practical to answer this question for any part= icular puzzle by purely mathematical methods, given the extreme difficulty.=   Computer tests need to be performed, i.e. scrambles need to be done = repeatedly and analyzed with statistics. Here is the worse news: Such statistical analyses have already been per= formed for the 3^3 Cube and Megaminx.  You can see the report on this = page: ups.yahoo.com/group/speedsolvingrubikscube/message/41005">http://games.grou= ps.yahoo.com/group/speedsolvingrubikscube/message/41005 It is true that the results are not the work of a mathematician, and th= e analyses could have been simplified and improved upon, but I've studied t= he paper and there appear to be no errors.  I believe that the results= are accurate enough for our purposes. I originally conjectured that 20 moves would suffice to scramble the Ru= bik's Cube, since every position can be solved in at most 20 moves.  T= his turns out to be a very naive and flawed assumption.  According to = the report, it takes around 45 moves to scramble a Rubik's Cube so that it = is sufficiently random. Now, he also studied the megaminx.  This is where things begin to = get depressing.  According to the page, it takes around 250 moves for = the megaminx to begin to become randomly mixed.  We can see the number= of moves rapidly increasing with the complexity of the puzzle.  The m= egaminx is simpler than even the standard 3^4 cube.  So, I'm very roug= hly estimating that for a puzzle such as Magic120Cell, which is hugely comp= lex, the number of moves required to generate a sufficiently random positio= n could be in the hundred thousands, millions, or even higher! So, I feel that for the more complex puzzles, and perhaps even for the = simpler ones, we have not performed anywhere near the necessary number of s= crambling moves required.  The solution to the question you asked me, = i.e. how many moves it takes to generate sufficiently random positions on v= arious puzzles, may be much, much higher than any of us previously thought,= even for the puzzles we have all been enjoying for years now.  I only= see two solutions to this problem, and the second is my recommendation.> First, we could reexamine the entire way we have been generating random= positions.  We could find a way to do so that does not involve twisti= ng a random puzzle a certain number of times from the solved state, but rat= her generating a random permutation and orientation of all of the pieces.&n= bsp; We then check (this is where my formulas would actually come in handy!= ) if each particular type of piece (they would be the 'families' in my NxNx= NxN Cube permutation paper) satisfies the mathematical criteria for produci= ng a solvable cube.  If not, then we twist one of the pieces or swap t= wo of them or both, depending on the situation. This method, however, has several obvious and significant drawbacks:> 1. We would need to reprogram all of the scrambling mechanisms for eve= ry program (depending on who would accept to do so), which would be an ardu= ous, lengthy and painstaking task. 2. The algorithm for doing so would be enormously complicated. 3= . We would need to find the mathematical restrictions on the pieces of ever= y type of puzzle available.  This would involve a huge mathematical ef= fort on my part, making us all very busy for months.  Also, the 'creat= e a puzzle' feature in MC4D 4.0 might have to be discarded. Now, here is the second option: we do nothing.  Or, to put it in m= ore optimistic terms, we reevaluate what 'sufficiently random' means to us,= not what it means technically.  We have all been enjoying all of your= collective creations for many years now.  We never realized the possi= bility that the scrambles are *technically* not close to random.  From= our point of view, it appears as if it is random.  And maybe that's g= ood enough for us.  I'm betting that no one will have a problem with a= ccepting that our puzzles, especially the more complex ones, may not be tec= hnically even close to random as we once thought, but that this knowledge i= n no way affects our enjoyment of solving the puzzle, or the difficulty we = perceive.  Indeed, we could probably never recognize the difference be= tween 'technically sufficiently random' and 'practically sufficiently rando= m' if we were presented with both.  So, I would suggest simply using the maximum number of scrambles you feel you can reasonably employ, = taking into consideration the sizes of the log files, for each puzzle. = ; Maybe the puzzles with two pieces per edge could be less than the maximum= .  Of course, this maximum should vary for the complexity of each puzz= le.  It will be the best we can do, and it should certainly be suffici= ent. So, hopefully we can consider the Goldilocks function to not be of too = much importance.  You have already said yourself that it was of very l= ow priority, so perhaps this lengthy dialogue was unnecessary.  But I = thought I would go into as much detail as possible, for the benefit of ever= yone. Thanks again for welcoming me back!  It's good to be back. :) = ; I now belong to many yahoo groups, but this was the first, and all of you= were really my first true friends, honestly.  It's a shame I made suc= h a poor decision in leaving, and I regret it, but at least I've summoned t= he courage to come back and repair my mistake. Anyway, I hope my Goldilocks discussion was helpful, and I'm confident = we don't need to modify the algorithms, as you most likely are as well.&nbs= p; Have a great weekend, everyone!  I'll be keeping in touch. :) All the best, David --- On Sat, 4/30/11, Melinda G= reen < target=3D"_blank" href=3D"/mc/compose?to=3Dmelinda@superliminal.com">melin= da@superliminal.com> wrote: From: Me= linda Green <com" target=3D"_blank" href=3D"/mc/compose?to=3Dmelinda@superliminal.com">m= elinda@superliminal.com> Subject: Re: [MC4D] Hi everyone, I'm bac= k! To: =3D"_blank" href=3D"/mc/compose?to=3D4D_Cubing@yahoogroups.com">4D_Cubing@y= ahoogroups.com Date: Saturday, April 30, 2011, 1:17 AM  =20 Hello David, and welcome home! :-) I was sad when you left, but m= ostly I was worried that you felt badly about somehow letting anybody d= own. So far as I know, you did nothing wrong nor let anybody down when = you left. I don't need any explanations. Since you ask, the only thing that I could have made use of was the Gol= dilocks function we discussed but I never depended on you for that and = it is of such low priority as to not matter. Please don't even think about it unless you want to do that for your own satisfaction. Everyone >can come and go from this group as they please, and contribute what they <= br>like and change their mind at any time. As long as people are nice to r> each other and keep the discussions even vaguely on-topic, I'm perfectly r>happy. Of course I'm thrilled that you are back because you have been >such a helpful resource in the past! Roice is perfectly correct. You are <= br> among friends. Have fun catching up! :-D -Melinda On 4/29/= 2011 3:47 PM, djs314djs314 wrote: > Hello my friends, > >= First of all, I very deeply apologize for my inexplicable behavior when I = suddenly and mysteriously left this group of very close friends over half a= year ago. I have had some very serious issues going on in my life. In Nove= mber I was hospitalized for a couple of weeks. To be a bit further ambiguou= s (sorry!), my departure was related to a symptom of my multiple illnesses.= Of course, I can't blame a foolish, consciousness decision entirely on a s= ymptom, and don't intend to. If any of you really want to know the whole st= ory, I'll share it, but with some hesitation! :) Melinda, you probably dese= rve an explanation, so I will send one to you privately at your request. Ag= ain, I apologize for my behavior, but am very much looking forward to being= an active member again, if you will have me. > > A very meaningful conversation with my good friend Roice inspi= red me to rejoin this group. I have wanted to for a while, but was honestly= afraid of how everyone would respond. Roice helped me realize that I am am= ong friends, and don't need to worry about such things. > > Well, I'm honestly thrilled to be back! :D I have so much to c= atch up on! I've only briefly scanned some of the recent messages, but I se= e that Magic120Cell and Klein's Quartic have some new solvers! And of cours= e, there have been contests (blindfold solving?!) and new programs. I'll ha= ve to check out all that! > > Hopefully my reintroduction will inspire me to help out and co= ntribute wherever I can. I would like to get back into the combinatorics of= the puzzles. Specifically, I've been promising myself for quite a while to= find the order of the 'n^d super-superhypercube group' (at least that is w= hat I call it! :) ). A super-supercube is like a Rubik's Cube of any size i= n which every cubie is either on the surface or on the inside of the cube; = the cube is solid. Any layer can be twisted. Also, each cubie has a unique = identity and orientation (imagine that each face of each cubie has a unique= integer associated to it). Obviously I don't need to expalin how this exte= nds to higher dimensions. My goal is to find a formula for the number of vi= sually ditinguishable permutations of a cube of arbitrary size,>=3D 2, a= nd arbitrary dimension,>=3D 3, that can be produced by a sequence of leg= al moves from the solved position > > Also, there are so many other areas I could investigate. If An= drey would like, I can supply an explicit 7-dimensional formula for countin= g cube permutations, but that probably isn't necessary. (My general formula= handles all dimensions, and who needs such a formula anyway? ;) ) There is= also Klein's Quartic (if you guys haven't figured it out already), general= MagicTile puzzles, general MagicCube4D 2.0 puzzles, etc. I know such effor= ts are not terribly important to the group, but they do provide me some sat= isfaction and I would be happy to provide any new formulas I find. > > My page of research has moved again, by the way, it is now her= e: > > i.weebly.com/channel.html">http://seti.weebly.com/channel.html ><= br> > Amongst the materials are formulas for n^4, n^5, n^6, and n^d permutat= ions, my Magic120Cell paper, my paper deriving the n^4 formula, and a color= ing result for Magic120Cell. > > I would also like to wish a wa= rm welcome to any members who may have joined since my unfortunate departur= e. I wish you the best, and look forward to meeting you! > > And Melinda, I had previously promised to help you with some r= esearch for MagicCube4D 2.0. If you still require my assistance, I am ready= to help as soon as possible. > > Thank you everyone so much fo= r your understanding and patience. :) It's time for me to browse the messag= es and download some programs! I'll be writing again soon, and have a great= day! > > All the best, > David e> ote> =20=20=20=20=20 =20

--0-1233418093-1304427904=:32307--

---

From: Melinda Green <melinda@superliminal.com>
Date: Tue, 03 May 2011 15:26:02 -0700
Subject: Re: [MC4D] Hi everyone, I'm back!

--------------080302050507090200020101
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

Hello David,

Thank you for your kind words.

I know that you worry a lot about your place here and like others before
me, I want to assure you that there is no reason to doubt that. Really,
as long as you are nice to everybody and remain even vaguely on-topic,
you have nothing to worry about. Regarding lengthy or frequent messages,
everybody on the list is quite able to delete messages that they are not
interested in. If someone is not interested in combinatorics, they can
even filter out all messages from you, and they shouldn't have the
slightest guilt about doing that. Of course you will want to avoid that
as much as that is within your control. For that, I suggest waiting 24
hours after composing a long message, and rereading it before you hit
"send". That way you may realize some potential problems before posting.

I also agree with Roice that the best place to share detailed
calculations is in the wiki, so I'm glad that you are having fun with
that. You can then announce new sections as you feel they are complete,
and of course you can fix any mistakes later without even announcing
them. People can watch pages of interest to them, and otherwise just
look-up particular pages as needed and see the latest data.

It is fascinating to remember all of the amazing puzzles and interesting
discussions that have transpired since you left. Certainly this has been
one of our richest periods especially due to Andrey and Roice's
contributions. There have been many times in the past when I thought
that maybe everything worthy of discussing in this realm had already
been discussed, but then something new and interesting always crops up.
That has happened so often that I no longer think the stream of
interesting puzzles and topics will ever end. The group may go quiet for
several months, but then something completely unexpected crops up and we
all get to watch it being explored even if we don't participate in the
discussion.

I have some thoughts to share regarding the Goldilocks function. The
first is that I had a small epiphany the other day while thinking about
the insights you gave. I now feel that I have a good feeling for why the
number of scrambling twists needed to fully scramble some puzzles can be
so amazingly high. Imagine the path of a single piece during the
scrambling process. If the puzzle is to be fully scrambled, then that
piece needs to be equally likely to end up in any possible position. For
a puzzle with a lot of faces (cells), a given piece must be able to
easily wander to the extreme opposite side of the puzzle. Scrambling
using random twists will cause that piece to move around with something
like Brownian motion which makes it unlikely for any piece to move very
far in just a few random twists that affect it. The result is something
like carefully placing a single drop of ink into a glass of water and
watching it spread. Eventually it will be fully dispersed, but the time
required for that to happen is highly dependent upon the amount of water
in the glass. In our case this means that it will be far more difficult
to fully scramble a face-turning 120 Cell compared to one where the
slices cut through the center. I find it interesting that the puzzles
that are more difficult to scramble seem to be the easiest to solve, and
vise versa. I now feel that I understand why.

My other thought about the Goldilocks formula is regarding the practical
applications to my problem. Even though a given puzzle may never be
practically scrambled this way, that doesn't let you off the hook. We
still need to at least choose a heuristic function, and some are better
than others. Here is the code that I currently use:

int totalTwistsNeededToFullyScramble =
puzzleManager.puzzleDescription.nFaces() // needed
twists is proportional to nFaces
*
(int)puzzleManager.puzzleDescription.getEdgeLength() // and to number of
slices
* 2; // and to a fudge factor that brings the 3^4
close to the original 40 twists.

It is simple, which is a good thing, but I am sure that it is far too
simple. The good news is that I don't need to know how many twists will
guarantee a well-scrambled puzzle. I only need a function that is "good
enough". For a function to be good enough, it needs to produce results
that appear to be fully scrambled, *and* that doesn't require an
impractical number of scrambling twists that would make the log files
impractically huge. My question for you then boils down to this: How
would you improve the above function to be more reasonable for any
puzzle the user might generate? I'm not looking for an optimal answer. I
just want an expert like yourself to advise me on how to improve my
clearly inadequate implementation. Of course maybe I should be asking
an engineer rather than a mathematician! :-)

As I was writing the above, it occurred to me that a practical solution
might relax the requirement of not bloating the log files with
scrambling twists. (You do get to suggest modifications to the
requirements if you feel they are over-constrained.) If the number of
twists needed for a decent scrambling is too large to be practical,
maybe we can just leave them out of the log file and just include the
resulting puzzle state. The previous log file format supported this, and
the scrambling twists were optional. That would mean that the "cheat"
version of the solve button will not be possible for those puzzles,
which is a limitation I'm sure we could live with. It even has the nice
feature of making it far harder for a solver to cheat.

Also, I *really* like your idea of manufacturing legitimately scrambled
states directly. I feel that this could be the best solution if it can
be implemented for the general case. I respect that you feel this would
be extremely difficult to do, and possibly even impossible for the
"build-your-own" option, so we can just let this idea sit until maybe
someone will think of a reasonably safe and practical implementation.

So for now, if you or anyone else have any suggestions for improving my
function above, please share them. Just remember that this is not a very
high priority feature, but it does deserve to be improved and would make
me happy.

-Melinda

On 4/30/2011 5:22 AM, David Smith wrote:
>
>
> Thank you so much Melinda! You are very gracious. :)
>
> I haven't browsed most of the messages I've missed (obviously there
> are a lot!), but after my reintroduction, I was immediately astounded
> by all of the new programs! 7-dimensional Rubik's Cubes? Magic
> Hyperbolic Tile? 5-dimensional Pac-man? 4-dimensional Tetris?!
> Incredible! I think Andrey deserves an award for being one of the
> talented programmers in the world, in the 'Creative Genius' category!
> And Roice provided the inspiration, being the first person to ever
> program a 5D Cube and Tile-based puzzles! (I'm sure he could do even
> more, but he is very busy!) And you and Don provided the inspiration
> for Roice, and this group. :)
>
> I feel so bad I missed out sharing the good times. But, it seems
> there are still plenty to be had! The only computer program I have
> written recently simulates Ulam's Game, a mathematical thought
> experiment. I believe it is the only one of its kind. But it was
> trivial to create; nothing even remotely close to what all of you have
> accomplished. I'm constantly inspired by your intelligence! And I
> forgot to mention that one day I do intend to work out solving these
> puzzles for myself.
>
> I've done some research into the Goldilocks function problem, and I
> have some bad news, and some worse news. :( The implications could be
> unfortunate, and you may wish I had never looked into it. It's up to
> all of you as to how you would like to proceed. I'm fine with keeping
> things as they are, and that what I am about to say may be considered
> questionable and irrelevant to our current scrambling methods.
>
> First, the bad news: This Goldilocks function is almost certainly
> beyond my capabilities. I'm betting a mathematician would have much
> trouble. The problem is that the number of moves it takes to produce
> a 'sufficiently random' position (which is already a subjective term;
> it can be made more precise mathematically, in a way that is somewhat
> above my head), varies from puzzle to puzzle. I doubt there is a
> general solution. Also, I doubt that it is practical to answer this
> question for any particular puzzle by purely mathematical methods,
> given the extreme difficulty. Computer tests need to be performed,
> i.e. scrambles need to be done repeatedly and analyzed with statistics.
>
> Here is the worse news: Such statistical analyses have already been
> performed for the 3^3 Cube and Megaminx. You can see the report on
> this page:
>
> http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/41005
>
> It is true that the results are not the work of a mathematician, and
> the analyses could have been simplified and improved upon, but I've
> studied the paper and there appear to be no errors. I believe that
> the results are accurate enough for our purposes.
>
> I originally conjectured that 20 moves would suffice to scramble the
> Rubik's Cube, since every position can be solved in at most 20 moves.
> This turns out to be a very naive and flawed assumption. According to
> the report, it takes around 45 moves to scramble a Rubik's Cube so
> that it is sufficiently random.
>
> Now, he also studied the megaminx. This is where things begin to get
> depressing. According to the page, it takes around 250 moves for the
> megaminx to begin to become randomly mixed. We can see the number of
> moves rapidly increasing with the complexity of the puzzle. The
> megaminx is simpler than even the standard 3^4 cube. So, I'm very
> roughly estimating that for a puzzle such as Magic120Cell, which is
> hugely complex, the number of moves required to generate a
> sufficiently random position could be in the hundred thousands,
> millions, or even higher!
>
> So, I feel that for the more complex puzzles, and perhaps even for the
> simpler ones, we have not performed anywhere near the necessary number
> of scrambling moves required. The solution to the question you asked
> me, i.e. how many moves it takes to generate sufficiently random
> positions on various puzzles, may be much, much higher than any of us
> previously thought, even for the puzzles we have all been enjoying for
> years now. I only see two solutions to this problem, and the second
> is my recommendation.
>
> First, we could reexamine the entire way we have been generating
> random positions. We could find a way to do so that does not involve
> twisting a random puzzle a certain number of times from the solved
> state, but rather generating a random permutation and orientation of
> all of the pieces. We then check (this is where my formulas would
> actually come in handy!) if each particular type of piece (they would
> be the 'families' in my NxNxNxN Cube permutation paper) satisfies the
> mathematical criteria for producing a solvable cube. If not, then we
> twist one of the pieces or swap two of them or both, depending on the
> situation.
>
> This method, however, has several obvious and significant drawbacks:
>
> 1. We would need to reprogram all of the scrambling mechanisms for
> every program (depending on who would accept to do so), which would be
> an arduous, lengthy and painstaking task.
>
> 2. The algorithm for doing so would be enormously complicated.
>
> 3. We would need to find the mathematical restrictions on the pieces
> of every type of puzzle available. This would involve a huge
> mathematical effort on my part, making us all very busy for months.
> Also, the 'create a puzzle' feature in MC4D 4.0 might have to be
> discarded.
>
> Now, here is the second option: we do nothing. Or, to put it in more
> optimistic terms, we reevaluate what 'sufficiently random' means to
> us, not what it means technically. We have all been enjoying all of
> your collective creations for many years now. We never realized the
> possibility that the scrambles are *technically* not close to random.
> From our point of view, it appears as if it is random. And maybe
> that's good enough for us. I'm betting that no one will have a
> problem with accepting that our puzzles, especially the more complex
> ones, may not be technically even close to random as we once thought,
> but that this knowledge in no way affects our enjoyment of solving the
> puzzle, or the difficulty we perceive. Indeed, we could probably
> never recognize the difference between 'technically sufficiently
> random' and 'practically sufficiently random' if we were presented
> with both. So, I would suggest simply using the maximum number of
> scrambles you feel you can reasonably employ, taking into
> consideration the sizes of the log files, for each puzzle. Maybe the
> puzzles with two pieces per edge could be less than the maximum. Of
> course, this maximum should vary for the complexity of each puzzle.
> It will be the best we can do, and it should certainly be sufficient.
>
> So, hopefully we can consider the Goldilocks function to not be of too
> much importance. You have already said yourself that it was of very
> low priority, so perhaps this lengthy dialogue was unnecessary. But I
> thought I would go into as much detail as possible, for the benefit of
> everyone.
>
> Thanks again for welcoming me back! It's good to be back. :) I now
> belong to many yahoo groups, but this was the first, and all of you
> were really my first true friends, honestly. It's a shame I made such
> a poor decision in leaving, and I regret it, but at least I've
> summoned the courage to come back and repair my mistake.
>
> Anyway, I hope my Goldilocks discussion was helpful, and I'm confident
> we don't need to modify the algorithms, as you most likely are as
> well. Have a great weekend, everyone! I'll be keeping in touch. :)
>
> All the best,
> David
>
>
>
> --- On *Sat, 4/30/11, Melinda Green //* wrote:
>
>
> From: Melinda Green
> Subject: Re: [MC4D] Hi everyone, I'm back!
> To: 4D_Cubing@yahoogroups.com
> Date: Saturday, April 30, 2011, 1:17 AM
>
> Hello David, and welcome home! :-)
>
> I was sad when you left, but mostly I was worried that you felt badly
> about somehow letting anybody down. So far as I know, you did nothing
> wrong nor let anybody down when you left. I don't need any
> explanations.
> Since you ask, the only thing that I could have made use of was the
> Goldilocks function we discussed but I never depended on you for that
> and it is of such low priority as to not matter. Please don't even
> think
> about it unless you want to do that for your own satisfaction.
> Everyone
> can come and go from this group as they please, and contribute
> what they
> like and change their mind at any time. As long as people are nice to
> each other and keep the discussions even vaguely on-topic, I'm
> perfectly
> happy. Of course I'm thrilled that you are back because you have been
> such a helpful resource in the past! Roice is perfectly correct.
> You are
> among friends.
>
> Have fun catching up! :-D
> -Melinda
>
> On 4/29/2011 3:47 PM, djs314djs314 wrote:
> > Hello my friends,
> >
> > First of all, I very deeply apologize for my inexplicable
> behavior when I suddenly and mysteriously left this group of very
> close friends over half a year ago. I have had some very serious
> issues going on in my life. In November I was hospitalized for a
> couple of weeks. To be a bit further ambiguous (sorry!), my
> departure was related to a symptom of my multiple illnesses. Of
> course, I can't blame a foolish, consciousness decision entirely
> on a symptom, and don't intend to. If any of you really want to
> know the whole story, I'll share it, but with some hesitation! :)
> Melinda, you probably deserve an explanation, so I will send one
> to you privately at your request. Again, I apologize for my
> behavior, but am very much looking forward to being an active
> member again, if you will have me.
> >
> > A very meaningful conversation with my good friend Roice
> inspired me to rejoin this group. I have wanted to for a while,
> but was honestly afraid of how everyone would respond. Roice
> helped me realize that I am among friends, and don't need to worry
> about such things.
> >
> > Well, I'm honestly thrilled to be back! :D I have so much to
> catch up on! I've only briefly scanned some of the recent
> messages, but I see that Magic120Cell and Klein's Quartic have
> some new solvers! And of course, there have been contests
> (blindfold solving?!) and new programs. I'll have to check out all
> that!
> >
> > Hopefully my reintroduction will inspire me to help out and
> contribute wherever I can. I would like to get back into the
> combinatorics of the puzzles. Specifically, I've been promising
> myself for quite a while to find the order of the 'n^d
> super-superhypercube group' (at least that is what I call it! :)
> ). A super-supercube is like a Rubik's Cube of any size in which
> every cubie is either on the surface or on the inside of the cube;
> the cube is solid. Any layer can be twisted. Also, each cubie has
> a unique identity and orientation (imagine that each face of each
> cubie has a unique integer associated to it). Obviously I don't
> need to expalin how this extends to higher dimensions. My goal is
> to find a formula for the number of visually ditinguishable
> permutations of a cube of arbitrary size,>= 2, and arbitrary
> dimension,>= 3, that can be produced by a sequence of legal moves
> from the solved position
> >
> > Also, there are so many other areas I could investigate. If
> Andrey would like, I can supply an explicit 7-dimensional formula
> for counting cube permutations, but that probably isn't necessary.
> (My general formula handles all dimensions, and who needs such a
> formula anyway? ;) ) There is also Klein's Quartic (if you guys
> haven't figured it out already), general MagicTile puzzles,
> general MagicCube4D 2.0 puzzles, etc. I know such efforts are not
> terribly important to the group, but they do provide me some
> satisfaction and I would be happy to provide any new formulas I find.
> >
> > My page of research has moved again, by the way, it is now here:
> >
> > http://seti.weebly.com/channel.html
> >
> > Amongst the materials are formulas for n^4, n^5, n^6, and n^d
> permutations, my Magic120Cell paper, my paper deriving the n^4
> formula, and a coloring result for Magic120Cell.
> >
> > I would also like to wish a warm welcome to any members who may
> have joined since my unfortunate departure. I wish you the best,
> and look forward to meeting you!
> >
> > And Melinda, I had previously promised to help you with some
> research for MagicCube4D 2.0. If you still require my assistance,
> I am ready to help as soon as possible.
> >
> > Thank you everyone so much for your understanding and patience.
> :) It's time for me to browse the messages and download some
> programs! I'll be writing again soon, and have a great day!
> >
> > All the best,
> > David
>
>
>
>

--------------080302050507090200020101
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable




">


Hello David,



Thank you for your kind words.



I know that you worry a lot about your place here and like others
before me, I want to assure you that there is no reason to doubt
that. Really, as long as you are nice to everybody and remain even
vaguely on-topic, you have nothing to worry about. Regarding lengthy
or frequent messages, everybody on the list is quite able to delete
messages that they are not interested in. If someone is not
interested in combinatorics, they can even filter out all messages
from you, and they shouldn't have the slightest guilt about doing
that. Of course you will want to avoid that as much as that is
within your control. For that, I suggest waiting 24 hours after
composing a long message, and rereading it before you hit "send".
That way you may realize some potential problems before posting.



I also agree with Roice that the best place to share detailed
calculations is in the wiki, so I'm glad that you are having fun
with that. You can then announce new sections as you feel they are
complete, and of course you can fix any mistakes later without even
announcing them. People can watch pages of interest to them, and
otherwise just look-up particular pages as needed and see the latest
data.



It is fascinating to remember all of the amazing puzzles and
interesting discussions that have transpired since you left.
Certainly this has been one of our richest periods especially due to
Andrey and Roice's contributions. There have been many times in the
past when I thought that maybe everything worthy of discussing in
this realm had already been discussed, but then something new and
interesting always crops up. That has happened so often that I no
longer think the stream of interesting puzzles and topics will ever
end. The group may go quiet for several months, but then something
completely unexpected crops up and we all get to watch it being
explored even if we don't participate in the discussion.



I have some thoughts to share regarding the Goldilocks function. The
first is that I had a small epiphany the other day while thinking
about the insights you gave. I now feel that I have a good feeling
for why the number of scrambling twists needed to fully scramble
some puzzles can be so amazingly high. Imagine the path of a single
piece during the scrambling process. If the puzzle is to be fully
scrambled, then that piece needs to be equally likely to end up in
any possible position. For a puzzle with a lot of faces (cells), a
given piece must be able to easily wander to the extreme opposite
side of the puzzle. Scrambling using random twists will cause that
piece to move around with something like Brownian motion which makes
it unlikely for any piece to move very far in just a few random
twists that affect it. The result is something like carefully
placing a single drop of ink into a glass of water and watching it
spread. Eventually it will be fully dispersed, but the time required
for that to happen is highly dependent upon the amount of water in
the glass. In our case this means that it will be far more difficult
to fully scramble a face-turning 120 Cell compared to one where the
slices cut through the center. I find it interesting that the
puzzles that are more difficult to scramble seem to be the easiest
to solve, and vise versa. I now feel that I understand why.



My other thought about the Goldilocks formula is regarding the
practical applications to my problem. Even though a given puzzle may
never be practically scrambled this way, that doesn't let you off
the hook. We still need to at least choose a heuristic function, and
some are better than others. Here is the code that I currently use:



=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 int totalTwistsNeededToFully=
Scramble =3D

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=
=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0 puzzleManager.puzzleDescription.nFaces()=
//
needed twists is proportional to nFaces

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=
=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0 *
(int)puzzleManager.puzzleDescription.getEdgeLength() // and to
number of slices

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=
=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0 * 2; // and to a fudge factor that bring=
s the
3^4 close to the original 40 twists.



It is simple, which is a good thing, but I am sure that it is far
too simple. The good news is that I don't need to know how many
twists will guarantee a well-scrambled puzzle. I only need a
function that is "good enough". For a function to be good enough, it
needs to produce results that appear to be fully scrambled, *and*
that doesn't require an impractical number of scrambling twists that
would make the log files impractically huge. My question for you
then boils down to this: How would you improve the above function to
be more reasonable for any puzzle the user might generate? I'm not
looking for an optimal answer. I just want an expert like yourself
to advise me on how to improve my clearly inadequate=C2=A0
implementation. Of course maybe I should be asking an engineer
rather than a mathematician!=C2=A0 :-)



As I was writing the above, it occurred to me that a practical
solution might relax the requirement of not bloating the log files
with scrambling twists. (You do get to suggest modifications to the
requirements if you feel they are over-constrained.) If the number
of twists needed for a decent scrambling is too large to be
practical, maybe we can just leave them out of the log file and just
include the resulting puzzle state. The previous log file format
supported this, and the scrambling twists were optional. That would
mean that the "cheat" version of the solve button will not be
possible for those puzzles, which is a limitation I'm sure we could
live with. It even has the nice feature of making it far harder for
a solver to cheat.



Also, I *really* like your idea of manufacturing legitimately
scrambled states directly. I feel that this could be the best
solution if it can be implemented for the general case. I respect
that you feel this would be extremely difficult to do, and possibly
even impossible for the "build-your-own" option, so we can just let
this idea sit until maybe someone will think of a reasonably safe
and practical implementation.



So for now, if you or anyone else have any suggestions for improving
my function above, please share them. Just remember that this is not
a very high priority feature, but it does deserve to be improved and
would make me happy.



-Melinda



On 4/30/2011 5:22 AM, David Smith wrote:

type=3D"cite">

Thank you so much Melinda!=C2=A0 You are very gracious. :) I haven't browsed most of the messages I've missed (obviously there are a lot!), but after my reintroduction, I was immediately astounded by all of the new programs!=C2=A0 7-dimensional Rubik's Cubes? Magic Hyperbolic Tile?=C2=A0 5-dimensional Pac-man?=C2=A0 4-dimensional Tetris?!=C2=A0 Incredible!=C2=A0 I think Andrey deserves an award for being one of the talented programmers in the world, in the 'Creative Genius' category!=C2=A0 And Roice provided the inspiration, being the first person to ever program a 5D Cube and Tile-based puzzles! (I'm sure he could do even more, but he is very busy!)=C2=A0 And you and Don provided th= e inspiration for Roice, and this group. :) I feel so bad I missed out sharing the good times.=C2=A0 But, it seems there are still plenty to be had!=C2=A0 The only computer program I have written recently simulates Ulam's Game, a mathematical thought experiment.=C2=A0 I believe it i= s the only one of its kind.=C2=A0 But it was trivial to create; nothing even remotely close to what all of you have accomplished.=C2=A0 I'm constantly inspired by your intelligence!=C2=A0 And I forgot to mention that one day I do intend to work out solving these puzzles for myself. I've done some research into the Goldilocks function problem, and I have some bad news, and some worse news. :(=C2=A0 The implications could be unfortunate, and you may wish I had never looked into it.=C2=A0 It's up to all of you = as to how you would like to proceed.=C2=A0 I'm fine with keeping things as they are, and that what I am about to say may be considered questionable and irrelevant to our current scrambling methods. First, the bad news: This Goldilocks function is almost certainly beyond my capabilities.=C2=A0 I'm betting a mathematician would have much trouble.=C2=A0 The problem is that the number of moves it takes to produce a 'sufficiently random' position (which is already a subjective term; it can be made more precise mathematically, in a way that is somewhat above my head), varies from puzzle to puzzle.=C2=A0 I doubt there is a genera= l solution.=C2=A0 Also, I doubt that it is practical to answer this question for any particular puzzle by purely mathematical methods, given the extreme difficulty.=C2=A0 Computer tests need to be performed, i.e. scrambles need to be done repeatedly and analyzed with statistics. Here is the worse news: Such statistical analyses have already been performed for the 3^3 Cube and Megaminx.=C2=A0 Y= ou can see the report on this page: oup/speedsolvingrubikscube/message/41005">http://games.groups.yahoo.com/gro= up/speedsolvingrubikscube/message/41005 It is true that the results are not the work of a mathematician, and the analyses could have been simplified and improved upon, but I've studied the paper and there appear to be no errors.=C2=A0 I believe that the results are accurate enough for our purposes. I originally conjectured that 20 moves would suffice to scramble the Rubik's Cube, since every position can be solved in at most 20 moves.=C2=A0 This turns out to be a very naive and flawed assumption.=C2=A0 According to the report, i= t takes around 45 moves to scramble a Rubik's Cube so that it is sufficiently random. Now, he also studied the megaminx.=C2=A0 This is where things begin to get depressing.=C2=A0 According to the page, it take= s around 250 moves for the megaminx to begin to become randomly mixed.=C2=A0 We can see the number of moves rapidly increasing with the complexity of the puzzle.=C2=A0 The megaminx is simpler than even the standard 3^4 cube.=C2=A0 So= , I'm very roughly estimating that for a puzzle such as Magic120Cell, which is hugely complex, the number of moves required to generate a sufficiently random position could be in the hundred thousands, millions, or even higher! So, I feel that for the more complex puzzles, and perhaps even for the simpler ones, we have not performed anywhere near the necessary number of scrambling moves required.=C2=A0 The solution to the question you asked me, i.e. how many moves it takes to generate sufficiently random positions on various puzzles, may be much, much higher than any of us previously thought, even for the puzzles we have all been enjoying for years now.=C2=A0 I only see two solutions t= o this problem, and the second is my recommendation. First, we could reexamine the entire way we have been generating random positions.=C2=A0 We could find a way to do = so that does not involve twisting a random puzzle a certain number of times from the solved state, but rather generating a random permutation and orientation of all of the pieces.=C2=A0 We then check (this is where my formulas would actually come in handy!) if each particular type of piece (they would be the 'families' in my NxNxNxN Cube permutation paper) satisfies the mathematical criteria for producing a solvable cube.=C2=A0 If not, then we twist one of the pieces or swap two of them or both, depending on the situation. This method, however, has several obvious and significant drawbacks: 1. We would need to reprogram all of the scrambling mechanisms for every program (depending on who would accept to do so), which would be an arduous, lengthy and painstaking task. 2. The algorithm for doing so would be enormously complicated. 3. We would need to find the mathematical restrictions on the pieces of every type of puzzle available.=C2=A0 This woul= d involve a huge mathematical effort on my part, making us all very busy for months.=C2=A0 Also, the 'create a puzzle' feature in MC4D 4.0 might have to be discarded. Now, here is the second option: we do nothing.=C2=A0 Or, to p= ut it in more optimistic terms, we reevaluate what 'sufficiently random' means to us, not what it means technically.=C2=A0 We have all been enjoying all of your collective creations for many years now.=C2=A0 We never realized the possibility that the scrambles are *technically* not close to random.=C2=A0 From our point of view, it appears as if it is random.=C2=A0 And maybe that's good enough for us.=C2=A0 I'm betting that no one will have a problem with accepting that our puzzles, especially the more complex ones, may not be technically even close to random as we once thought, but that this knowledge in no way affects our enjoyment of solving the puzzle, or the difficulty we perceive.=C2=A0 Indeed, we could probably never recognize the difference between 'technically sufficiently random' and 'practically sufficiently random' if we were presented with both.=C2=A0 So, I would suggest simply using t= he maximum number of scrambles you feel you can reasonably employ, taking into consideration the sizes of the log files, for each puzzle.=C2=A0 Maybe the puzzles with two piec= es per edge could be less than the maximum.=C2=A0 Of course, thi= s maximum should vary for the complexity of each puzzle.=C2=A0 = It will be the best we can do, and it should certainly be sufficient. So, hopefully we can consider the Goldilocks function to not be of too much importance.=C2=A0 You have already said yourself that it was of very low priority, so perhaps this lengthy dialogue was unnecessary.=C2=A0 But I thought I would go into as much detail as possible, for the benefit of everyone. Thanks again for welcoming me back!=C2=A0 It's good to be bac= k. :)=C2=A0 I now belong to many yahoo groups, but this was the first, and all of you were really my first true friends, honestly.=C2=A0 It's a shame I made such a poor decision in leaving, and I regret it, but at least I've summoned the courage to come back and repair my mistake. Anyway, I hope my Goldilocks discussion was helpful, and I'm confident we don't need to modify the algorithms, as you most likely are as well.=C2=A0 Have a great weekend, everyone!=C2=A0 I'll be keeping in touch. :) All the best, David --- On Sat, 4/30/11, Melinda Green link-rfc2396E" href=3D"mailto:melinda@superliminal.com"><melinda@superli= minal.com> wrote: 255); margin-left: 5px; padding-left: 5px;"> From: Melinda Green =3D"mailto:melinda@superliminal.com"><melinda@superliminal.com>r> Subject: Re: [MC4D] Hi everyone, I'm back! To: _Cubing@yahoogroups.com">4D_Cubing@yahoogroups.com Date: Saturday, April 30, 2011, 1:17 AM =C2=A0 Hello David, and welcome home! :-) I was sad when you left, but mostly I was worried that you felt badly about somehow letting anybody down. So far as I know, you did nothing wrong nor let anybody down when you left. I don't need any explanations. Since you ask, the only thing that I could have made use of was the Goldilocks function we discussed but I never depended on you for that and it is of such low priority as to not matter. Please don't even think about it unless you want to do that for your own satisfaction. Everyone can come and go from this group as they please, and contribute what they like and change their mind at any time. As long as people are nice to each other and keep the discussions even vaguely on-topic, I'm perfectly happy. Of course I'm thrilled that you are back because you have been such a helpful resource in the past! Roice is perfectly correct. You are among friends. Have fun catching up! :-D -Melinda On 4/29/2011 3:47 PM, djs314djs314 wrote: > Hello my friends, > > First of all, I very deeply apologize for my inexplicable behavior when I suddenly and mysteriously left this group of very close friends over half a year ago. I have had some very serious issues going on in my life. In November I was hospitalized for a couple of weeks. To be a bit further ambiguous (sorry!), my departure was related to a symptom of my multiple illnesses. Of course, I can't blame a foolish, consciousness decision entirely on a symptom, and don't intend to. If any of you really want to know the whole story, I'll share it, but with some hesitation! :) Melinda, you probably deserve an explanation, so I will send one to you privately at your request. Again, I apologize for my behavior, but am very much looking forward to being an active member again, if you will have me. > > A very meaningful conversation with my good friend Roice inspired me to rejoin this group. I have wanted to for a while, but was honestly afraid of how everyone would respond. Roice helped me realize that I am among friends, and don't need to worry about such things. > > Well, I'm honestly thrilled to be back! :D I have so much to catch up on! I've only briefly scanned some of the recent messages, but I see that Magic120Cell and Klein's Quartic have some new solvers! And of course, there have been contests (blindfold solving?!) and new programs. I'll have to check out all that! > > Hopefully my reintroduction will inspire me to help out and contribute wherever I can. I would like to get back into the combinatorics of the puzzles. Specifically, I've been promising myself for quite a while to find the order of the 'n^d super-superhypercube group' (at least that is what I call it! :) ). A super-supercube is like a Rubik's Cube of any size in which every cubie is either on the surface or on the inside of the cube; the cube is solid. Any layer can be twisted. Also, each cubie has a unique identity and orientation (imagine that each face of each cubie has a unique integer associated to it). Obviously I don't need to expalin how this extends to higher dimensions. My goal is to find a formula for the number of visually ditinguishable permutations of a cube of arbitrary size,>=3D 2, and arbitrary dimension,>=3D 3, that can be produced by a sequence of legal moves from the solved position > > Also, there are so many other areas I could investigate. If Andrey would like, I can supply an explicit 7-dimensional formula for counting cube permutations, but that probably isn't necessary. (My general formula handles all dimensions, and who needs such a formula anyway? ;) ) There is also Klein's Quartic (if you guys haven't figured it out already), general MagicTile puzzles, general MagicCube4D 2.0 puzzles, etc. I know such efforts are not terribly important to the group, but they do provide me some satisfaction and I would be happy to provide any new formulas I find.> > > My page of research has moved again, by the way, it is now here: > > target=3D"_blank" href=3D"http://seti.weebly.com/channel.html">http:/= /seti.weebly.com/channel.html > > Amongst the materials are formulas for n^4, n^5, n^6, and n^d permutations, my Magic120Cell paper, my paper deriving the n^4 formula, and a coloring result for Magic120Cell. > > I would also like to wish a warm welcome to any members who may have joined since my unfortunate departure. I wish you the best, and look forward to meeting you! > > And Melinda, I had previously promised to help you with some research for MagicCube4D 2.0. If you still require my assistance, I am ready to help as soon as possible. > > Thank you everyone so much for your understanding and patience. :) It's time for me to browse the messages and download some programs! I'll be writing again soon, and have a great day! > > All the best, > David

=20=20=20=20=20=20

--------------080302050507090200020101--

---

From: David Smith <djs314djs314@yahoo.com>
Date: Tue, 3 May 2011 17:53:30 -0700 (PDT)
Subject: Re: [MC4D] Hi everyone, I'm back!

=C2=A0



=20=20


=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20

=20=20
=20=20
Hello David,

=20=20=20=20

Thank you for your kind words.

=20=20=20=20

I know that you worry a lot about your place here and like others
before me, I want to assure you that there is no reason to doubt
that. Really, as long as you are nice to everybody and remain even
vaguely on-topic, you have nothing to worry about. Regarding lengthy
or frequent messages, everybody on the list is quite able to delete
messages that they are not interested in. If someone is not
interested in combinatorics, they can even filter out all messages
from you, and they shouldn't have the slightest guilt about doing
that. Of course you will want to avoid that as much as that is
within your control. For that, I suggest waiting 24 hours after
composing a long message, and rereading it before you hit "send".
That way you may realize some potential problems before posting.

=20=20=20=20

I also agree with Roice that the best place to share detailed
calculations is in the wiki, so I'm glad that you are having fun
with that. You can then announce new sections as you feel they are
complete, and of course you can fix any mistakes later without even
announcing them. People can watch pages of interest to them, and
otherwise just look-up particular pages as needed and see the latest
data.

=20=20=20=20

It is fascinating to remember all of the amazing puzzles and
interesting discussions that have transpired since you left.
Certainly this has been one of our richest periods especially due to
Andrey and Roice's contributions. There have been many times in the
past when I thought that maybe everything worthy of discussing in
this realm had already been discussed, but then something new and
interesting always crops up. That has happened so often that I no
longer think the stream of interesting puzzles and topics will ever
end. The group may go quiet for several months, but then something
completely unexpected crops up and we all get to watch it being
explored even if we don't participate in the discussion.

=20=20=20=20

I have some thoughts to share regarding the Goldilocks function. The
first is that I had a small epiphany the other day while thinking
about the insights you gave. I now feel that I have a good feeling
for why the number of scrambling twists needed to fully scramble
some puzzles can be so amazingly high. Imagine the path of a single
piece during the scrambling process. If the puzzle is to be fully
scrambled, then that piece needs to be equally likely to end up in
any possible position. For a puzzle with a lot of faces (cells), a
given piece must be able to easily wander to the extreme opposite
side of the puzzle. Scrambling using random twists will cause that
piece to move around with something like Brownian motion which makes
it unlikely for any piece to move very far in just a few random
twists that affect it. The result is something like carefully
placing a single drop of ink into a glass of water and watching it
spread. Eventually it will be fully dispersed, but the time required
for that to happen is highly dependent upon the amount of water in
the glass. In our case this means that it will be far more difficult
to fully scramble a face-turning 120 Cell compared to one where the
slices cut through the center. I find it interesting that the
puzzles that are more difficult to scramble seem to be the easiest
to solve, and vise versa. I now feel that I understand why.

=20=20=20=20

My other thought about the Goldilocks formula is regarding the
practical applications to my problem. Even though a given puzzle may
never be practically scrambled this way, that doesn't let you off
the hook. We still need to at least choose a heuristic function, and
some are better than others. Here is the code that I currently use:

=20=20=20=20

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 int totalTwistsNeededToFully=
Scramble =3D=20

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=
=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0 puzzleManager.puzzleDescription.nFaces()=
//
needed twists is proportional to nFaces

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=
=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0 *
(int)puzzleManager.puzzleDescription.getEdgeLength() // and to
number of slices

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=
=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0 * 2; // and to a fudge factor that bring=
s the
3^4 close to the original 40 twists.

=20=20=20=20

It is simple, which is a good thing, but I am sure that it is far
too simple. The good news is that I don't need to know how many
twists will guarantee a well-scrambled puzzle. I only need a
function that is "good enough". For a function to be good enough, it
needs to produce results that appear to be fully scrambled, *and*
that doesn't require an impractical number of scrambling twists that
would make the log files impractically huge. My question for you
then boils down to this: How would you improve the above function to
be more reasonable for any puzzle the user might generate? I'm not
looking for an optimal answer. I just want an expert like yourself
to advise me on how to improve my clearly inadequate=C2=A0
implementation. Of course maybe I should be asking an engineer
rather than a mathematician!=C2=A0 :-)

=20=20=20=20

As I was writing the above, it occurred to me that a practical
solution might relax the requirement of not bloating the log files
with scrambling twists. (You do get to suggest modifications to the
requirements if you feel they are over-constrained.) If the number
of twists needed for a decent scrambling is too large to be
practical, maybe we can just leave them out of the log file and just
include the resulting puzzle state. The previous log file format
supported this, and the scrambling twists were optional. That would
mean that the "cheat" version of the solve button will not be
possible for those puzzles, which is a limitation I'm sure we could
live with. It even has the nice feature of making it far harder for
a solver to cheat.

=20=20=20=20

Also, I *really* like your idea of manufacturing legitimately
scrambled states directly. I feel that this could be the best
solution if it can be implemented for the general case. I respect
that you feel this would be extremely difficult to do, and possibly
even impossible for the "build-your-own" option, so we can just let
this idea sit until maybe someone will think of a reasonably safe
and practical implementation.

=20=20=20=20

So for now, if you or anyone else have any suggestions for improving
my function above, please share them. Just remember that this is not
a very high priority feature, but it does deserve to be improved and
would make me happy.

=20=20=20=20

-Melinda

=20=20=20=20

On 4/30/2011 5:22 AM, David Smith wrote:
=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20
Thank you so much
Melinda!=C2=A0 You are very gracious. :)

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

I haven't browsed most of the messages I've missed
(obviously there are a lot!), but after my reintroduction,
I was immediately astounded by all of the new programs!=C2=A0
7-dimensional Rubik's Cubes? Magic Hyperbolic Tile?=C2=A0
5-dimensional Pac-man?=C2=A0 4-dimensional Tetris?!=C2=A0
Incredible!=C2=A0 I think Andrey deserves an award for being
one of the talented programmers in the world, in the
'Creative Genius' category!=C2=A0 And Roice provided the
inspiration, being the first person to ever program a 5D
Cube and Tile-based puzzles! (I'm sure he could do even
more, but he is very busy!)=C2=A0 And you and Don provided th=
e
inspiration for Roice, and this group. :)

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

I feel so bad I missed out sharing the good times.=C2=A0 But,
it seems there are still plenty to be had!=C2=A0 The only
computer program I have written recently simulates Ulam's
Game, a mathematical thought experiment.=C2=A0 I believe it i=
s
the only one of its kind.=C2=A0 But it was trivial to create;
nothing even remotely close to what all of you have
accomplished.=C2=A0 I'm constantly inspired by your
intelligence!=C2=A0 And I forgot to mention that one day I do
intend to work out solving these puzzles for myself.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

I've done some research into the Goldilocks function
problem, and I have some bad news, and some worse news.
:(=C2=A0 The implications could be unfortunate, and you may
wish I had never looked into it.=C2=A0 It's up to all of you =
as
to how you would like to proceed.=C2=A0 I'm fine with keeping
things as they are, and that what I am about to say may be
considered questionable and irrelevant to our current
scrambling methods.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

First, the bad news: This Goldilocks function is almost
certainly beyond my capabilities.=C2=A0 I'm betting a
mathematician would have much trouble.=C2=A0 The problem is
that the number of moves it takes to produce a
'sufficiently random' position (which is already a
subjective term; it can be made more precise
mathematically, in a way that is somewhat above my head),
varies from puzzle to puzzle.=C2=A0 I doubt there is a genera=
l
solution.=C2=A0 Also, I doubt that it is practical to answer
this question for any particular puzzle by purely
mathematical methods, given the extreme difficulty.=C2=A0
Computer tests need to be performed, i.e. scrambles need
to be done repeatedly and analyzed with statistics.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Here is the worse news: Such statistical analyses have
already been performed for the 3^3 Cube and Megaminx.=C2=A0 Y=
ou
can see the report on this page:

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/41005

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

It is true that the results are not the work of a
mathematician, and the analyses could have been simplified
and improved upon, but I've studied the paper and there
appear to be no errors.=C2=A0 I believe that the results are
accurate enough for our purposes.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

I originally conjectured that 20 moves would suffice to
scramble the Rubik's Cube, since every position can be
solved in at most 20 moves.=C2=A0 This turns out to be a very
naive and flawed assumption.=C2=A0 According to the report, i=
t
takes around 45 moves to scramble a Rubik's Cube so that
it is sufficiently random.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Now, he also studied the megaminx.=C2=A0 This is where things
begin to get depressing.=C2=A0 According to the page, it take=
s
around 250 moves for the megaminx to begin to become
randomly mixed.=C2=A0 We can see the number of moves rapidly
increasing with the complexity of the puzzle.=C2=A0 The
megaminx is simpler than even the standard 3^4 cube.=C2=A0 So=
,
I'm very roughly estimating that for a puzzle such as
Magic120Cell, which is hugely complex, the number of moves
required to generate a sufficiently random position could
be in the hundred thousands, millions, or even higher!

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

So, I feel that for the more complex puzzles, and perhaps
even for the simpler ones, we have not performed anywhere
near the necessary number of scrambling moves required.=C2=A0
The solution to the question you asked me, i.e. how many
moves it takes to generate sufficiently random positions
on various puzzles, may be much, much higher than any of
us previously thought, even for the puzzles we have all
been enjoying for years now.=C2=A0 I only see two solutions t=
o
this problem, and the second is my recommendation.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

First, we could reexamine the entire way we have been
generating random positions.=C2=A0 We could find a way to do =
so
that does not involve twisting a random puzzle a certain
number of times from the solved state, but rather
generating a random permutation and orientation of all of
the pieces.=C2=A0 We then check (this is where my formulas
would actually come in handy!) if each particular type of
piece (they would be the 'families' in my NxNxNxN Cube
permutation paper) satisfies the mathematical criteria for
producing a solvable cube.=C2=A0 If not, then we twist one of
the pieces or swap two of them or both, depending on the
situation.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

This method, however, has several obvious and significant
drawbacks:

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

1. We would need to reprogram all of the scrambling
mechanisms for every program (depending on who would
accept to do so), which would be an arduous, lengthy and
painstaking task.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

2. The algorithm for doing so would be enormously
complicated.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

3. We would need to find the mathematical restrictions on
the pieces of every type of puzzle available.=C2=A0 This woul=
d
involve a huge mathematical effort on my part, making us
all very busy for months.=C2=A0 Also, the 'create a puzzle'
feature in MC4D 4.0 might have to be discarded.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Now, here is the second option: we do nothing.=C2=A0 Or, to p=
ut
it in more optimistic terms, we reevaluate what
'sufficiently random' means to us, not what it means
technically.=C2=A0 We have all been enjoying all of your
collective creations for many years now.=C2=A0 We never
realized the possibility that the scrambles are
*technically* not close to random.=C2=A0 From our point of
view, it appears as if it is random.=C2=A0 And maybe that's
good enough for us.=C2=A0 I'm betting that no one will have a
problem with accepting that our puzzles, especially the
more complex ones, may not be technically even close to
random as we once thought, but that this knowledge in no
way affects our enjoyment of solving the puzzle, or the
difficulty we perceive.=C2=A0 Indeed, we could probably never
recognize the difference between 'technically sufficiently
random' and 'practically sufficiently random' if we were
presented with both.=C2=A0 So, I would suggest simply using t=
he
maximum number of scrambles you feel you can reasonably
employ, taking into consideration the sizes of the log
files, for each puzzle.=C2=A0 Maybe the puzzles with two piec=
es
per edge could be less than the maximum.=C2=A0 Of course, thi=
s
maximum should vary for the complexity of each puzzle.=C2=A0 =
It
will be the best we can do, and it should certainly be
sufficient.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

So, hopefully we can consider the Goldilocks function to
not be of too much importance.=C2=A0 You have already said
yourself that it was of very low priority, so perhaps this
lengthy dialogue was unnecessary.=C2=A0 But I thought I would
go into as much detail as possible, for the benefit of
everyone.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Thanks again for welcoming me back!=C2=A0 It's good to be bac=
k.
:)=C2=A0 I now belong to many yahoo groups, but this was the
first, and all of you were really my first true friends,
honestly.=C2=A0 It's a shame I made such a poor decision in
leaving, and I regret it, but at least I've summoned the
courage to come back and repair my mistake.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Anyway, I hope my Goldilocks discussion was helpful, and
I'm confident we don't need to modify the algorithms, as
you most likely are as well.=C2=A0 Have a great weekend,
everyone!=C2=A0 I'll be keeping in touch. :)

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

All the best,

David

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

--- On Sat, 4/30/11, Melinda Green
wrote:

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

From: Melinda Green

Subject: Re: [MC4D] Hi everyone, I'm back!

To: 4D_Cubing@yahoogroups.com

Date: Saturday, April 30, 2011, 1:17 AM

=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
=C2=A0
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
Hello David, and welcome home! :-)

=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

I was sad when you left, but mostly I was worried
that you felt badly=20

about somehow letting anybody down. So far as I
know, you did nothing=20

wrong nor let anybody down when you left. I don't
need any explanations.=20

Since you ask, the only thing that I could have
made use of was the=20

Goldilocks function we discussed but I never
depended on you for that=20

and it is of such low priority as to not matter.
Please don't even think=20

about it unless you want to do that for your own
satisfaction. Everyone=20

can come and go from this group as they please,
and contribute what they=20

like and change their mind at any time. As long as
people are nice to=20

each other and keep the discussions even vaguely
on-topic, I'm perfectly=20

happy. Of course I'm thrilled that you are back
because you have been=20

such a helpful resource in the past! Roice is
perfectly correct. You are=20

among friends.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Have fun catching up! :-D

-Melinda

=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

On 4/29/2011 3:47 PM, djs314djs314 wrote:

> Hello my friends,

>

> First of all, I very deeply apologize for my
inexplicable behavior when I suddenly and
mysteriously left this group of very close friends
over half a year ago. I have had some very serious
issues going on in my life. In November I was
hospitalized for a couple of weeks. To be a bit
further ambiguous (sorry!), my departure was
related to a symptom of my multiple illnesses. Of
course, I can't blame a foolish, consciousness
decision entirely on a symptom, and don't intend
to. If any of you really want to know the whole
story, I'll share it, but with some hesitation! :)
Melinda, you probably deserve an explanation, so I
will send one to you privately at your request.
Again, I apologize for my behavior, but am very
much looking forward to being an active member
again, if you will have me.

>

> A very meaningful conversation with my good
friend Roice inspired me to rejoin this group. I
have wanted to for a while, but was honestly
afraid of how everyone would respond. Roice helped
me realize that I am among friends, and don't need
to worry about such things.

>

> Well, I'm honestly thrilled to be back! :D I
have so much to catch up on! I've only briefly
scanned some of the recent messages, but I see
that Magic120Cell and Klein's Quartic have some
new solvers! And of course, there have been
contests (blindfold solving?!) and new programs.
I'll have to check out all that!

>

> Hopefully my reintroduction will inspire me
to help out and contribute wherever I can. I would
like to get back into the combinatorics of the
puzzles. Specifically, I've been promising myself
for quite a while to find the order of the 'n^d
super-superhypercube group' (at least that is what
I call it! :) ). A super-supercube is like a
Rubik's Cube of any size in which every cubie is
either on the surface or on the inside of the
cube; the cube is solid. Any layer can be twisted.
Also, each cubie has a unique identity and
orientation (imagine that each face of each cubie
has a unique integer associated to it). Obviously
I don't need to expalin how this extends to higher
dimensions. My goal is to find a formula for the
number of visually ditinguishable permutations of
a cube of arbitrary size,>=3D 2, and arbitrary
dimension,>=3D 3, that can be produced by a
sequence of legal moves from the solved position

>

> Also, there are so many other areas I could
investigate. If Andrey would like, I can supply an
explicit 7-dimensional formula for counting cube
permutations, but that probably isn't necessary.
(My general formula handles all dimensions, and
who needs such a formula anyway? ;) ) There is
also Klein's Quartic (if you guys haven't figured
it out already), general MagicTile puzzles,
general MagicCube4D 2.0 puzzles, etc. I know such
efforts are not terribly important to the group,
but they do provide me some satisfaction and I
would be happy to provide any new formulas I find.

>

> My page of research has moved again, by the
way, it is now here:

>

> http://seti.weebly.com/channel.html

>

> Amongst the materials are formulas for n^4,
n^5, n^6, and n^d permutations, my Magic120Cell
paper, my paper deriving the n^4 formula, and a
coloring result for Magic120Cell.

>

> I would also like to wish a warm welcome to
any members who may have joined since my
unfortunate departure. I wish you the best, and
look forward to meeting you!

>

> And Melinda, I had previously promised to
help you with some research for MagicCube4D 2.0.
If you still require my assistance, I am ready to
help as soon as possible.

>

> Thank you everyone so much for your
understanding and patience. :) It's time for me to
browse the messages and download some programs!
I'll be writing again soon, and have a great day!

>

> All the best,

> David

=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20
=20=20



=20=20=20=20
=20=20=20=20=20

=20=20=20=20
=20=20=20=20


=20



=20=20




--0-1355284027-1304470410=:80482
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">Hi Melinda, Thanks for your reassuranc= e that I belong here!  I know I can be a bit of a downer on myself = sometimes, and will try to stay more positive in the future. :)  Ther>less time people have to spend reassuring me, that's less time wasted!&nb= sp; And thanks for the good advice regarding sending long or mathematica= lly detailed messages, as well.  And I agree that the wiki is a gre= at idea.  I'm hoping that some of you find my efforts enjoyable and= /or useful. Yes, it appears I must have missed out on a whole lot of= great times.  Shame on me!  At least I'm back, and I'm defini= tely going to make the best of it, and contribute as much as I can. <= br>Speaking of contributing, permutations are good and all, but I'd really = like to help in a more significant way.  And so I'm delighted to he= ar that you have some ideas for how I can contribute with the Goldilocks f= unction! (I like your Brownian motion explanation, by the way.  It = is even more clear when one considers that for any particular piece, the= vast majority of random face turns won't even move it, much less get it= equally likely to be in any position!  And by symmetry, we can say= the puzzle is fully scrambled when a single piece is equally likely to = be anywhere after random face turns.)  I certainly didn't feel off the= hook before, it was more of a let-down!  Now I'm very glad you hav= e clarified that I will be able to help with this. :) Before, I d= idn't actually realize that the very low number of twists, compared to t= he number needed to randomize the puzzle, had a noticeable impact on the pu= zzle solving, but now I'm hearing that it does.  And wouldn't it be= wonderful to have a truly scrambled puzzle?  I'm truly happy that you love the idea of generating completely scrambled puzzles= .  I've been thinking about it, and I believe we can make it work, = possibly even for the create your own puzzle option!  In my earlier>post, I was mostly concerned with you as the programmers, having to modify= your code too much.  But if you willing to do so for such a huge b= enefit, I can try and make it work.  It would be a great contributi= on!  When finding my formulas, the hard part nowadays is in countin= g the number of pieces of every family.  The easy part is actually = finding the restrictions, and I may be able to do so for any puzzle give= n the Schlafli symbol.  As I mentioned in my previous post about ther>corner algorithm, I have a systematic method for determining permutation = and orientation restrictions of any puzzle very quickly and easily. = ; I'll write up the complete algorithm is pseudocode, once I finish, and then we'll see if you think it's worth implementing. >There might be a difficulty in implementing such a scrambling method forr>pieces called wings (see the wiki for an explanation; it's a bit lengthy)= , however. You might need to modify your code so you know which pieces a= re wings and which are normals as you generate them.  But in any ca= se, I'm confident at this point that I can come up with an algorithm.> Thanks a lot for writing, and I look forward to assisting you! = All the best, David --- On Tue, 5/3/11, Melinda Green &= lt;melinda@superliminal.com> wrote: er-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;">= From: Melinda Green <melinda@superliminal.com> Subject: Re: [M= C4D] Hi everyone, I'm back! To: 4D_Cubing@yahoogroups.com Date: Tuesd= ay, May 3, 2011, 6:26 PM   =20=20=20=20=20=20 =20=20=20=20=20=20 =20=20 =20=20 Hello David, Thank you for your kind words. I know that you worry a lot about your place here and like others before me, I want to assure you that there is no reason to doubt that. Really, as long as you are nice to everybody and remain even vaguely on-topic, you have nothing to worry about. Regarding lengthy or frequent messages, everybody on the list is quite able to delete messages that they are not interested in. If someone is not interested in combinatorics, they can even filter out all messages from you, and they shouldn't have the slightest guilt about doing that. Of course you will want to avoid that as much as that is within your control. For that, I suggest waiting 24 hours after composing a long message, and rereading it before you hit "send". That way you may realize some potential problems before posting. I also agree with Roice that the best place to share detailed calculations is in the wiki, so I'm glad that you are having fun with that. You can then announce new sections as you feel they are complete, and of course you can fix any mistakes later without even announcing them. People can watch pages of interest to them, and otherwise just look-up particular pages as needed and see the latest data. It is fascinating to remember all of the amazing puzzles and interesting discussions that have transpired since you left. Certainly this has been one of our richest periods especially due to Andrey and Roice's contributions. There have been many times in the past when I thought that maybe everything worthy of discussing in this realm had already been discussed, but then something new and interesting always crops up. That has happened so often that I no longer think the stream of interesting puzzles and topics will ever end. The group may go quiet for several months, but then something completely unexpected crops up and we all get to watch it being explored even if we don't participate in the discussion. I have some thoughts to share regarding the Goldilocks function. The first is that I had a small epiphany the other day while thinking about the insights you gave. I now feel that I have a good feeling for why the number of scrambling twists needed to fully scramble some puzzles can be so amazingly high. Imagine the path of a single piece during the scrambling process. If the puzzle is to be fully scrambled, then that piece needs to be equally likely to end up in any possible position. For a puzzle with a lot of faces (cells), a given piece must be able to easily wander to the extreme opposite side of the puzzle. Scrambling using random twists will cause that piece to move around with something like Brownian motion which makes it unlikely for any piece to move very far in just a few random twists that affect it. The result is something like carefully placing a single drop of ink into a glass of water and watching it spread. Eventually it will be fully dispersed, but the time required for that to happen is highly dependent upon the amount of water in the glass. In our case this means that it will be far more difficult to fully scramble a face-turning 120 Cell compared to one where the slices cut through the center. I find it interesting that the puzzles that are more difficult to scramble seem to be the easiest to solve, and vise versa. I now feel that I understand why. My other thought about the Goldilocks formula is regarding the practical applications to my problem. Even though a given puzzle may never be practically scrambled this way, that doesn't let you off the hook. We still need to at least choose a heuristic function, and some are better than others. Here is the code that I currently use:         int totalTwistsNeededToFully= Scramble =3D             &nbs= p;       puzzleManager.puzzleDescription.nFaces() = // needed twists is proportional to nFaces             &nbs= p;       * (int)puzzleManager.puzzleDescription.getEdgeLength() // and to number of slices             &nbs= p;       * 2; // and to a fudge factor that brings= the 3^4 close to the original 40 twists. It is simple, which is a good thing, but I am sure that it is far too simple. The good news is that I don't need to know how many twists will guarantee a well-scrambled puzzle. I only need a function that is "good enough". For a function to be good enough, it needs to produce results that appear to be fully scrambled, *and* that doesn't require an impractical number of scrambling twists that would make the log files impractically huge. My question for you then boils down to this: How would you improve the above function to be more reasonable for any puzzle the user might generate? I'm not looking for an optimal answer. I just want an expert like yourself to advise me on how to improve my clearly inadequate  implementation. Of course maybe I should be asking an engineer rather than a mathematician!  :-) As I was writing the above, it occurred to me that a practical solution might relax the requirement of not bloating the log files with scrambling twists. (You do get to suggest modifications to the requirements if you feel they are over-constrained.) If the number of twists needed for a decent scrambling is too large to be practical, maybe we can just leave them out of the log file and just include the resulting puzzle state. The previous log file format supported this, and the scrambling twists were optional. That would mean that the "cheat" version of the solve button will not be possible for those puzzles, which is a limitation I'm sure we could live with. It even has the nice feature of making it far harder for a solver to cheat. Also, I *really* like your idea of manufacturing legitimately scrambled states directly. I feel that this could be the best solution if it can be implemented for the general case. I respect that you feel this would be extremely difficult to do, and possibly even impossible for the "build-your-own" option, so we can just let this idea sit until maybe someone will think of a reasonably safe and practical implementation. So for now, if you or anyone else have any suggestions for improving my function above, please share them. Just remember that this is not a very high priority feature, but it does deserve to be improved and would make me happy. -Melinda On 4/30/2011 5:22 AM, David Smith wrote: =20=20=20=20=20=20 =20=20=20=20=20=20 Thank you so much Melinda!  You are very gracious. :) I haven't browsed most of the messages I've missed (obviously there are a lot!), but after my reintroduction, I was immediately astounded by all of the new programs!  7-dimensional Rubik's Cubes? Magic Hyperbolic Tile?  5-dimensional Pac-man?  4-dimensional Tetris?!  Incredible!  I think Andrey deserves an award for being one of the talented programmers in the world, in the 'Creative Genius' category!  And Roice provided the inspiration, being the first person to ever program a 5D Cube and Tile-based puzzles! (I'm sure he could do even more, but he is very busy!)  And you and Don provided th= e inspiration for Roice, and this group. :) I feel so bad I missed out sharing the good times.  But, it seems there are still plenty to be had!  The only computer program I have written recently simulates Ulam's Game, a mathematical thought experiment.  I believe it i= s the only one of its kind.  But it was trivial to create; nothing even remotely close to what all of you have accomplished.  I'm constantly inspired by your intelligence!  And I forgot to mention that one day I do intend to work out solving these puzzles for myself. I've done some research into the Goldilocks function problem, and I have some bad news, and some worse news. :(  The implications could be unfortunate, and you may wish I had never looked into it.  It's up to all of you = as to how you would like to proceed.  I'm fine with keeping things as they are, and that what I am about to say may be considered questionable and irrelevant to our current scrambling methods. First, the bad news: This Goldilocks function is almost certainly beyond my capabilities.  I'm betting a mathematician would have much trouble.  The problem is that the number of moves it takes to produce a 'sufficiently random' position (which is already a subjective term; it can be made more precise mathematically, in a way that is somewhat above my head), varies from puzzle to puzzle.  I doubt there is a genera= l solution.  Also, I doubt that it is practical to answer this question for any particular puzzle by purely mathematical methods, given the extreme difficulty.  Computer tests need to be performed, i.e. scrambles need to be done repeatedly and analyzed with statistics. Here is the worse news: Such statistical analyses have already been performed for the 3^3 Cube and Megaminx.  Y= ou can see the report on this page: _blank" href=3D"http://games.groups.yahoo.com/group/speedsolvingrubikscube/= message/41005">http://games.groups.yahoo.com/group/speedsolvingrubikscube/m= essage/41005 It is true that the results are not the work of a mathematician, and the analyses could have been simplified and improved upon, but I've studied the paper and there appear to be no errors.  I believe that the results are accurate enough for our purposes. I originally conjectured that 20 moves would suffice to scramble the Rubik's Cube, since every position can be solved in at most 20 moves.  This turns out to be a very naive and flawed assumption.  According to the report, i= t takes around 45 moves to scramble a Rubik's Cube so that it is sufficiently random. Now, he also studied the megaminx.  This is where things begin to get depressing.  According to the page, it take= s around 250 moves for the megaminx to begin to become randomly mixed.  We can see the number of moves rapidly increasing with the complexity of the puzzle.  The megaminx is simpler than even the standard 3^4 cube.  So= , I'm very roughly estimating that for a puzzle such as Magic120Cell, which is hugely complex, the number of moves required to generate a sufficiently random position could be in the hundred thousands, millions, or even higher! So, I feel that for the more complex puzzles, and perhaps even for the simpler ones, we have not performed anywhere near the necessary number of scrambling moves required.  The solution to the question you asked me, i.e. how many moves it takes to generate sufficiently random positions on various puzzles, may be much, much higher than any of us previously thought, even for the puzzles we have all been enjoying for years now.  I only see two solutions t= o this problem, and the second is my recommendation. First, we could reexamine the entire way we have been generating random positions.  We could find a way to do = so that does not involve twisting a random puzzle a certain number of times from the solved state, but rather generating a random permutation and orientation of all of the pieces.  We then check (this is where my formulas would actually come in handy!) if each particular type of piece (they would be the 'families' in my NxNxNxN Cube permutation paper) satisfies the mathematical criteria for producing a solvable cube.  If not, then we twist one of the pieces or swap two of them or both, depending on the situation. This method, however, has several obvious and significant drawbacks: 1. We would need to reprogram all of the scrambling mechanisms for every program (depending on who would accept to do so), which would be an arduous, lengthy and painstaking task. 2. The algorithm for doing so would be enormously complicated. 3. We would need to find the mathematical restrictions on the pieces of every type of puzzle available.  This woul= d involve a huge mathematical effort on my part, making us all very busy for months.  Also, the 'create a puzzle' feature in MC4D 4.0 might have to be discarded. Now, here is the second option: we do nothing.  Or, to p= ut it in more optimistic terms, we reevaluate what 'sufficiently random' means to us, not what it means technically.  We have all been enjoying all of your collective creations for many years now.  We never realized the possibility that the scrambles are *technically* not close to random.  From our point of view, it appears as if it is random.  And maybe that's good enough for us.  I'm betting that no one will have a problem with accepting that our puzzles, especially the more complex ones, may not be technically even close to random as we once thought, but that this knowledge in no way affects our enjoyment of solving the puzzle, or the difficulty we perceive.  Indeed, we could probably never recognize the difference between 'technically sufficiently random' and 'practically sufficiently random' if we were presented with both.  So, I would suggest simply using t= he maximum number of scrambles you feel you can reasonably employ, taking into consideration the sizes of the log files, for each puzzle.  Maybe the puzzles with two piec= es per edge could be less than the maximum.  Of course, thi= s maximum should vary for the complexity of each puzzle.  = It will be the best we can do, and it should certainly be sufficient. So, hopefully we can consider the Goldilocks function to not be of too much importance.  You have already said yourself that it was of very low priority, so perhaps this lengthy dialogue was unnecessary.  But I thought I would go into as much detail as possible, for the benefit of everyone. Thanks again for welcoming me back!  It's good to be bac= k. :)  I now belong to many yahoo groups, but this was the first, and all of you were really my first true friends, honestly.  It's a shame I made such a poor decision in leaving, and I regret it, but at least I've summoned the courage to come back and repair my mistake. Anyway, I hope my Goldilocks discussion was helpful, and I'm confident we don't need to modify the algorithms, as you most likely are as well.  Have a great weekend, everyone!  I'll be keeping in touch. :) All the best, David --- On Sat, 4/30/11, Melinda Green class=3D"yiv1694461136moz-txt-link-rfc2396E" ymailto=3D"mailto:melinda@supe= rliminal.com" target=3D"_blank" href=3D"/mc/compose?to=3Dmelinda@superlimin= al.com"><melinda@superliminal.com> wrote: "> From: Melinda Green 136moz-txt-link-rfc2396E" ymailto=3D"mailto:melinda@superliminal.com" targe= t=3D"_blank" href=3D"/mc/compose?to=3Dmelinda@superliminal.com"><melinda= @superliminal.com> Subject: Re: [MC4D] Hi everyone, I'm back! To: abbreviated" ymailto=3D"mailto:4D_Cubing@yahoogroups.com" target=3D"_blank"= href=3D"/mc/compose?to=3D4D_Cubing@yahoogroups.com">4D_Cubing@yahoogroups.= com Date: Saturday, April 30, 2011, 1:17 AM   Hello David, and welcome home! :-) I was sad when you left, but mostly I was worried that you felt badly about somehow letting anybody down. So far as I know, you did nothing wrong nor let anybody down when you left. I don't need any explanations. Since you ask, the only thing that I could have made use of was the Goldilocks function we discussed but I never depended on you for that and it is of such low priority as to not matter. Please don't even think about it unless you want to do that for your own satisfaction. Everyone can come and go from this group as they please, and contribute what they like and change their mind at any time. As long as people are nice to each other and keep the discussions even vaguely on-topic, I'm perfectly happy. Of course I'm thrilled that you are back because you have been such a helpful resource in the past! Roice is perfectly correct. You are among friends. Have fun catching up! :-D -Melinda On 4/29/2011 3:47 PM, djs314djs314 wrote: > Hello my friends, > > First of all, I very deeply apologize for my inexplicable behavior when I suddenly and mysteriously left this group of very close friends over half a year ago. I have had some very serious issues going on in my life. In November I was hospitalized for a couple of weeks. To be a bit further ambiguous (sorry!), my departure was related to a symptom of my multiple illnesses. Of course, I can't blame a foolish, consciousness decision entirely on a symptom, and don't intend to. If any of you really want to know the whole story, I'll share it, but with some hesitation! :) Melinda, you probably deserve an explanation, so I will send one to you privately at your request. Again, I apologize for my behavior, but am very much looking forward to being an active member again, if you will have me. > > A very meaningful conversation with my good friend Roice inspired me to rejoin this group. I have wanted to for a while, but was honestly afraid of how everyone would respond. Roice helped me realize that I am among friends, and don't need to worry about such things. > > Well, I'm honestly thrilled to be back! :D I have so much to catch up on! I've only briefly scanned some of the recent messages, but I see that Magic120Cell and Klein's Quartic have some new solvers! And of course, there have been contests (blindfold solving?!) and new programs. I'll have to check out all that! > > Hopefully my reintroduction will inspire me to help out and contribute wherever I can. I would like to get back into the combinatorics of the puzzles. Specifically, I've been promising myself for quite a while to find the order of the 'n^d super-superhypercube group' (at least that is what I call it! :) ). A super-supercube is like a Rubik's Cube of any size in which every cubie is either on the surface or on the inside of the cube; the cube is solid. Any layer can be twisted. Also, each cubie has a unique identity and orientation (imagine that each face of each cubie has a unique integer associated to it). Obviously I don't need to expalin how this extends to higher dimensions. My goal is to find a formula for the number of visually ditinguishable permutations of a cube of arbitrary size,>=3D 2, and arbitrary dimension,>=3D 3, that can be produced by a sequence of legal moves from the solved position > > Also, there are so many other areas I could investigate. If Andrey would like, I can supply an explicit 7-dimensional formula for counting cube permutations, but that probably isn't necessary. (My general formula handles all dimensions, and who needs such a formula anyway? ;) ) There is also Klein's Quartic (if you guys haven't figured it out already), general MagicTile puzzles, general MagicCube4D 2.0 puzzles, etc. I know such efforts are not terribly important to the group, but they do provide me some satisfaction and I would be happy to provide any new formulas I find.> > > My page of research has moved again, by the way, it is now here: > > tp://seti.weebly.com/channel.html">http://seti.weebly.com/channel.html<= br> > > Amongst the materials are formulas for n^4, n^5, n^6, and n^d permutations, my Magic120Cell paper, my paper deriving the n^4 formula, and a coloring result for Magic120Cell. > > I would also like to wish a warm welcome to any members who may have joined since my unfortunate departure. I wish you the best, and look forward to meeting you! > > And Melinda, I had previously promised to help you with some research for MagicCube4D 2.0. If you still require my assistance, I am ready to help as soon as possible. > > Thank you everyone so much for your understanding and patience. :) It's time for me to browse the messages and download some programs! I'll be writing again soon, and have a great day! > > All the best, > David =20=20=20=20=20=20 =20=20 =20=20=20=20=20 =20

--0-1355284027-1304470410=:80482--

---

From: Melinda Green <melinda@superliminal.com>
Date: Tue, 03 May 2011 21:43:59 -0700
Subject: Re: [MC4D] Hi everyone, I'm back!

--------------060308080002060607080607
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit



On 5/3/2011 5:53 PM, David Smith wrote:
>
>
> [...]
>
>
> Before, I didn't actually realize that the very low number of twists,
> compared to
> the number needed to randomize the puzzle, had a noticeable impact on
> the puzzle
> solving, but now I'm hearing that it does.
>

I'm not saying that it does, but for some cases I can imagine that it would.

> And wouldn't it be wonderful to have
> a truly scrambled puzzle? I'm truly happy that you love the idea of
> generating
> completely scrambled puzzles. I've been thinking about it, and I
> believe we can
> make it work, possibly even for the create your own puzzle option! In
> my earlier
> post, I was mostly concerned with you as the programmers, having to
> modify your
> code too much. But if you willing to do so for such a huge benefit, I
> can try
> and make it work. It would be a great contribution! When finding my
> formulas,
> the hard part nowadays is in counting the number of pieces of every
> family. The
> easy part is actually finding the restrictions, and I may be able to
> do so for any
> puzzle given the Schlafli symbol. As I mentioned in my previous post
> about the
> corner algorithm, I have a systematic method for determining
> permutation and
> orientation restrictions of any puzzle very quickly and easily. I'll
> write up the
> complete algorithm is pseudocode, once I finish, and then we'll see if
> you think
> it's worth implementing.
>

I just want to be clear here that although I really like your idea of a
truly general Schlafli-based method of scrambling by reassembly, I will
also be very happy with simply a smarter replacement for my simplistic
code I included earlier. Each method addresses a related but different
problem.

Also, I may not be ready for a big coding exercise on this right away
even if you do come up with the pseudo-code. That also sounds more
within Roice's sphere, but I don't want to pressure him to do anything
either. The good news is that we have exactly the right place to record
these sorts of coding possibilities, which is in the issue tracker. You
can simply create a new issue and drop your pseudo-code in there for
someone to pick up when they feel inspired.

I also want to be even more clear that I don't consider you to be on any
hook at all. I shouldn't have phrased it that way. You won't be letting
anyone down even if you do nothing on this. It just seems like a fun
task for you which could lead to some nice additions to the code.

-Melinda

--------------060308080002060607080607
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable




">






On 5/3/2011 5:53 PM, David Smith wrote:

type=3D"cite">

[...]

type=3D"cite">

Before, I didn't actually realize that the very low number of twists, compared to the number needed to randomize the puzzle, had a noticeable impact on the puzzle solving, but now I'm hearing that it does.=C2=A0

I'm not saying that it does, but for some cases I can imagine that
it would.

type=3D"cite">

And wouldn't it be wonderful to have a truly scrambled puzzle?=C2=A0 I'm truly happy that you love the idea of generating completely scrambled puzzles.=C2=A0 I've been thinking about it, and I believe we can make it work, possibly even for the create your own puzzle option!=C2=A0 In my earlier post, I was mostly concerned with you as the programmers, having to modify your code too much.=C2=A0 But if you willing to do so for such a huge benefit, I can try and make it work.=C2=A0 It would be a great contribution!=C2= =A0 When finding my formulas, the hard part nowadays is in counting the number of pieces of every family.=C2=A0 The easy part is actually finding the restrictions, and I may be able to do so for any puzzle given the Schlafli symbol.=C2=A0 As I mentioned in my previous post about the corner algorithm, I have a systematic method for determining permutation and orientation restrictions of any puzzle very quickly and easily.=C2=A0 I'll write up the complete algorithm is pseudocode, once I finish, and then we'll see if you think it's worth implementing.

I just want to be clear here that although I really like your idea
of a truly general Schlafli-based method of scrambling by
reassembly, I will also be very happy with simply a smarter
replacement for my simplistic code I included earlier. Each method
addresses a related but different problem.



Also, I may not be ready for a big coding exercise on this right
away even if you do come up with the pseudo-code. That also sounds
more within Roice's sphere, but I don't want to pressure him to do
anything either. The good news is that we have exactly the right
place to record these sorts of coding possibilities, which is in the
issue tracker. You can simply create a new issue and drop your
pseudo-code in there for someone to pick up when they feel inspired.>


I also want to be even more clear that I don't consider you to be on
any hook at all. I shouldn't have phrased it that way. You won't be
letting anyone down even if you do nothing on this. It just seems
like a fun task for you which could lead to some nice additions to
the code.



-Melinda




--------------060308080002060607080607--

---

From: "Andrey" <andreyastrelin@yahoo.com>
Date: Wed, 04 May 2011 05:50:18 -0000
Subject: Re: [MC4D] Hi everyone, I'm back!

Hi all,
If we estimate number of twists for fully scrambled puzzle by its number =
of states, the simplest formula may be like this:

N=3Dlog(number_of_colors)/log(number_of_possible_twists)*number_of_stickers=
.

Here we count all "chemically" possible paintings of the puzzle. Their numb=
er is not much more than number of the possible states (for 120-cell it's c=
lose to the square of the number of states). So we have some reserve for "B=
rownian motion" in the graph of possible states, and it should be enough fo=
r practical purposes. For 7^5 it gives 66000 twists, but for smaller puzzle=
s results are more acceptable:

3^4: 80
4^4: 180
5^4: 350
3^5: 360
120-cell: 4000
{3}x{3}, 3 layers: 64

But in my new program I'll use something more simple: N=3D1000 :)

Andrey

---

From: Melinda Green <melinda@superliminal.com>
Date: Wed, 04 May 2011 00:36:05 -0700
Subject: Re: [MC4D] Hi everyone, I'm back!

Well, if Andrey is backing away from this problem, then it must be more
problematic than I first supposed! ;-)

I don't quite accept the idea that the number of puzzle states is a good
proxy for the number of scrambling twists needed to fully scramble.
Consider the 4D megaminx (AKA 120 Cell) compared with the 4D pyraminx
crystal. It seems as if they might both have roughly the same number of
possible states, but I feel that the first will be much harder to
scramble than the second because it is far less internally connected.
It's as if in the first case, a given piece must stumble it's way all
the way around a roughly spherical surface whereas the in the second
case, pieces can move "through" the sphere and quickly find themselves
just about anywhere.

-Melinda

On 5/3/2011 10:50 PM, Andrey wrote:
> Hi all,
> If we estimate number of twists for fully scrambled puzzle by its number of states, the simplest formula may be like this:
>
> N=log(number_of_colors)/log(number_of_possible_twists)*number_of_stickers.
>
> Here we count all "chemically" possible paintings of the puzzle. Their number is not much more than number of the possible states (for 120-cell it's close to the square of the number of states). So we have some reserve for "Brownian motion" in the graph of possible states, and it should be enough for practical purposes. For 7^5 it gives 66000 twists, but for smaller puzzles results are more acceptable:
>
> 3^4: 80
> 4^4: 180
> 5^4: 350
> 3^5: 360
> 120-cell: 4000
> {3}x{3}, 3 layers: 64
>
> But in my new program I'll use something more simple: N=1000 :)
>
> Andrey

---

From: "Andrey" <andreyastrelin@yahoo.com>
Date: Wed, 04 May 2011 09:28:19 -0000
Subject: Re: [MC4D] Hi everyone, I'm back!

Melinda,
May be, you are right. I don't know the structure of 4D pyraminx crystal,=
but I made an experiment on 120-cell.=20
Take one 2C piece. A random twist moves one of its cells with probability=
1/60, so in 2000-twist sequence it will be moved about 33 times. It can ta=
ke one of 1440 positions+orientations, and it's not difficult to find a dis=
tribution of its states after a number of twists.
I can say that after 33 moves touching the piece its probabilities will b=
e distributed from 0.869/1440 (positions on the opposite cell) to 1.133/144=
0 (on the same cell where it started). For me it's random enough. After 67 =
moves (=3D4000 twists of the puzzle) it will vary from 0.9957/1440 to 1.004=
3/1440.=20
But after 1000-twist scramble there are 4 times more chance of the piece =
to be in the starting position than to appear at the opposite cell: 1.75/14=
40 vs 0.42/1440.

So 2000-twist scramble is good, 4000-twist is very good, but 1000-twist i=
s not enough if somebody wants really good scrambling :)

Andrey

--- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
>
> Well, if Andrey is backing away from this problem, then it must be more=20
> problematic than I first supposed! ;-)
>=20
> I don't quite accept the idea that the number of puzzle states is a good=
=20
> proxy for the number of scrambling twists needed to fully scramble.=20
> Consider the 4D megaminx (AKA 120 Cell) compared with the 4D pyraminx=20
> crystal. It seems as if they might both have roughly the same number of=20
> possible states, but I feel that the first will be much harder to=20
> scramble than the second because it is far less internally connected.=20
> It's as if in the first case, a given piece must stumble it's way all=20
> the way around a roughly spherical surface whereas the in the second=20
> case, pieces can move "through" the sphere and quickly find themselves=20
> just about anywhere.
>=20
> -Melinda
>=20
> On 5/3/2011 10:50 PM, Andrey wrote:
> > Hi all,
> > If we estimate number of twists for fully scrambled puzzle by its nu=
mber of states, the simplest formula may be like this:
> >
> > N=3Dlog(number_of_colors)/log(number_of_possible_twists)*number_of_stic=
kers.
> >
> > Here we count all "chemically" possible paintings of the puzzle. Their =
number is not much more than number of the possible states (for 120-cell it=
's close to the square of the number of states). So we have some reserve fo=
r "Brownian motion" in the graph of possible states, and it should be enoug=
h for practical purposes. For 7^5 it gives 66000 twists, but for smaller pu=
zzles results are more acceptable:
> >
> > 3^4: 80
> > 4^4: 180
> > 5^4: 350
> > 3^5: 360
> > 120-cell: 4000
> > {3}x{3}, 3 layers: 64
> >
> > But in my new program I'll use something more simple: N=3D1000 :)
> >
> > Andrey
>

---

From: Melinda Green <melinda@superliminal.com>
Date: Wed, 04 May 2011 02:43:39 -0700
Subject: Re: [MC4D] Hi everyone, I'm back!

I just made up the 4D pyraminx crystal as the extrapolation from the 3D
version, but there's no reason to go to 4D in the first place. I'm
betting that the 3D megaminx is harder to scramble well compared with
the pyraminx crystal.

Hey, maybe the members interested in speedsolving can tell us how they
solve that problem. I mean whoever runs those contests must have some
rules regarding the minimum number of scrambling twists to use with each
different puzzle. They must have the same dilemma that I have which is
that they must choose a sufficiently large minimum, but not one that is
so large as to be impractical. Anyone here know how they choose those
numbers?

-Melinda

On 5/4/2011 2:28 AM, Andrey wrote:
> Melinda,
> May be, you are right. I don't know the structure of 4D pyraminx crystal, but I made an experiment on 120-cell.
> Take one 2C piece. A random twist moves one of its cells with probability 1/60, so in 2000-twist sequence it will be moved about 33 times. It can take one of 1440 positions+orientations, and it's not difficult to find a distribution of its states after a number of twists.
> I can say that after 33 moves touching the piece its probabilities will be distributed from 0.869/1440 (positions on the opposite cell) to 1.133/1440 (on the same cell where it started). For me it's random enough. After 67 moves (=4000 twists of the puzzle) it will vary from 0.9957/1440 to 1.0043/1440.
> But after 1000-twist scramble there are 4 times more chance of the piece to be in the starting position than to appear at the opposite cell: 1.75/1440 vs 0.42/1440.
>
> So 2000-twist scramble is good, 4000-twist is very good, but 1000-twist is not enough if somebody wants really good scrambling :)
>
> Andrey
>
> --- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
>> Well, if Andrey is backing away from this problem, then it must be more
>> problematic than I first supposed! ;-)
>>
>> I don't quite accept the idea that the number of puzzle states is a good
>> proxy for the number of scrambling twists needed to fully scramble.
>> Consider the 4D megaminx (AKA 120 Cell) compared with the 4D pyraminx
>> crystal. It seems as if they might both have roughly the same number of
>> possible states, but I feel that the first will be much harder to
>> scramble than the second because it is far less internally connected.
>> It's as if in the first case, a given piece must stumble it's way all
>> the way around a roughly spherical surface whereas the in the second
>> case, pieces can move "through" the sphere and quickly find themselves
>> just about anywhere.
>>
>> -Melinda
>>
>> On 5/3/2011 10:50 PM, Andrey wrote:
>>> Hi all,
>>> If we estimate number of twists for fully scrambled puzzle by its number of states, the simplest formula may be like this:
>>>
>>> N=log(number_of_colors)/log(number_of_possible_twists)*number_of_stickers.
>>>
>>> Here we count all "chemically" possible paintings of the puzzle. Their number is not much more than number of the possible states (for 120-cell it's close to the square of the number of states). So we have some reserve for "Brownian motion" in the graph of possible states, and it should be enough for practical purposes. For 7^5 it gives 66000 twists, but for smaller puzzles results are more acceptable:
>>>
>>> 3^4: 80
>>> 4^4: 180
>>> 5^4: 350
>>> 3^5: 360
>>> 120-cell: 4000
>>> {3}x{3}, 3 layers: 64
>>>
>>> But in my new program I'll use something more simple: N=1000 :)
>>>
>>> Andrey
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>

---

From: "schuma" <mananself@gmail.com>
Date: Wed, 04 May 2011 16:50:16 -0000
Subject: Re: Hi everyone, I'm back!

Melinda,

The official rule of WCA about scrambling can be found here:



The rule specified which program to use to generate the scramble sequences,=
and the length of the sequences. They shouldn't be too long coz that's a b=
urden for the scramblers.=20

I think the most interesting case is 2x2x2. By simple brute force search, t=
he god's number is shown to be 11. The length of scramble sequences is rand=
om, according to the official program. The length is usually 7~9, which is =
less than the god's number. Sometimes very short scramble sequence is gener=
ated from that program, like with length 5. Then the contestant will be luc=
ky. And the record is still official. I think the reason they don't use 11-=
move scrambling is because, with 9 moves most of the states (3 million out =
of 3.6 million states) can already be covered (see the table in http://en.w=
ikipedia.org/wiki/Pocket_Cube). So WCA feels it not necessary to use more m=
oves.=20

The scrambling rule for other puzzles is more intuitive. The length is alwa=
ys approximately the god's number of an estimate of it, as far as I can se=
e. For example, the length for 3x3x3 is about 20, 21.=20

But I guess every one agrees that the complexity of a human solve has littl=
e to do with whether the puzzle is really fully scrambled or not, except it=
's too easy. Like, nobody can take advantage from the fact that the 120-cel=
l is scrambled by 1000 moves rather than 4000 moves.=20

Nan

--- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
>
> I just made up the 4D pyraminx crystal as the extrapolation from the 3D=
=20
> version, but there's no reason to go to 4D in the first place. I'm=20
> betting that the 3D megaminx is harder to scramble well compared with=20
> the pyraminx crystal.
>=20
> Hey, maybe the members interested in speedsolving can tell us how they=20
> solve that problem. I mean whoever runs those contests must have some=20
> rules regarding the minimum number of scrambling twists to use with each=
=20
> different puzzle. They must have the same dilemma that I have which is=20
> that they must choose a sufficiently large minimum, but not one that is=20
> so large as to be impractical. Anyone here know how they choose those=20
> numbers?
>=20
> -Melinda
>=20
> On 5/4/2011 2:28 AM, Andrey wrote:
> > Melinda,
> > May be, you are right. I don't know the structure of 4D pyraminx cry=
stal, but I made an experiment on 120-cell.
> > Take one 2C piece. A random twist moves one of its cells with probab=
ility 1/60, so in 2000-twist sequence it will be moved about 33 times. It c=
an take one of 1440 positions+orientations, and it's not difficult to find =
a distribution of its states after a number of twists.
> > I can say that after 33 moves touching the piece its probabilities w=
ill be distributed from 0.869/1440 (positions on the opposite cell) to 1.13=
3/1440 (on the same cell where it started). For me it's random enough. Afte=
r 67 moves (=3D4000 twists of the puzzle) it will vary from 0.9957/1440 to =
1.0043/1440.
> > But after 1000-twist scramble there are 4 times more chance of the p=
iece to be in the starting position than to appear at the opposite cell: 1.=
75/1440 vs 0.42/1440.
> >
> > So 2000-twist scramble is good, 4000-twist is very good, but 1000-tw=
ist is not enough if somebody wants really good scrambling :)
> >
> > Andrey
> >
> > --- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
> >> Well, if Andrey is backing away from this problem, then it must be mor=
e
> >> problematic than I first supposed! ;-)
> >>
> >> I don't quite accept the idea that the number of puzzle states is a go=
od
> >> proxy for the number of scrambling twists needed to fully scramble.
> >> Consider the 4D megaminx (AKA 120 Cell) compared with the 4D pyraminx
> >> crystal. It seems as if they might both have roughly the same number o=
f
> >> possible states, but I feel that the first will be much harder to
> >> scramble than the second because it is far less internally connected.
> >> It's as if in the first case, a given piece must stumble it's way all
> >> the way around a roughly spherical surface whereas the in the second
> >> case, pieces can move "through" the sphere and quickly find themselves
> >> just about anywhere.
> >>
> >> -Melinda
> >>
> >> On 5/3/2011 10:50 PM, Andrey wrote:
> >>> Hi all,
> >>> If we estimate number of twists for fully scrambled puzzle by its=
number of states, the simplest formula may be like this:
> >>>
> >>> N=3Dlog(number_of_colors)/log(number_of_possible_twists)*number_of_st=
ickers.
> >>>
> >>> Here we count all "chemically" possible paintings of the puzzle. Thei=
r number is not much more than number of the possible states (for 120-cell =
it's close to the square of the number of states). So we have some reserve =
for "Brownian motion" in the graph of possible states, and it should be eno=
ugh for practical purposes. For 7^5 it gives 66000 twists, but for smaller =
puzzles results are more acceptable:
> >>>
> >>> 3^4: 80
> >>> 4^4: 180
> >>> 5^4: 350
> >>> 3^5: 360
> >>> 120-cell: 4000
> >>> {3}x{3}, 3 layers: 64
> >>>
> >>> But in my new program I'll use something more simple: N=3D1000 :)
> >>>
> >>> Andrey
> >
> >
> >
> > ------------------------------------
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
>

---

From: Melinda Green <melinda@superliminal.com>
Date: Wed, 04 May 2011 12:47:56 -0700
Subject: Re: [MC4D] Re: Hi everyone, I'm back!

Hello Nan,

Thank you for the link to the speedsolving scrambling rules. I guess
it's not much help though it's good to see how others have approached
this problem.

I understand what you are saying about scrambling for humans.
Specifically, after 10 twists or so, no human will save any time by
trying to carefully back out the scrambling moves, meaning that they
will have to perform a "full" solution. It is good to note that it may
be rather easy to back out 10 or even 20 random twists on the 120 Cell
because faces are very sparsely interconnected. I'm going to go out on a
limb here and say that I disagree that 1000 twists on this puzzle is as
good as 4000. Given the low odds of any given piece on this puzzle
finding itself on its opposite face, I would expect the length of human
solutions on 1000 twist scrambles to be consistently shorter than for
4000 twist scrambles.

As I was composing the above, I just thought of a potentially good way
of scrambling at least any puzzle in which every face has an opposite:
First, construct a checkerboard pattern in which every face alternates
pieces with its opposite, and then use random scrambling twists from
that state. That still doesn't solve our need for a Goldilocks function,
but I bet that it would drastically reduce the number of needed
scrambling twists for many puzzles.

-Melinda

On 5/4/2011 9:50 AM, schuma wrote:
> Melinda,
>
> The official rule of WCA about scrambling can be found here:
>
>
>
> The rule specified which program to use to generate the scramble sequences, and the length of the sequences. They shouldn't be too long coz that's a burden for the scramblers.
>
> I think the most interesting case is 2x2x2. By simple brute force search, the god's number is shown to be 11. The length of scramble sequences is random, according to the official program. The length is usually 7~9, which is less than the god's number. Sometimes very short scramble sequence is generated from that program, like with length 5. Then the contestant will be lucky. And the record is still official. I think the reason they don't use 11-move scrambling is because, with 9 moves most of the states (3 million out of 3.6 million states) can already be covered (see the table in http://en.wikipedia.org/wiki/Pocket_Cube). So WCA feels it not necessary to use more moves.
>
> The scrambling rule for other puzzles is more intuitive. The length is always approximately the god's number of an estimate of it, as far as I can see. For example, the length for 3x3x3 is about 20, 21.
>
> But I guess every one agrees that the complexity of a human solve has little to do with whether the puzzle is really fully scrambled or not, except it's too easy. Like, nobody can take advantage from the fact that the 120-cell is scrambled by 1000 moves rather than 4000 moves.

---

Return to MagicCube4D main page
Return to the Superliminal home page