God's Number Is 20 (2010) | Hacker News Reader

God's Number Is 20 (2010)

cube20.org

152 pointsweinzierl83 comments

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

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

Comparing 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!

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

Wouldn'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.

> (let's assume we already normalize for orientation etc.)

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

Here'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.

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

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

For reference, what you call a 'cross section' is sometimes called an ideal or a downset. I can't quite make out your definition of 'surface', but, if it is meant to read "the set of all points x in A such that for all y in A we have not y > x", then it is the set of maximal elements of A. I'm not an expert on posets, but, if I've got the terminology right, your notion of convexity sounds like you want to deal with a ranked poset with unimodal h-vector.

I think you mean the growth of that set as d goes to half circumference. The absolute size increases up to the area of the sphere.

If we take the definition to refer to points that are exactly distance d, rather than points that are within distance d, I think the original formulation is correct.

Oh, yeah, my mistake.

Here'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%20an...

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

! has operator precedence over \

It's not helped by the fact than HN markup is interpreting asterisks as requests for italics and backslashes as escape sequences...

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

I'd prefer real markdown, but iirc 4 spaces of indentation does it?
Foo*bar

Two: https://news.ycombinator.com/formatdoc

Does anyone know where to find a guide to HN markup? I've exhausted my google-fu and have come up dry...

There's a short one here: https://news.ycombinator.com/formatdoc

Thanks!

It's 2^12 × 3^8 × 8! × 12!

To go full Unicode: 2¹² × 3⁸ × 8! × 12!

12!9!(4!3!)³

Perhaps someone can tell us how many digits that has (or am expression for how many digits...)

Its explicit value is 519024039293878272000 (not nearly as big as some integers we discuss around here!).

Or roughly 5.2E20, if you're just looking for the order of magnitude.
Or ~520 exapositions, if you want to say it in a way that upsets people.

451 exapositions, if you want to say it in a way that really upsets people.

451 "exbipositions" should calm some of those people down (and further antagonize others).
https://en.wikipedia.org/wiki/Binary_prefix#exbi
BTW don't bother Googling for exaposition or exbiposition. :-)

It's pretty much impossible to decipher if you don't remember the operator precedence or have the operator precendence handy.

Looks like you might need to put spaces between * and other text because the auto-italicization thing is gobbling your multiplication.

2 spaces prefix for verbatim

The same paper also states that they calculated the number above earlier, but only about 1/12th of those are valid so the real number of valid combinations is 4x10^19

I thought this was the successor to Time Cube at first.

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

Divide and conquer

If you have 43,252,003,274,489,856,000 computers, it could solve in milliseconds!

Then you'd have to have 43 quintillion network operations. That would probably take a couple hundred years.

not with 43 quintillion mbps :O

Plus the time needed to aggregate the results...

Can skilled players usually solve a random position in 20 moves? If not - what's the usual human target for an arbitrary position?

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

I 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/ [2] https://www.quora.com/How-many-moves-does-it-take-to-solve-R...

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

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

Not 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).

There's an event in competitions called "fewest moves" where you have one hour to find the shortest solve of a particular scramble.
Just a month ago Harry Savage managed to beat the world record and find a 17-move solve. 20 moves or fewer has been managed a number of times, but it's not regular.

No, at least not for normal solves. On average most solves will be 40-60 moves, though that's very luck dependent. In the case of the most common CFOP method, F2L (the F in CFOP) makes or breaks most solves because everyone does it intuitively.
However there are 3x3x3 least-moves challenges in most big competitions, but they are much closer to being mathematics problems than practical cubing. You usually get a fairly long amount of time to find the shortest number of moves to solve said cube. The record was beaten recently by Harry Savage with a 17-move solution (note that 20 moves is the maximum number for an ideal solution).

For ideal solve competitions, do we input the cube into a computer to have surety on the ideal solve number?

I believe so. In addition, for smallest-move competitions you're actually given the scramble moves -- so your job is to apply a bunch of mathematical techniques to shorten the number of moves to the smallest number you can.

I'm a speedcuber with an official (World Cube Association) 3x3 average of 10.01 seconds. I use the CFOP method, which is 50-60 moves on average. The other popular method for speedsolving the 3x3 is Roux, which is ~5 moves lower.
There's another event the WCA conducts called Fewest Moves Challenge, or FMC in short. In this event, you're given a scramble and one hour to find the shortest solution to that scramble. The world record solve for that is 17, with just 20 people having an attempt <= 20 moves. There's no fixed method like CFOP or Roux that people use for FMC. The general heuristic is to solve as many individual pieces as possible at once with a few moves and then use commutators to solve the rest. It's all pretty interesting - check out Ryan Heise's website! (https://www.ryanheise.com/cube/commutators.html)

How about these problems:
Given a cube where two squares have been swapped (so it's not a valid cube anymore), how fast can you determine that it's the case?
And how fast can you shuffle it to the state that is closest to the solved state?
And for more than two swapped squares?

(speedcuber here too)
Two random squares being swapped isn't really something that happens in real life. But abstracting that, you'd notice as soon as you've placed the piece one of them is on, which is kind of hard to predict in general, it'll really depend on where it is wrt which side you started from.
What does happen in real life is two pieces ("cubies") getting swapped, say after assembling back up a popped cube. Using CFOP, you'd notice the inversion itself one sequence before the end, though you might notice the fact they're not oriented properly one sequence before that.
For more swapped pieces, (theory ahoy) there's two cases. Odd number of swaps: they're all equivalent to the case above. Even number of swaps: equivalent to no swap at all. Interestingly, you can cancel out an edge piece swap with a corner piece swap.
I hinted at it above, and it's related: no need for swaps, you can make the cube unsolvable by flipping an edge or rotating a corner in place. A CFOP solver would notice two sequences before the end. Edge flips cancel each other out by pairs; corner twists cancel each out by triplets of the same orientation. Contrary to swaps, there's no catching up a flip with a twist.
In all cases, almost-solving them is just a gasp of surprise away from solving an untainted one.

Just to let everyone know: In practice, typical speed cubes (not Rubik's brand) are loose enough where the corner can accidentally be twisted[1], and if you get to the end with a corner twisted, you can untwist it legally. Well, unless you already stopped the timer like in that video. (Similarly, if the cube pieces fall off, you can put it back together. Also, if a few pieces are swapped in a way that makes it unsolvable you could take a few pieces apart and put it together again.) [2]
[1] https://www.youtube.com/watch?v=Vg23BI6sv1w
[2] https://www.worldcubeassociation.org/regulations/#article-5-...

God 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-c...

Just 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?

I guess that's just all they needed until they were done?

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

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

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

So there is 43,252,003,274,489,856,000 positions of a Rubik's Cube? Pretty mind blowing.

And 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

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

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

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

Easier by what metric, though? Someone with moderate practice at both can do the cube faster. Someone with zero practice won't know what you mean by "sorting" a deck of cards. The cards only win at going backwards from goal to algorithm. And do we have any idea what God's Number is for sorting a deck of cards?

Depending on what you will define as an 'operation' there are some probably some easy numbers.
I think the simplest answer is 52. You need to place each card correctly once. Things get complicated if you account for searching in the deck, but we don't account for looking at the rubiks cube either.
A more interesting question is 'what if we count how far we need to move the card' (i.e. moving it from position 1 to 52 is 52 steps, and from 1 to 3 is only 2 steps).
This is a question of simple group theory though. Shuffling cards is the group S_52. The 'moving a card one position' is working with 51 simple operations of swap (idx, idx + 1). This is essentially bubble sort.

I can also do the cube faster. That's completely separate from how easy the problem is to solve for a novice.
Yes, obviously the solver has to understand what the desired solved state is in each case.
If you can't see that sorting a deck of cards is easier, I doubt I can explain it to you, but the metric I'd use is give each problem to 100 people, and see how well each group does.

"And do we have any idea what God's Number is for sorting a deck of cards?"
It depends on your definition of sorting. Since we have a known, finite, compact set of incoming inputs, essentially the numbers 1-52, as rocqua says we can use a bin sort with 52 bins and sort the cards in essentially 52 operations. This is physically practical as well. Generally the "constant overhead" on it is such that people will sort with something more like a merge sort, but it's certainly completely practical to find a space large enough to hold the entire deck laid out physically.
If you limit sorting to the computer science sense of the term, in which the sort must be accomplished by swaps, I expect it could be worked out pretty easily by people skilled in the art of sorting, again because the small constant size and input makes it relatively easy. I know it can be proved that this style of sort can't take less than O(n log n) comparisons, but I'm not 100% sure I can guarantee it's literally ciel(52 * log2 52). Somebody else may be able to.

Subtract one and it's a prime number, so you can say there are prime number of unsolved states. This is only true for some cubes of different sizes [1].
[1]: https://www.speedsolving.com/forum/threads/a-collection-of-c...

26 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! :)

Yeah, 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 :)

For a second I worried that someone had managed to post that TimeCube lunatic to HN.

I think this site is making an homage/reference to it.

Is there a position you could get the cube into, maybe by having to take it apart, that can not be solved?

Yes by taking it apart, just rotate a single corner, flip a single edge or swap two edges.

Its definitely 42 folks. https://en.wikipedia.org/wiki/42_(number)#The_Hitchhiker's_G...

To point out the obvious, that's the answer to the Life, the Universe, and Everything, not God's Number.

Well 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!

To (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?' ..."

Reply on news.ycombinator.com