7 ms·
"God's Number" is 20 - Rubik's cube has been "solved"
- arnorhs 16y agoAs an amateur speedcuber, I am impressed. Currently I probably use around 100 moves, but my technique is obviously flawed.
- Murkin 16y agoNow you have conclusive proof that you are, indeed, not God.
- scorpion032 16y agoHe took 5 times the number of steps taken by God. So I propose, a new metric, god index, as the inverse of the number of times of the steps he takes, to the one god would. His godly index: 20%
- greyman 16y agoI am curious, what is so appealing about the speedcubing hobby? Doesn't it become boring and repetitive after some time?
- rimantas 16y agoBeating the record (your own or other's) I guess. Canabalt is even more boring and repetitive, but still addictive.
- mvarner 16y agoA good friend of mine hangs out with the 7x7 cube champion of the United States. He plays with various different kinds of Rubik's cubes, and from what I gather cubing can also get rather addicting.
- teller 16y agoMany speedcubers hit a plateau after a number of years and get bored, true, but it's a deep subject. Every solve is different and there is endless opprotunity for optimization and improvisation. And the physical dexterity aspect just adds to the fun. It would get boring only if you never improved or learned anything new. Definitely more satisfying than Sudoku or Solitaire.
- brent 16y agoIf you find Sudoku boring you just need to add more constraints. For example, try solving one by considering some ordering on the entries (say, Left-to-Right then Top-to-Bottom) and only allow yourself to fill in entries in that order... then time yourself!
- Locke1689 16y agoSudoku is very boring. If I wanted to spend my time solving small value NP-complete problems I might as well go out and solve TSPs over and over again.
- 5teev 16y agoI saw a guy solving a cube with only one hand, thus freeing the other hand to do the same thing, more or less.
- arnorhs 16y agoIt's the perfect thing to do while you're watching videos or listening to podcasts. I can't really watch anything or listen to a podcast at the same time that I'm coding. But there is still stuff I really want to watch. This week in startups and some Mixergy shows etc. But only sitting there watching videos can be very boring, so it's good to have something to do with your hands. Also. There are so many formulas, techniques, etc. You gradually gain a greater understanding of how the cube works, etc. I recommend it. Great hobby. But don't be one of those losers that tries to impress a whole party by solving one, it's really lame to cubists.
- AndrewWarner 16y agoI always wonder what people do while listening to my interviews. Cool.
- arnorhs 16y agoyes, and they are awesome, Andrew. Keep up the good work!
- scorpion032 16y agoSo, your godly index is 0.2 :) PS: Same here.
- jacquesm 16y agoSo, they've brute forced the problem and they now know that there are no positions that need more than 20 moves, but that does not get you closer to developing an algorithm giving you those 20 moves (edit: or however many that configuration takes). Is there any progress on the algorithmic front?
- dan_netwalker 16y agoI'll make an educated guess... the advancement is knowing that if you make a machine that can bruteforce 6 sides x 2 turn directions, you can stop searching once a 20th movement is not enough to get the cube solved, and in the worst scenario, you will check ( 6 x 2 )^20 movements in total. I think that scores as test cases :P
- randomwalker 16y agoI think you're confused -- they went the other way around, using the algorithm to find the optimal number. Search techniques that can quickly solve any cube with a small (near-optimal) number of moves have been known for a while, mainly due to the work of Kociemba: http://www.jaapsch.net/puzzles/compcube.htm#kocal http://www.jaapsch.net/puzzles/compcube.htm#kocal The techniques used are standard AI tree/graph search algorithms with lots of Rubik's cube-specific optimizations. A few years ago, these methods became good enough to solve almost any cube quickly within 20 moves (which was conjectured to be God's number.) So the algorithm as well as a fast implementation already existed. Here's Kociemba's page http://kociemba.org/cube.htm http://kociemba.org/cube.htm and here's an iPhone app with a neat twist: you can photograph your physical cube to solve it http://www.wired.com/epicenter/2009/01/iphone-app-solv/ http://www.wired.com/epicenter/2009/01/iphone-app-solv/ What these guys did was to make further optimizations and run it on a cluster to search through all possible position sets. As they say, they can solve about 4000 positions/s (in 20 moves or less) on a single machine.
- Vivtek 16y agoThis, and P ne NP on the same day - clearly I can resign my post at the patent office now; everything has already been solved.
- elblanco 16y agoWell there you go, I think we're all done here now.
- eru 16y agoPerhaps somebody can still come up with an improvement on the 1-click checkout of Amazon?
- noonespecial 16y ago0-click. They decide what I want, send it to me, and then bill me. Pay me.
- kazuya 16y agoIf shipment cost is reasonably low, just deliver predetermined items (e.g. those recommended by Amazon) to customers, have them pay for what they consumed and return the rest. Or, if storage cost at customers is low and items do not perish, leave the items they didn't consume at their site. Later they may find them useful and pay for them. This is actually the model employed by some of medical drug resellers in Japan.
- faboo 16y agoIsn't this what record and bookclubs were? (are? I haven't seen hide nor hair of one of those in a long time)
- marklittlewood 16y agoWith Amazon recommendations this could go badly wrong. 'People who previously bought books, also bought books. We sent you our entire fracking catalogue'
- vog 16y ago
- slig2 16y agoAny guesses of how much this would cost to do on EC2?
- fragmede 16y agoRoughly $43000, using spot-instances. Back of the envelope... From the link, it would take 1.1 billion seconds @ 4x 2.8ghz = 4.4 billion @ 2.8 Ghz = 12.32 billion seconds @ 1 Ghz = ~3430000 hours Using ec2 unit performance as 1Ghz, assume computing is comparable, Ghz for Ghz (it isn't...), and storage and xfer is negligible. Normal instances instance-size|ec2units | $/hr | $ total sm | 1 | 0.085 | 291550 large | 4 | 0.34 | 291550 xl | 8 | 0.50 | 214375 himem-xl | 6.5 | 0.69 | 364108 himem-double-xl | 13 | 1.20 | 316615 himem-quad | 26 | 2.40 | 316615 hicpu-med | 5 | 0.17 | 116620 hicpu-xl | 20 | 0.68 | 116620 cluster | 33.5 | 1.60 | 163821 Using spot instances sm | 1 | 0.031 | 106330 large | 4 | 0.14 | 120050 xl | 8 | 0.245 | 105044 himem-xl | 6.5 | 0.172 | 90763.1 himem-double-xl | 13 | 0.427 | 112662 himem-quad | 26 | 0.871 | 114905 hicpu-med | 5 | 0.06 | 41160 hicpu-xl | 20 | 0.249 | 42703.5
- bd 16y agoWith some handwaving it could be about $82.5K (computation spread over 1 year) or $125K (computation done in 1 month). total cost was 35 CPU years (Intel Nehalem, 4-core, 2.8GHz) 1 EC2 compute unit is about 1 GHz Xeon let's assume 1 Google unit = 12 EC2 units (3x4 cores) High-CPU Extra Large instance = 20 EC2 units 35*12 = 420 EC2 unit years = 5040 EC2 unit months = 21 HiCPU XL instances for 1 year = 252 HiCPU XL instances for 1 month Putting this into AWS calculator [1] yields: $82,491.36 (21 HiCPU XL reserved instances for 1 year) $125,435.52 (252 HiCPU XL on-demand instances for 1 month) [1] http://calculator.s3.amazonaws.com/calc5.html http://calculator.s3.amazonaws.com/calc5.html ------ Edit: It could be actually a bit more, Nehalems seem to be faster than my first estimate. Plugging in EC2 computing unit comparison from Cluster Compute instance (which has 2x quadcore Nehalem), 1 Google unit can be 16.75 EC2 units. This gives: $114K for 1 year of 29 reserved HiCPU XL instances $166K for 1 year of 18 reserved cluster compute instances $173K for 1 month of 348 on-demand HiCPU XL instances $246K for 1 month of 210 on-demand cluster compute instances ----- Edit2: Dedicated server hosting would be much cheaper. For example, from Hetzner [2] it would cost just about 26K EUR (= $34K) to rent 35 dedicated quadcore Nehalem servers for 1 year. [2] http://www.hetzner.de/en/hosting/produktmatrix/rootserver-produktmatrix/Produktmatrix http://www.hetzner.de/en/hosting/produktmatrix/rootserver-pr...
- acangiano 16y ago> With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, This is the wrong time to use the adverb "essentially". You either solved every position or you didn't.
- pohl 16y agoI'd agree with you had they used a weasel-word like "virtually", but "essentially" seems appropriate in this case: adverb: used to emphasize the basic, fundamental, or intrinsic nature of a person, thing, or situation If you didn't actually iterate through every position - but rather a subset that provided equivalent coverage by eliminating symmetries - then you have, in essence, solved every position.
- acangiano 16y agoFair enough. I was in a rush so I didn't read the whole page. Considering their approach, essentially is appropriate.
- Avshalom 16y agoWell they didn't actually "solve" every position, they just found a solution under 20 moves for every position.
- smallblacksun 16y agoThey didn't optimally solve every position, but they did solve every position.
- drallison 16y agoSomewhat off point, but the site cube20.org kills Firefox but views OK in Chrome. Firefox reports a seg-fault somewhere.
- JoeAltmaier 16y agoAlso proves that all possible cubes are reachable, since they can all be solved.
- gojomo 16y agoHmm... I'm sure someone with more experience will chime in, but I recall reading in a Scientific American years ago that removing a particular piece from the cube then reinserting it wrong could yield a non-solvable configuration. So I think your statement is only true if you define 'possible' and 'reachable' as synonymous, making it tautological. There are still 'cubes' that look plausible, with the right number of faces of each color and adjacent-faced-pieces, that are still unsolvable.
- eru 16y agoIf 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.
- soundsop 16y agoI see that cube21.org also resolves to the same site, so I guessed they hedged their bets.
- rradu 16y agoThis is cool and all, but couldn't that computing power have gone to greater use? There is a ton of medical research going on that could have been helped by Google's donation.