Spin off from thisthread.
Ignoring the length of time it would take to try it (possibly longer than the lifetime of the universe, I suspect), is it mathematically possible to visit each and every one of the 43,252,003,274,489,856,000 different possible configurations of a Rubik’s Cube, without ever repeating a combination?
I remember reading of people trying to maximize the cycle length of a fixed set of moves. The cycle length was the number of moves to return to solved, divided by the number of moves in your fixed set. So if your set was jut rotate the top 1/4 turn, your cycle length was 4. If your set was top 1/4, right 1/4, and that returned to solved after 24 moves, the cycle length would be 24/2 = 12.
My memory is really hazy on how long the longest cycle length was at the time, but I think it was on the order of hundreds, give or take a factor of ten. No where near what you would need to hit every permutation.
OK, I did a little searching, and found a page titled A Hamiltonian circuit for Rubik’s Cube, which I only skimmed the top of, but seems directly relevant to your question.
Here’s another site, with some discussion about what I remembered. It looks like the maximum cycle length is 1260 (possibly less, depending on who you believe).
I guess the question is whether those cycles can be truncated by one move each (so they dont quite repeat), then seamlessly linked up into one long sequence.
If the 1260 figure is correct, you could potentially come up with a 34,326,986,725,785,600-turn sequence which, when repeated 1260 times, would cycle through all possible permutations of the cube. No smaller sequence would work.
Not really in the spirit of your OP, I would guess.
These comments are still useful in exploring the shape of the problem, so thanks.
Note that the number of positions you quote is a couple of orders of magnitude bigger than the number of seconds since the Big Bang, which is only a piddling 10[sup]18[/sup] or so. So you’d better get your time down to milliseconds for each position if you want to get it done before the heat death of the Universe, for a start.
Already noted.
Huh. Didn’t see where it said that.
No problem. If we implement this, I’ll distribute the task across a team of 10[sup]18[/sup] monkeys (or more)
In the close but no cigar department …
Consider the set of configurations reachable from the start position as a set of nodes in an undirected graph. An edge connects two nodes (positions) if there is a simple move (90, 180, 270 degree turn of one face) that gets you from one position to the other.
Since each node has degree 18, that means there is an Euler tour where each edge is visited exactly once. But in the process, you would visit each node (position) 9 times.
I.e., it’s possible to go thru all reachable moves on a Rubik’s cube without repeating the same move twice.
Visiting each node in a graph once is a Hamiltonian cycle which is a much, much nastier thing to solve in general. Even the general version of, say, “Visit at least half the nodes just once.” is just as hard as the full problem.
Any argument about number of positions reached without repetition has to avoid anything like solving the Hamiltonian cycle problem.
In the link in my first reply, that’s what they claim has been done:
Of course, for a truly general graph, the Hamiltonian circuit problem and variations of it are exceedingly difficult (probably NP-hard), but for a graph with symmetries or other special properties, one can often find a solution via some cleverness or another. And the graph of the Rubik’s Cube group is extremely symmetric.
Did you mean “provably” instead of “probably”? Because the Hamiltonian circuit problem is provably NP-hard; it’s just not clear if that makes it not P-easy.
I meant “probably”, because I wasn’t sure if it had been proven or not. I’m not at all surprised to hear that it has been.