Since there's been such thoughtful silence on the Rubik's Cube problem, I thought I'd barge in with more amateur thoughts. First of all, I said that 6,576,625,523 (the square root of the number of Rubik's positions) x 10 bytes per position is about 66 terabytes, but it's only 66 gigabytes. But now it seems to me that the Rubik's cube is not a square-root meet- in-the-middle type of problem. That is, if you graph how many positions you can get to in a given number of moves, you get a sigmoid curve, reaching half (not the square root) of the possible positions in half the maximum number of moves. Thinking that your odds of going backwards goes up like the number of positions you've covered so far. Am I getting this wrong? or looking at something irrelevant? On the other hand, would it be useful to have just the raw numbers of positions at distances up until you ran out of disk space? Would it help to know just how many moves it takes to get to the square root? Would that number help focus the search for the actual diameter? How much effort and space can be saved by having a list of symmetries, and only storing canonical representatives of positions? Er, is that where the square root comes in? --Steve
From: "Schroeppel, Richard" <rschroe@sandia.gov>
Has the diameter of the Rubik's cube puzzle been established yet? We now have enough computing power to find & prove the distance- to-start for any particular position, using the obvious square-root meet-in-the-middle algorithm and a big disk. We can search for edge positions by generating random positions and using the exact distance algorithm to guide a hill-climb away from the start position. But this is only heuristic.
From Steve Witham <sw@tiac.net> http://en.wikipedia.org/wiki/Rubik%27s_Cube_group says that the number of positions is ( 8! 3^8 12! 2^12 ) / 12 = 43,252,003,274,489,856,200 so the square root is about 6,576,625,523
Each position needs about 5 bytes, and I guess having two copies of the set would make it go a lot faster, so that's 66 terabytes...by my amateur guess.
From: Jason Holt <jason@lunkwill.org>
If somebody is serious about coding up an algorithm, let's work up some resource estimates and I can ask if we can get them for this important bit of mathematical research. I work for a company that reportedly has servers spread in at least 25 locations around the world.