15 ms·
God's Number is 20 (2010)
- nocman 10y agoHahaha -- I saw this and immediately thought it was that crazy "Timecube" guy again! :-D http://timecube.2enp.com/ http://timecube.2enp.com/
- RiderOfGiraffes 10y agoPrevious discussions are closed now, of course, but in case anyone is interested in the HN thoughts and opinions, here are some links. The result was announced some 6 years ago, and there was a long discussion about it here: https://news.ycombinator.com/item?id=1587340 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 https://news.ycombinator.com/item?id=7374994 The other submissions had no discussion: https://news.ycombinator.com/item?id=3921215 https://news.ycombinator.com/item?id=3921215 (1689 days ago) https://news.ycombinator.com/item?id=1606717 https://news.ycombinator.com/item?id=1606717 (2315 days ago)
- genericacct 10y agoThanks for reposting. i had missed this.
- RiderOfGiraffes 10y agoI always hesitate - some people hate it, others appreciate it. I think it's worth cross-connecting previous conversations, because I see the HN discussions as a resource. Others seem to think it should all be ephemeral and throw-away. Having said all that, I hope this gets some new discussion.
- shshhdhs 10y agoI think of it as a public service, so others don't have to do the same. Thanks!
- sophacles 10y agoThis jarred loose a memory... You and I discussed this here once, years ago: https://news.ycombinator.com/item?id=227579 https://news.ycombinator.com/item?id=227579 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.
- dorianm 10y agoThe quality of the comments is surprisingly high: a AWS analysis, some maths, etc. 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.
- benibela 10y agoThere are even more sets if you start painting the sides
- dorianm 10y agoSource code is in CWeb: http://cube20.org/src/ http://cube20.org/src/ (Can be transformed to C or to PDF: https://en.wikipedia.org/wiki/CWEB https://en.wikipedia.org/wiki/CWEB) Basically mostly written with 1 and 2 chars variable names. BTW Finding the God Number is pretty amazing!
- dom0 10y ago> Basically mostly written with 1 and 2 chars variable names. So just your average codebase written by a mathematician? ;)
- blt 10y agosometimes, an algorithm is so intricate that it can only be understood by reading the paper. in this case, it's much more useful to make the variable names match the paper than to attempt semantic variable names.
- deleted 10y ago[deleted]
- crypto5 10y agoWhy is it "God's"?..
- lgas 10y agohttps://en.wikipedia.org/wiki/God's_algorithm https://en.wikipedia.org/wiki/God's_algorithm
- wincy 10y agoThere's a link in the article to Wikipedia. Basically that an omniscient being would know the shortest number of moves on a Rubik's cube, so the most number of moves "God" would take to solve a Rubik's cube would be 20. https://en.m.wikipedia.org/wiki/God's_algorithm https://en.m.wikipedia.org/wiki/God's_algorithm
- schoen 10y agoIt's named for the idea of "God's algorithm", which is a perfect optimal solution to a puzzle like the Rubik's cube from any position. https://en.wikipedia.org/wiki/God%27s_algorithm 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).
- crypto5 10y agoThank you. Nit: It seems like Rubik's God's number would be better naming, because other puzzles would have different God's numbers..
- schoen 10y agoTrue! I guess in this case the Rubik's cube enthusiasts first coined the term, and the question was most discussed and studied in that community, so for them the intended reference was still clear even though the concept had also been applied to other puzzles.
- mysterypie 10y agoFunny story: When the Rubik's Cube first came out, the box proudly proclaimed: "More than 20 million combinations!" 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.
- theoh 10y ago"Even in those days"? 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.
- 505 10y agoAt some point before 1985, an algorithm was found that could solve it in 21 "twists". (Just checked in my old copy of Hofstadter's Metamagical Themas.)
- BurningFrog 10y agoThis is not true. Back in those days the best known method needed 52 moves (Thistlethwaite).
- jordigh 10y agoWow, yet another result found by computer proof. Mathematics is getting weird. Maybe there is some metamathematical proof that the computer proof was produced in the correct fashion. My puny human brain wants reassurance that this proof is correct. 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-mathematical-results-that-were-later-shown-wrong/35558 http://mathoverflow.net/questions/35468/widely-accepted-math...
- ibejoeb 10y agoThis is years old and I'm not familiar with it, but generally, the proof is among the simplest and most straightforward, right? If I read it right, it's proof by exhaustion. The trick is that it was previously impractical.
- phamilton 10y agoI think in this case, the lower bound was theoretically proven, and now exhaustively it has been determined that there are no positions which exceed the theoretical lower bound. I'm pretty comfortable with that conclusion. 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.
- jordigh 10y agoAnd how do you know the exhaustion was done correctly? What was the process that lead to it? Is that process correct? Could they have forgot to check some cases? How do we know they didn't? 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.
- protomikron 10y agoIf you did not solve the Rubik cube (or did not investigate it in general), I highly advice you to try solving it on your own. Just read nothing about it. 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).
- phamilton 10y agoThis is one of my biggest regrets: learning to solve it at a young age (10) and not actually solving it, but rather learning an existing algorithm. I have had much satisfaction as an adult in solving 4x4 and 5x5 cubes, but even that tends to be derivative of existing 3x3 solutions (though I did create some sequences myself and those proved easier to scale that traditional ones). 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.
- uptownfunk 10y agoWhat is gods number for a 2x2x2 cube?
- protomikron 10y ago11 (quarter and half turns) or 14 (only quarter turns). You can brute-force that in your favorite language (there are ~3.5*10^6 configurations). quarter turn: +- pi/2 half turn: +- pi
- dtwhitney 10y agowell... I'm glad we know
- iamtew 10y agoI'd expect it to be 23.
- tajen 10y agoWhy? I remember using a simple program in 2000 to see how many moves were canonically required, and most positions I came up with were resolved in 13 moves. 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.
- schwarze_pest 10y ago> Why? Probably: https://s23.org/wiki/23 https://s23.org/wiki/23
- ForFreedom 10y agointeresting
- grkvlt 10y agoI have a cube that I got as conference swag which they made unintentionally harder to solve. There are two sides where the three middle pieces (number 4, 5 and 6 if you think of the arrangement of numbers on a numeric keypad) have a logo printed across them - 'Samsung' in fact. The middle of the three pieces is therefore constrained to be in a certain orientation (normally rotations of that square would not matter) and therefore symmetry is broken. 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?
- deleted 10y ago[deleted]
- jimminy 10y agoThat wouldn't make it any harder. Sides only have a single orientation, with the opposite side suited to the center piece of one of the neighboring sides. Placing the piece with the correct neighboring side addresses the issue automatically. Corner pieces can be rotationally incorrect, through the solving process, and is one of the harder areas to sove on the puzzle.
- grkvlt 10y agoNo, the center piece on a particular side has a preferred orientation with regards to the pieces on its left and right assuming the cube is like this, with S M G standing for the Samsung logo and o being a standard plain coloured square: o o o S M G o o o The M piece must be correctly positioned to align with the S and G pieces, if it is rotated the logo will look wrong. Obviously if they were plain coloured squares the rotation would not matter.
- jeffwass 10y agoIt's almost a "supercube" : https://www.speedsolving.com/wiki/index.php/Supercube https://www.speedsolving.com/wiki/index.php/Supercube 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.)
- brownbat 10y agoPretty amazing that in the quarter-turn metric, only one confirmed state requires the full 26 moves. http://cube20.org/qtm/ http://cube20.org/qtm/
- taotao670 10y agoThose interested in the field of Algebra, the Rubik's cube makes a great topic of research. You'll learn about the Rubik's cube group and how it is a subgroup of S_{48}. For a project I had this semester, I wanted to use Algebraic components of the cube to come up with algorithms for solving it, but I did not have the time.