God's Number is 20 (2010)
cube20.org
cube20.org
I did it with the help of programming and it is one of the coolest problems I solved (finding an algorithm to solve any instance).
Although I used a computer, it took me something like one or two month to really crack it and lots of RAM to come up with a working solution.
Fun fact: My first approach (I just knew, there was this colorful cube problem, but not that it's that hard) was a simple recursive Haskell program where I thought I could just brute force the solution in an afternoon (I did not know about the problem's math at that point, but looked it up afterwards) ... damn, was I wrong.
I remember that the approach involved restricting the operations (turning a specific side) on the cube, and by allowing just 1 side to rotate one gets len([0, pi/2, pi, 3pi/2]) == 4 solutions, but by allowing _2_ rotations the number jumps to something like ~4*10^7 combinations already.
At that point my simple wonderful Haskell program just ate up memory, and I had to rewrite it in another language (after first solving the 2x2x2 cube to keep my motivation). I tried Python (very slow) and Java (which was the fastest), but could not get rid of some GC panics, so in the end it was good old C which found the solution by encoding one state into 24 Bytes and building various fat, unbalanced binary trees, that provided a lookup-table for specific phases of the algorithm.
Granted my solution was not the best, but my point is that I would not have found it via Haskell, as I was interested in specific upper bounds to sub-problems and being memory constrained was a nightmare with Haskell (my initial program was nice, it type-checked and for sure terminated, but termination required probably a Petabyte - in any case a too big number - of RAM).
Even then <spoiler alert>, I recall vividly the moment my 10 year old self understood the 3 dimensional nature of "a side", and how a side was not solved until the top row of the each of its neighbors was also correct. It was quite an intellectual thrill for a 10 year old to make that transition.
These days I try to focus on block building rather than memorized sequences. It's a little more intellectually stimulating. If I do go the memorized sequence route, I try to string 2 such sequences together.
They say we shouldn't compare to others too much but you're sometimes kind of making it real heard HN :).
I know - I'm marvelling at the patience and effort required
All those suspended computations may eat your RAM for no good reason at all. For example:
sum (replicate n 0)
foldl' (+) 0 (replicate n 0)
My point is that it is easy to eat all your RAM using haskell even in the simple `sum` case above. More so in more involved computations.
Of course, if you can compute your solution in constant space using C, you can also do it in haskell. But writing it in Haskell would require careful thought in how your code is evaluated.
EDIT: It is about trade offs.
If you want declarative and readabe code, with little memory layout noise (allocate memory, assign variables, etc...) then haskell is a reasonable choise. You can write fairly readable clode for complex algorithms. If you are an expert, you can also make it efficient on the first go (speed and space wise). If speed is of upmost importance, then you can write more compiler specific code but with a lot of added noise.
Or you can start with C, write less (than haskell) declarative code and less readable code. It would be harder to get right(the more complex the computation the harder to debug), but when you are done you probably have efficent code. If you have the experience, you may be able to make it fairly readable too.
Full source: https://gist.github.com/k-bx/4a7729bcf2386583583b95bed7d4f26...
Also, Haskell has a nice LANGUAGE Strict pragma since recently. Won't save you from things like lazy pairs or other imported things, of course, but at least can be good for one-file scripts where you want to solve Rubic's cube.
GHC will have more trouble making the right choice in more involved computations. It will revert to "just do what the coder says".
Consider this C code for example:
unsigned int sum = 0;
const unsigned int n = 1000;
for(int i = 0; i<n; i++) {
sum += 0;
}
unsigned int sum = 0;
EDIT: format
EDIT: What I was trying to say in my original comment is that, in haskell, space leaks my appear even in the most innocent looking code. And that it may require a bit of experience to identify and avoid them.
I think GHCi is helpful in this situation, however. It clearly distinguishes between leaky and non-leaky code. This leak is a product of "just doing what the coder says" (go to "Data.Monoid.sum" and do what it says there with such and such...). I'm assuming that, for this code, GHCi is bug-free.
I think
sum (replicate n 0)
foldl (+) 0 (replicate n 0)
foldr (+) 0 (replicate n 0)
There is `{-# LANGUAGE Strict #-}`, as you mention, and BangPatterns for strict arguments. But I would assume, those are used only by coders already familiar with haskell and its leaky pitfalls.
Even in those days, it was known that it had vastly more than 20 million positions. I've wondered about the marketing guy's rationale. Obviously, "43 quintillion combinations" would not make sense to most people. But why not write, "20 billion" or "20 trillion"? Maybe it was too discouraging.
Douglas Hofstadter apparently published a correct analysis of the number of configurations in Scientific American in 1981... It's not as if it was anywhere remotely near being beyond the tools available to mathematics at the time.
(Can be transformed to C or to PDF: https://en.wikipedia.org/wiki/CWEB)
Basically mostly written with 1 and 2 chars variable names.
BTW Finding the God Number is pretty amazing!
So just your average codebase written by a mathematician? ;)
It is not unheard of that widely accepted results turn out to be false. It's rare, but it has happened. Here are some examples:
http://mathoverflow.net/questions/35468/widely-accepted-math...
From what I understand, the 12 million positions that require 20 moves is not considered definitive not completely accurate. They stated that the searches weren't looking for the optimal solution, but rather any solution that took 20 or less moves. Without the theoretical lower bound, all the exhaustive proof would demonstrate is that the upper bound is 20. I feel like the exhaustive proof of establishing a given upper bound is much easier than finding the optimal solutions for every possible position.
There are still questions pending. If you and I write bugs into our programs, they may well have done the same thing for their program that supposedly checks all cases.
The source is available and can,should be, and has been peer reviewed.
There are different kinds of pitfalls in computer proofs, and I wonder how can we account for them. The errors in a computer program are far less forgiving than the errors in a human proof. A typo in a human proof doesn't grind the whole proof to a halt and usually the human reader can quickly mentally correct the typo, but computer proofs are more brittle.
I don't really see the difference honestly, besides quantitative complexity. A computer run exhaustive proof is less brittle than a manual exhaustive proof. I think complexity of the proof is just a function of the length. And for a computer proof, that length includes the toolchain.
So, there are four extra positions for each of the rotations of the logo centre piece, and two of these pieces. Intuitively, it seems obvious this makes it harder, but I'm not sure by how much. Any ideas?
Corner pieces can be rotationally incorrect, through the solving process, and is one of the harder areas to sove on the puzzle.
o o o
S M G
o o o
There's some math in the regular wikipedia entry, not exactly your case but one for all sides requiring the right rotation relative to neighbors, which increases the state space by a factor of 4^6/2, or 2048x.
(Edit - I originally naively thought your configuration would increase the space by 16x, but the calculation is more complicated, as some configurations aren't attainable from a given starting arrangement without disassembly. So it would depend on how the two labelled faces were positioned relative to each other (ie, are they in adjacent or opposite faces), and if your definition of a solution only requires the logos to be restored per face but not the same orientation relative to the initial configuration.)
quarter turn: +- pi/2
half turn: +- piThe result was announced some 6 years ago, and there was a long discussion about it here: https://news.ycombinator.com/item?id=1587340
It was submitted again three years ago with another lengthy discussion: https://news.ycombinator.com/item?id=7374994
The other submissions had no discussion:
https://news.ycombinator.com/item?id=3921215 (1689 days ago)
https://news.ycombinator.com/item?id=1606717 (2315 days ago)
Having said all that, I hope this gets some new discussion.
The experiential difference of seeing the contextualization you put in the top-level post here, and just seeing a list of links (like you used to do) is huge. This way feels friendly like being invited into a larger conversation. A "sterile" list of previous discussion feels a little too much like "OMG repost".
I can't speak for others - but I think you hit the sweet spot of how to do the cross-connecting.
My favorite being:
> If you disassemble your cube and put it back together, there
> are 12 possible sets that you can land in. Those sets are
> not reachable from each other.
> The proof is quite elementary.https://en.wikipedia.org/wiki/God%27s_algorithm
The idea of this is that an omniscient being would know the best possible move in any configuration, and therefore might solve the puzzle in a strikingly more efficient way than an ordinary solver.
I don't know who originated the term but, if I remember correctly, it already appeared in Douglas Hofstadter's discussion of the Rubik's cube in the 1980s, so it was already current then. It was a big topic of Rubik's cube research until it was definitely solved (by the people whose work is linked above).
On the other hand, I would have thought 19 steps were enough because they already cover the full space of positions. To wit: There are 12 possible choices at each step, 19 steps cover 12^19 possibilities, which is 8 times more than the 43,000,000,000,000,000,000 positions.
Probably: https://s23.org/wiki/23