# Is a \*Knight's Tour\* style procedure mathematically possible for Rubik's Cube? **URL:** \ **Category:** Factual Questions\ **Created:** [May 19, 2014, 11:37am UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724 "2014-05-19T11:37:48Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [May 19, 2014, 11:37am UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/1 "2014-05-19T11:37:48Z")
Spin off from [this](http://boards.straightdope.com/sdmb/showthread.php?t=723700)thread. 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? ---
**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\ **Post date:** [May 19, 2014, 2:10pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/2 "2014-05-19T14:10:38Z")
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](http://bruce.cubing.net/ham333/rubikhamiltonexplanation.html), which I only skimmed the top of, but seems directly relevant to your question. ---
**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\ **Post date:** [May 19, 2014, 2:29pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/3 "2014-05-19T14:29:24Z")
[Here’s another site](http://godplaysdice.blogspot.com/2008/10/upper-bound-for-order-of-element-of.html), with some discussion about what I remembered. It looks like the maximum cycle length is 1260 (possibly less, depending on who you believe). ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [May 19, 2014, 4:21pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/4 "2014-05-19T16:21:12Z")
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. ---
**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\ **Post date:** [May 19, 2014, 5:02pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/5 "2014-05-19T17:02:52Z")
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. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [May 19, 2014, 5:27pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/6 "2014-05-19T17:27:44Z")
These comments are still useful in exploring the shape of the problem, so thanks. ---
**Author:** ![Malacandra](https://avatars.discourse-cdn.com/v4/letter/m/45deac/32.png) [@Malacandra](https://boards.straightdope.com/u/Malacandra)\ **Post date:** [May 20, 2014, 7:05am UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/7 "2014-05-20T07:05:46Z")
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. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [May 20, 2014, 7:23am UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/8 "2014-05-20T07:23:29Z")
Already noted. ---
**Author:** ![Malacandra](https://avatars.discourse-cdn.com/v4/letter/m/45deac/32.png) [@Malacandra](https://boards.straightdope.com/u/Malacandra)\ **Post date:** [May 20, 2014, 9:39am UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/9 "2014-05-20T09:39:43Z")
Huh. Didn’t see where it said that. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [May 20, 2014, 10:05am UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/10 "2014-05-20T10:05:52Z")
No problem. If we implement this, I’ll distribute the task across a team of 10[sup]18[/sup] monkeys (or more) ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [May 20, 2014, 4:22pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/11 "2014-05-20T16:22:09Z")
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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Hamiltonian_path) 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. ---
**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\ **Post date:** [May 20, 2014, 4:57pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/12 "2014-05-20T16:57:29Z")
> [@ftg](#): > > 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: > [@](#): > > At last, the Hamiltonian circuit problem for Rubik’s Cube has a solution! To be a little more mathematically precise, a Hamiltonian circuit of the quarter-turn metric Cayley graph for the Rubik’s Cube group has been found. > > Basically it is a sequence of quarter-turn moves that would (in theory) put a Rubik’s cube through all of its 43,252,003,274,489,856,000 positions without repeating any of them, and then one more move restores the cube to the starting position. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 20, 2014, 6:46pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/13 "2014-05-20T18:46:07Z")
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. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 20, 2014, 6:58pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/14 "2014-05-20T18:58:42Z")
> [@Chronos](#): > > Of course, for a truly general graph, the Hamiltonian circuit problem and variations of it are exceedingly difficult (probably NP-hard) 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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 20, 2014, 7:47pm UTC](https://boards.straightdope.com/t/is-a-knights-tour-style-procedure-mathematically-possible-for-rubiks-cube/688724/15 "2014-05-20T19:47:49Z")
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.