View unanswered posts  View active topics

Page 1 of 1

[ 23 posts ] 

Author 
Message 
Jared

Post subject: If God's Number for the 3x3x3 is 20... Posted: Fri Jan 03, 2014 9:10 pm 

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 


KelvinS

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Fri Jan 03, 2014 9:55 pm 

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 


darryl

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Fri Jan 03, 2014 11:38 pm 

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 


KelvinS

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Fri Jan 03, 2014 11:48 pm 

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 


Allagem

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

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


KelvinS

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Sun Jan 05, 2014 12:23 pm 

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


Brandon Enright

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Sun Jan 05, 2014 1:44 pm 

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
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


darryl

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Sun Jan 05, 2014 5:51 pm 

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 


Brandon Enright

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Sun Jan 05, 2014 6:05 pm 

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 


KelvinS

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Sun Jan 05, 2014 9:24 pm 

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 


garathnor

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

Joined: Fri Dec 20, 2013 11:47 pm

Not yet. They still get weird answers sometimes with 1+1


Top 


Brandon Enright

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Sun Jan 05, 2014 11:17 pm 

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 quantumoperations too, not classical ones. 2^89 classical operations will probably be achievable in 2030 years. In short, quantum computing might help but we're probably talking 50100 years from now, if ever.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


Jeffery Mewtamer

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

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 


1NSAN3

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

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 


Brandon Enright

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Mon Jan 06, 2014 3:21 pm 

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=TeXAMS_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/HTMLCSS"]%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 


darryl

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Mon Jan 06, 2014 4:44 pm 

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 


KelvinS

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Mon Jan 06, 2014 5:05 pm 

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 


Brandon Enright

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Mon Jan 06, 2014 6:25 pm 

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 


KelvinS

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Mon Jan 06, 2014 6:32 pm 

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 


darryl

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Mon Jan 06, 2014 10:26 pm 

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 


benpuzzles

Post subject: Re: If God's Number for the 3x3x3 is 20... Posted: Mon Jan 06, 2014 11:48 pm 

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!)^712!/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!
_________________ My Youtube channel My Shapeways Shop


Top 


garathnor

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

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 


Elrog

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

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 



Page 1 of 1

[ 23 posts ] 

Who is online 
Users browsing this forum: Google Adsense [Bot] and 5 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


