20 ms·
God's Number Is 20 (2010)
- _petronius 8y agoComparing the quarter-turn metric and the "standard" metric is very interesting. I'm fascinated that for both, the number of positions above a certain distance starts to reduce again (which is much more pronounced in the quarter-turn table). Intuitively, it isn't obvious to me why this would be so, but it's nerd sniped me into thinking about how combinations work in general and the geometry of the Rubik's cube particularly. Off to Wikipedia!
- blattimwind 8y ago> Intuitively, it isn't obvious to me why this would be so, but it's nerd sniped me into thinking about how combinations work in general and the geometry of the Rubik's cube particularly. My guess would be that this can be hand-waved by looking at it like a sort of discrete space. Then a solved cube is a single point in that space (let's assume we already normalize for orientation etc.). The moves we can make on a cube connect each point in the space to a set of adjacent points. The shortest path from A to B would be the space's metric. Now we know that the maximum distance from the origin / solution point is 20. Let's call all the points with a given distance n S_n (like "stratum"). To explain the distribution we only need to look at paths that either go from S_n to S_n+1 or to S_n-1, because "lateral moves" are never relevant to the shortest/optimal paths. So for small n the number of points grows, because each stratum we go away from the solution gives us more possible moves to go even further away. For S_20 there are no moves that go further away, for S_19 each combination has at most one move that goes further away etc., so essentially I think the limitation of the path length at the edge reduces the possible combinations you can get in those stratums, i.e. close to the center a random move will bring you farther away, so there has to be more points farther away, but when you are close to the edge, a random move either doesn't move you at all (stratum-wise) or closer to the center, so there have to be fewer points as you approach the edge. The really interesting thing however is how these two balance each other to place most points in S_17 and S_18.
- entropicdrifter 8y agoWouldn't a solved cube actually be several possible points in that space? My intuition suggests that the inner four squares on each side could be rotated somehow, but I haven't learned the skill of solving rubik's cubes, so I'm not sure if that's true.
- blattimwind 8y ago> (let's assume we already normalize for orientation etc.)
- cvoss 8y agoIn the usual setting, the various orientations of the centers are considered irrelevant because you can't tell them apart. So those points in the configuration space are considered the same point. There is such a thing as a cube with marked centers, sometimes called a supercube, where the difference does matter. These are harder to solve, and I believe God's number is still unknown in that setting.
- kevinventullo 8y agoHere's an analogy: take a point on the sphere and consider the set of points on the sphere that are distance d from that point. The size of that set increases as d goes from 0 to 1/4 * circumference, then decreases as d goes to 1/2 * circumference, and you end up with just the antipodal point. There's probably some general argument that you'll always see this with any sufficiently nice compact metric space.
- schoen 8y agoIt also works for Hamming distance of bit strings. For an n-bit string there are C(n,k) ways of achieving a Hamming distance of k, for example there is only 1 string with distance 0 (the original string) and 1 string with distance n (the complement of the original string), and everything in the middle goes first up and then down—following the components of Pascal's triangle. This could also be viewed as, for example, the distance along edges from one corner of an n-dimensional hypercube to other corners. There is 1 corner where you don't move at all and 1 corner where you move in every dimension, and the largest number of corners in which you move in half of the dimensions. I agree with your intuition that this phenomenon will apply to a whole lot of contexts and situations.
- rocqua 8y agoFeels to me like this is required of any 'lattice' (partial ordered set with a unique supremum and infinum for every sub-set). Notably, given any 'cross-section' of a lattice (a set A such that given an x in A, and any x > y then y in A) has a 'surface' (the set of all points x in z such that for all y in A we NOT z > x). That cross section needs to start (1 element) at the cross section containing only the 'infinum' of the entire lattice. Similarly, the surface needs to end small (1 element again) at the cross-section that is the entire lattice. In between, it will generally by larger. I think there might be some 'convexity' results that can be proven about the surfaces of increasing sequences of cross-sections. Given specific kinds of lattices. It feels to me like a cartesian-lattice would always have this convexity porperty. (By convexity I mean that the surface starts of increasing, might be constant for a while, and then must continue decreasing.) Cool subject, makes me wish I was doing a PhD in mathematics.
- kreiw 8y agoInteresting. I was convinced that Terry A. Davis had died.
- andybak 8y agoCan skilled players usually solve a random position in 20 moves? If not - what's the usual human target for an arbitrary position?
- hmate9 8y agoNo. Humans memorise algorithms for different patterns and then apply them. Humans don’t solve a rubic’s cube by trying to find the least moves.
- killlameme99 8y agoI mean to an extent you do search for the least number of move: you memorize a number of different algorithms and apply the one that will work with the least number of moves in the given situation. The method used by a majority of cubers is called "CFOP" [1] which can can solve the cube in "average 50-60 moves" according to a quora user [2]. [1] https://ruwix.com/the-rubiks-cube/advanced-cfop-fridrich/ https://ruwix.com/the-rubiks-cube/advanced-cfop-fridrich/ [2] https://www.quora.com/How-many-moves-does-it-take-to-solve-Rubiks-cube-first-and-second-layer https://www.quora.com/How-many-moves-does-it-take-to-solve-R...
- aeorgnoieang 8y agoAccording to sibling comments of your own, you're wrong. Humans deliberately solve cubes with the least number of moves and even compete to do so. Generally tho, you're probably correct.
- rimliu 8y agoAnd even in speed solves sometimes a different algorithm (which may be a bit longer/not as convenient to execute) is applied if the solver knows that it will lead to the more favourable position afterwards. E.g. OLL/PLL skips.
- rwnspace 8y agoNot usually - exceedingly rarely - but yes. Some people specialise in this as a competitive event. There are advanced techniques applied which aren't appropriate or very useful for speed-solving. The average movecount for experienced speed-solvers is generally between 45-60, depending on methods employed. These methods rely much more on a variety of intuition and heavily drilled algorithms (pre-memorised sequences).
- crististm 8y agoSo 35 years can be compressed into, say 6 weeks, using only about 300 computers. I'm impressed what we can do with the computers of today.
- rntksi 8y agoDivide and conquer
- yitchelle 8y agoIf you have 43,252,003,274,489,856,000 computers, it could solve in milliseconds!
- peterwwillis 8y agoThen you'd have to have 43 quintillion network operations. That would probably take a couple hundred years.
- vectorEQ 8y agonot with 43 quintillion mbps :O
- lgeorget 8y agoPlus the time needed to aggregate the results...
- Vagantem 8y agoSo there is 43,252,003,274,489,856,000 positions of a Rubik's Cube? Pretty mind blowing.
- sjcsjc 8y agoAnd there are 80658175170943878571660636856403766975289505440883277824000000000000 possible shuffles of a pack of cards which is also mind blowing but really just an excuse for me to wheel out this excellent link again https://czep.net/weblog/52cards.html https://czep.net/weblog/52cards.html
- Dylan16807 8y agoOr in the typical way of measuring entropy, about 2^225. So you can make a connection through these impossibly big numbers into levels of security for cryptography, and see how this particular amount of impossible is right in the middle of typical use. It's also interesting to think about how a deck of cards is both elegant and unwieldy as a way to store a key.
- alex_stoddard 8y agohttps://en.wikipedia.org/wiki/Solitaire_(cipher) https://en.wikipedia.org/wiki/Solitaire_(cipher) "The Solitaire cryptographic algorithm was designed by Bruce Schneier at the request of Neal Stephenson for use by field agents in his novel Cryptonomicon, enabling them to communicate securely without having to rely on electronics or having to carry incriminating tools, It was designed to be a manual cryptosystem calculated with an ordinary deck of playing cards. In Cryptonomicon, this algorithm was originally called Pontifex to hide the fact that it involved playing cards."
- BurningFrog 8y agoAnd yet sorting a deck of cards is vastly easier than solving a Rubik's Cube. Which shows that these numbers don't at all measure puzzle difficulty.
- 8y ago
- deleted 8y ago[deleted]
- mrcactu5 8y agoHere's some notes from Harvard on how to count Rubik's Cube positions with Group Theory The number is: 2^(12)3^88!*12! http://www.math.harvard.edu/~jjchen/docs/Group%20Theory%20and%20the%20Rubik's%20Cube.pdf http://www.math.harvard.edu/~jjchen/docs/Group%20Theory%20an...
- skrebbel 8y agoI know mathematicians hate interpunction with a passion but that one's pretty extreme! I have no idea where the timeses and the parentheses are supposed to go..
- c3534l 8y ago! has operator precedence over \
- LeifCarrotson 8y agoIt's not helped by the fact than HN markup is interpreting asterisks as requests for italics and backslashes as escape sequences...
- simias 8y agoThe fact that HN still doesn't have a proper way to display code or mathematical formulas after all these years is a bit ridiculous. I guess by now it's part of the website's culture...
- yjftsjthsd-h 8y agoI'd prefer real markdown, but iirc 4 spaces of indentation does it? Foo*bar
- saagarjha 8y agoTwo: https://news.ycombinator.com/formatdoc https://news.ycombinator.com/formatdoc
- drinane 8y agoIts definitely 42 folks. https://en.wikipedia.org/wiki/42_(number)#The_Hitchhiker's_Guide_to_the_Galaxy https://en.wikipedia.org/wiki/42_(number)#The_Hitchhiker's_G...
- paulddraper 8y agoTo point out the obvious, that's the answer to the Life, the Universe, and Everything, not God's Number.
- magduf 8y agoWell isn't that kinda the same thing? If God is everywhere and in everything, you're talking about the same thing, so 42 is definitely the true number of God!
- mmjaa 8y agoTo (misquote) Deep Thought: "Whats the point of being a computer brain the size of a planet if all they ever ask you is 'What's Gods Phone Number?' ..."
- trentlott 8y agoA small note - is anyone else frustrated that the video can't be played in both directions? Watching someone disorder a solved cube is not particularly interesting or satisfying. I'm sure it does serve the text, but boy it irks me.
- rlue 8y agoYou can always click-and-drag the progress slider backwards. I think I'm more annoyed that the step-backwards and step-forwards buttons skip the animation and just flash to the cube's next state.
- yonatron 8y ago26 actually is G-d's number in Kabbala. (G-d's name Y-HVH has the the gematria (Jewish numerology) equivalent of 26 - an important number in kabbala and gematria.) I conclude therefore that the quarter-turn metric is the correct one! :)
- mirimir 8y agoYeah, that's what I thought TFA would be about. OK so this is totally off the wall. Back in the late 80s, I recall an Apple video which claimed that all of the Hebrew characters are 2D projections of some 3D shape. And then [something about creation, the structure of reality, etc]. I also remember something about a lawsuit by some guy in California, claiming that the video producer had stolen his work. I think that I even had a videotape. But it's all gone, or maybe packed in a box that I've lost track of. And it was so pre-Internet that there's no trace that I've managed to find. It was very trippy stuff. Anyway, had to ask :)
- Causality1 8y agoFor a second I worried that someone had managed to post that TimeCube lunatic to HN.
- namuol 8y agoI think this site is making an homage/reference to it.
- ktpsns 8y agoJust to put the statement "35 CPU-years of idle computer time donated by Google" into relation: One year is ~8640 hours. This means 302.400 CPU hours. That's nothing compared to a single research proposal (we count in multiples of millions of CPU hours). Any explanation of this number?
- _hl_ 8y agoI guess that's just all they needed until they were done?
- ktpsns 8y agoThe worth of a single CPUh on a cluster is roughly 0,1€. That's a 30k€ donation from google. Weird that they put this number at the front. My guess is that they run on a large number of CPU cores. On 1000 cores, it's already 300 million CPUh. Really, to put this into relationship, on many clusters you get 100k CPUh for free when you apply for getting access, just to test your code. That's why 300k CPUh is not much.
- _hl_ 8y agoSo you're saying the donation is insignificant in comparison to other applications? I'd say 30k€ is pretty significant, and it makes sense to thank them by mentioning it right at the front.
- ktpsns 8y agoEvery donation is significant. It's just uncommon in science to mention donations in the first sentence at all. As a reader, this suggests something exceptional. My point is only that this number isn't.
- tazeg95 8y agoGod move for pocket cube is 14, how to generate all positions and solve the cube : https://en.jeffprod.com/blog/2017/solving-a-rubik-s-pocket-cube-with-a-graph-database/ https://en.jeffprod.com/blog/2017/solving-a-rubik-s-pocket-c...
- ErotemeObelus 8y agoI thought this was the successor to Time Cube at first.
- megaremote 8y agoIs there a position you could get the cube into, maybe by having to take it apart, that can not be solved?
- poizan42 8y agoYes by taking it apart, just rotate a single corner, flip a single edge or swap two edges.