Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Thu Apr 17, 2014 5:15 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 23 posts ] 
Author Message
 Post subject: If God's Number for the 3x3x3 is 20...
PostPosted: Fri Jan 03, 2014 9:10 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Does that also mean that any position can be reached within 20 moves no matter what state your cube is in?


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Fri Jan 03, 2014 9:55 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Surely yes, because the final state just depends on where the stickers happen to be, and does not need to be solved.

Plus, all permutations are mathematically equivalent with the same mechanical symmetry, so each state has the same God's number to all other states, and vice versa.

Thus, the final state (location of the stickers) is irrelevant.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Fri Jan 03, 2014 11:38 pm 
Offline
User avatar

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
Would this then be true of any puzzle with unrestricted turning?

-d


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Fri Jan 03, 2014 11:48 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Yes I believe so - as long as you can follow the same path backward for every path forward between any two configurations, then God's number should be independent of the final configuration, and depend only on the puzzle itself. Probably Jaap or Carl or Brandon can verify this...

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 7:20 am 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
Kelvin, your analysis is, in general, correct and the reason lies in this statement:
KelvinS wrote:
Plus, all permutations are mathematically equivalent with the same mechanical symmetry, so each state has the same God's number to all other states, and vice versa

Provided the distinct configurations of a puzzle exactly form a group and the nature of the moves are not dependent on the state of the puzzle, the group "looks" the same from any element in the group, which translates into the distribution of states from a given state A is independent of the choice of state A.

However...

I can think of two ways this can fail, both of which are quite common on twisty puzzles 8-)



1. This is not necessarily true if some set of pieces in the same orbit are indistinguishable.

A 4x4x4 is an example of this that we are all familiar with. The centers on a 4x4x4 come in 6 sets of 4 indistinguishable pieces. The visually distinct configurations of these pieces do NOT form a group and thus the configurations are NOT in the same distribution away from every configuration. Now, a 4x4x4 has JUST a few too many configurations for me to analyze completely by computer :lol: but I can give another example.

Consider a Master Floppy Cube, a 1x4x4, with each face a solid color, but no super stickers. This puzzle has 4 indistinguishable pieces - the 4 center pieces with only two stickers each (ok, technically you can tell 2 apart from the other 2 due to orientation restrictions, but there exists at least two indistinguishable pieces all the same!). The Master Floppy Cube can reach 20,736 visually distinct configurations but before I can analyze the distribution of configurations, I need to define what counts as one move and what counts as two. Let's say slice moves are two moves, but moving an outer and inner layer on the same side together is only one move (note I could also reverse this statement OR define both situations as only one move; all 3 options result in slightly different distributions). From the solved position, the states are distributed as follows:

0 - 1
1 - 6
2 - 24
3 - 91
4 - 339
5 - 1086
6 - 2670
7 - 4754
8 - 5562
9 - 4139
10 - 1772
11 - 292

Now rotate the top 2 layers of the puzzle so that the square face shows half one color and half the opposite color. From THIS position the states are distributed as follows:

0 - 1
1 - 6
2 - 24
3 - 91
4 - 330
5 - 1005
6 - 2471
7 - 4620
8 - 5726
9 - 4338
10 - 1816
11 - 308

You'll notice there are some slight discrepancies :wink: The differences in these numbers indicate some positions are further away (accounting for the difference in starting position) while others are closer. In this case though, God's Number remains unchanged at 11.



2. This is also not necessarily true if some pieces have visible orientation while other pieces in the same orbit do not.

A fantastic example of this is the Fisher Cube - using the piece names before the shape modification, some edges and some centers have visible orientation while other edges and centers do not. Other examples include many shape mods and the Mixup Cube. Again the Fisher Cube has too many states for a complete analysis (at least not by me on my dinky little laptop :P ) so let me instead demonstrate with a different puzzle we are all familiar with: a 2x2x2.

Now, a standard 2x2x2 has visible orientation on every piece so let's modify that. Remove all of the stickers from two adjacent corners in the solved position. Color the plastic on one of these bare corners a different color. There. Now we have a puzzle with 8 distinguishable pieces, but 2 of them have no distinguishable orientation. Surely there could exist a shape-mod that has the same properties. The 1,224,720 configurations of this puzzle are distributed from solved as follows:

0 - 1
1 - 9
2 - 54
3 - 321
4 - 1847
5 - 9980
6 - 49528
7 - 207280
8 - 561920
9 - 386996
10 - 6784

As we can see from this list, God's Number for this modified 2x2x2 is 10

Now for the fun part: while the puzzle is solved, put one of the bare corners in the D layer and one in the U layer. Perform the move U². From here, the sequence:
R² F² R' F' R² U F R² U R' U'
reaches a state that cannot be returned to the starting position (U² from solved) in less than 11 moves 8-)



The Rubik's Cube does not have either of these properties so yes, every position can be reached from every position in 20 moves or less (and the same numbers of positions can be reached after each number of moves up to 20).

So your intuition is correct: all states in a group are equivalent in terms of distribution from one another under generator operations, but very often, twisty puzzles do not quite form a group as cleanly as we (I) would like :)

Peace,
Matt Galla

PS:
My new life goal is to get included in this list:
KelvinS wrote:
Probably Jaap or Carl or Brandon can verify this...


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 12:23 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
PS. Good thinking, thanks Matt, though intuitively I find it hard to believe that different configurations of a 4x4x4 have a different God's number, except for the sole reason that some pieces *appear* to be equivalent when they are mathematically non-equivalent.

PS. Regarding the list, those were just names that came to my mind, it certainly wasn't exhaustive given the average IQ in this place! :-)

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 1:44 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Excellent analysis Matt. My response would have been much shorter: "only if the puzzle forms a group" and I may have provided and example or two of puzzles that don't form a group. Therefor I humbly surrender my spot in Kevin's list to you :D

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 5:51 pm 
Offline
User avatar

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
Wow, great work Matt!! Just think, in another 10 years, it may even be possible to do the 4x4 analysis in a reasonable amount of time.

-d


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 6:05 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
darryl wrote:
Wow, great work Matt!! Just think, in another 10 years, it may even be possible to do the 4x4 analysis in a reasonable amount of time.

-d

Sadly the 4x4x4 analysis will never be able to be done.

A 4x4x4 has (8! * 24! * (24! / ((4!)^6)) * 3^7) / 24 = 7401196841564901869874093974498574336000000000 positions.

If you want to analyze the whole group (super 4x4x4) it has: (8! * 24! * (24! / 2) * 3^7) / 24 = 707195371192426622240452051915172831683411968000000000 positions.

That's ~ 2^179 positions. That's beyond any calculation physically possible.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 9:24 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Could quantum computing handle that? I have no idea of its theoretical limitations...

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 9:31 pm 
Offline

Joined: Fri Dec 20, 2013 11:47 pm
Not yet. They still get weird answers sometimes with 1+1 :D


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Sun Jan 05, 2014 11:17 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
KelvinS wrote:
Could quantum computing handle that? I have no idea of its theoretical limitations...

Well, I'm not an expert in quantum computing but most quantum speedups I've seen do sqrt(O(orig)) which is like saying O(2^N) -> O(2^(N/2)) so if a quantum computer could speed up the calculation, it would go from 2^179 to 2^89. That's quantum-operations too, not classical ones.

2^89 classical operations will probably be achievable in 20-30 years.

In short, quantum computing might help but we're probably talking 50-100 years from now, if ever.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 7:29 am 
Offline

Joined: Sun Nov 23, 2008 2:18 am
Please excuse my ignorance, but is the impossibility of analysing the 4*4*4 group because it would take more memory than a computer that could store a bit in every elementary particle in the observable universe, because it would take the age of the universe to complete even on a binary computer operating at the theoretical limit, or due to some other limitation I can't think of?

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 1:48 pm 
Offline

Joined: Sun Aug 04, 2013 4:50 am
Location: The Netherlands
Jeffery Mewtamer wrote:
Please excuse my ignorance, but is the impossibility of analysing the 4*4*4 group because it would take more memory than a computer that could store a bit in every elementary particle in the observable universe, because it would take the age of the universe to complete even on a binary computer operating at the theoretical limit, or due to some other limitation I can't think of?


You're not going to believe me, but...

I JUST ASKED MYSELF THE SAME QUESTION!

_________________
- Eric


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 3:21 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jeffery Mewtamer wrote:
Please excuse my ignorance, but is the impossibility of analysing the 4*4*4 group because it would take more memory than a computer that could store a bit in every elementary particle in the observable universe, because it would take the age of the universe to complete even on a binary computer operating at the theoretical limit, or due to some other limitation I can't think of?

Actually neither time nor space is the limiting factor. There are probably algorithms that could be used that have O(1) memory usage so even though there are more states than atoms in the universe, that isn't an issue.

The limit is actually a thermodynamic one. Check out this great paper Ultimate physical limits to computation by Seth Lloyd.

In brief, the minimum amount of energy needed to perform a logical operation is $E \geq \frac{\pi \hbar}{2 \Delta t}$

So suppose each state could be visited in one logical operation (absurd, I know) and we want to perform the calculation in one year using the most thermodynamically efficient parallel computer where all operations are done at the same time over a 1 year period of time.

(((Pi hbar) / (2 * (1 year in seconds))) * ((8! * 24! * (24! / 2) * 3^7) / 24)) = $3.7 \times 10^{12}\: \mathrm{J}$


Not to mention this calculation is much larger than what you'd need to factor 2048 bit RSA keys and break a lot of other crypto.

Note: If you want to render the TeX in this post, make a bookmark in your browser to this Javascript:
Code:
javascript:(function(){if(window.MathJax===undefined){var%20script%20=%20document.createElement("script");script.type%20=%20"text/javascript";script.src%20=%20"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML";var%20config%20=%20%27MathJax.Hub.Config({%27%20+%20%27extensions:%20["tex2jax.js"],%27%20+%20%27tex2jax:%20{%20inlineMath:%20[["$","$"],["\\\\\\\\\\\\(","\\\\\\\\\\\\)"]],%20displayMath:%20[["$$","$$"],["\\\\[","\\\\]"]],%20processEscapes:%20true%20},%27%20+%20%27jax:%20["input/TeX","output/HTML-CSS"]%27%20+%20%27});%27%20+%20%27MathJax.Hub.Startup.onload();%27;if%20(window.opera)%20{script.innerHTML%20=%20config}%20else%20{script.text%20=%20config}%20document.getElementsByTagName("head")[0].appendChild(script);(doChatJax=function(){window.setTimeout(doChatJax,1000);MathJax.Hub.Queue(["Typeset",MathJax.Hub]);})();}else{MathJax.Hub.Queue(["Typeset",MathJax.Hub]);}})();

Then when you visit the bookmark while on this page, the Javascript will load MathJax and render the inline TeX.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 4:44 pm 
Offline
User avatar

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
I just threw 10 years out there kind of arbitrary. I do recall the 3x3x3 being outside the realm of being calculated, but some extremely clever short cuts were incorporated to make it possible. I just thought, coming up with some other revolutionary shortcuts along with increased processing power and/or quantum computing, it may be possible. I suppose though 10 years is extremely optimistic for quantum computers. I too have heard that at least with cracking encryption, quantum calculations would cut the time down by a square root. I don't see why it would be different for working through this type of calculation, but I am by no means an expert.

It would be interesting though to see all sorts of resources thrown at this problem. I would imagine if the NSA had nothing better to do, they could probably get us an answer in less than a year :)

-d


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 5:05 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
darryl wrote:
quantum calculations would cut the time down by a square root.

Would't that depnd what units of time you are counting in? For example:

SQRT(1 Year) = 1 Year
SQRT(12 mo) = 3.5 months
SQRT(52 weeks) = 7.2 weeks
SQRT(365 days) = 19.1 days

Surely these can't all be right as the answers are inconsistent!

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 6:25 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
KelvinS wrote:
darryl wrote:
quantum calculations would cut the time down by a square root.

Would't that depnd what units of time you are counting in? For example:

SQRT(1 Year) = 1 Year
SQRT(12 mo) = 3.5 months
SQRT(52 weeks) = 7.2 weeks
SQRT(365 days) = 19.1 days

Surely these can't all be right as the answers are inconsistent!


It's the square root of the work, not the time. Work is measured in elementary operations so if something takes O(2^128) work, some quantum algorithms can do it in O(2^64) work.

Regarding quantum computations speeding up an algorithm generically, that comes from the ability for a quantum computer to be able to search an UNSORTED list of length n in O(sqrt(n)) time whereas classical computers take n time to search the list. This speeds up certain types of crypto like finding hash collisions because of generic searching speedups.

I don't think any of that apply to visiting every state of a puzzle. That is, I don't think you only need to visit sqrt(n) states rather than all n states. Also, the minimum energy stated above is for quantum bits.

Comparing the 4x4x4 problem for a moment, the Super 4x4x4 is 7983681996152001103100136000000 times the size of the Super 3x3x3. That's 2^102 times as big.

Suppose in some far off future there are 10 billion computers on Earth and each computer can search the ENTIRE Super 3x3x3 space in 1 nano second. Then it would take 25316 years to search the 4x4x4 space.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 6:32 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
And Oskar's 17x17x17?

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 10:26 pm 
Offline
User avatar

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
So really then, the only practical way is to come up with a really clever way of trimming down the set.

-d


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Mon Jan 06, 2014 11:48 pm 
Offline
User avatar

Joined: Fri Dec 28, 2012 1:50 pm
Location: Near Las Vegas, NV
KelvinS wrote:
And Oskar's 17x17x17?

According to my extremely lazy calculations the super 17x17x17 has a total of:
(12!/2)*(2^11)*(8!)*(3^7)*((4^6)/12)*(24!/2)^56*(24!)^7
12!/2=central edge permutations
2^11=central edge orientations
8!=corner permutations
3^7=corner orientations
(4^6)/12=super center orientations (I'm not 100% sure if this is right)
(24!/2)^56=center permutations (If centers have even parity, which I think is true)
(24!)^7=wing edge permutations
It all equals infinity! :lol:

_________________
My Youtube channel
My Shapeways Shop


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Tue Jan 07, 2014 12:17 am 
Offline

Joined: Fri Dec 20, 2013 11:47 pm
Now divide by 6 and you will have all the unique permutations since it can be exactly the same 6 different ways, the only variance being the color scheme.


Top
 Profile  
 
 Post subject: Re: If God's Number for the 3x3x3 is 20...
PostPosted: Tue Jan 07, 2014 12:21 am 
Offline

Joined: Fri Dec 06, 2013 2:37 am
I am completely lost when it comes to computer programming, but calculating permutations, I definitely do understand. I was helping some new cubers understand how to calculate the permutations of a Rubik's cube (on the speedcubing forum) when the master (cmowla) showed up and produced this link.

This link contains a very well written explanation of how to calculate the number of permutations of an nxnxn cube and nxnxn supercube. I suggest that you check it out even if you do understand how to calculate the permutations of a cube, because it makes it seem so simple.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 23 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Drake, Google Adsense [Bot] and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group