# Hamiltonian Circuit for a 1x1x1 cube



## ortwin (Feb 7, 2016)

Hamiltonian circuit for a 1x1x1 cube.

To make a 1x1x1 cube even more of a challange, one could acount for the orientation of the cube when it sits on the table.
For instance one could definde the position as solved when the white face is on top and the green face is showing towards the observer
(F : green; U: white).
With this you would have 24 distinct states of the cube. Gods number is 2 in htm and it is 3 in qtm.

A path through all possible states of the cube that starts and end in the solved position (hamiltonian circuit, devil's algorithm) is this one:
FRU BLD FRU BLU FRU BLD FRU BLU
https://alg.cubing.net/?puzzle=1x1x1&alg=FRU_BLD%0AFRU_BLU%0AFRU_BLD%0AFRU_BLU


and this is another one:
UUUF UUUF' UUUF' UUUF UUUF U'U'U'F
https://alg.cubing.net/?puzzle=1x1x1&alg=UUU%0AF______%2F%2F_move_blue_up_%0AUUU%0AF-_____%2F%2F_move_orange_up%0AUUU%0AF-_____%2F%2F_move_yellow_up%0AUUU%0AF_____%2F%2F__move_green_up%0AUUU%0AF_____%2F%2F__move_red_up%0AU-U-U-%0AF____%2F%2F___back_to_start

open questions: how many different "hamiltonian circuits" do exist for the 1x1x1 cube ?


----------



## whauk (Feb 7, 2016)

I thought this thread was a joke but it is actually an interesting question. No new insights yet but it might be easier to consider the rotation cube of the group as S4 (symmetric group over a 4 element set) by the isomorphism:
x to (1234)
y to (1324)
z to (1243)
(Do we have LaTeX build into the forum? I think I saw it sometimes...)
In order to see that this works assign 1,2,3,4 to a set of two antipodal corners and observe the permutations given by x,y,z.


----------



## cuBerBruce (Feb 8, 2016)

I came up with a trivial upper bound of 6*(5^18)*4*3*2 = 549316406250000 < 550 trillion (for QTM, of course). So I concluded this could probably be calculated with rather brute force techniques.

So I wrote a program, and I got the following values for the number of paths of length n that don't visit a node more than once (for n = 1 to 23). The starting node is considered visited.


```
n       count
  1           6
  2          30
  3         150
  4         696
  5        3264
  6       13848
  7       59328
  8      228192
  9      886752
 10     3041760
 11    10541184
 12    31616400
 13    95821056
 14   244183104
 15   628072992
 16  1302752640
 17  2724479616
 18  4302952704
 19  6842868480
 20  7296624384
 21  7825910784
 22  4218607104
 23  2286208512
```

This suggests that there are 2,286,208,512 total Hamiltonian paths (length 23).

I altered the program to find how many of these Hamiltonian paths can reach the starting node using one more quarter turn. Slightly over half of them did, for a total of 1,151,330,304 Hamiltonian circuits.

I note that some might consider a cyclic shift to be essentially the same Hamiltonian circuit. One might also consider symmetrical variants and even inverses to be essentially the same. My program did not attempt to reduce the count due to these considerations.


----------



## shadowslice e (Feb 8, 2016)

Is it possible to return to the same position (same orientation) in an odd number of moves when using QTM?

My intuition says no but if anyone has a more concrete answer or counterexample that would be great.

Because that would be interesting as though Hamilton cycles could exist, there would never be a cycle of an odd length.

And also it would mean that the calculations for the total positions slightly simpler because you would only need to look at which faces had been covered an even number of "turns" away so could halve the amount of work essentially.

And also would it mean that you only need to check if certain faces had been covered because the others would be an odd number of turns away from the start so could not come up.

Actually, I suppose it wouldn't be quite that simple.

Sorry if this was a bit confusing; it was just a stream of consciousness kind of thing.

EDIT: also, would this hold true for any cube? (ie the odd or even number of moves in QTM will also be the same as in the solution (eg a scramble is 23 moves long and the solution is 67 moves (slices count as 2 and rotations count as 3 for each quarter turn on a 3x3 etc))).


----------



## Cale S (Feb 8, 2016)

shadowslice e said:


> Is it possible to return to the same position (same orientation) in an odd number of moves when using QTM?
> 
> My intuition says no but if anyone has a more concrete answer or counterexample that would be great.


You can think of each "move" as a 4-cycle of faces, which affects parity, so an odd number of moves always has parity


shadowslice e said:


> EDIT: also, would this hold true for any cube? (ie the odd or even number of moves in QTM will also be the same as in the solution (eg a scramble is 23 moves long and the solution is 67 moves (slices count as 2 and rotations count as 3 for each quarter turn on a 3x3 etc))).


Skewb doesn't have parity and you can do an odd number of moves to return to solved (I think this also works for pyra and mega, not sure though)


----------



## shadowslice e (Feb 8, 2016)

Cale S said:


> You can think of each "move" as a 4-cycle of faces, which affects parity, so an odd number of moves always has parity


So... Was my intuition correct?



> Skewb doesn't have parity and you can do an odd number of moves to return to solved (I think this also works for pyra and mega, not sure though)



Yeah, I was mostly talking about N*N*N cubes and I don't think megaminx would work (because you have no real parity because it is all one parity orbit). IDK much about skewb though. Can it rotate to the the same position on 1 axis in 3 moves? That would make sense as it would need to be an even rotation on each side if my logic was to work.


----------



## Cale S (Feb 8, 2016)

shadowslice e said:


> So... Was my intuition correct?


yeah



shadowslice e said:


> Yeah, I was mostly talking about N*N*N cubes and I don't think megaminx would work (because you have no real parity because it is all one parity orbit). IDK much about skewb though. Can it rotate to the the same position on 1 axis in 3 moves? That would make sense as it would need to be an even rotation on each side if my logic was to work.



You could just do U5 on megaminx and U3 on pyraminx/skewb, the fact that it takes an odd number of one face turn to return to solved is why these puzzles don't get parity (they only do odd-numbered cycles with every move)


----------



## ortwin (Feb 9, 2016)

cuBerBruce said:


> I came up with a trivial upper bound of 6*(5^18)*4*3*2 = 549316406250000 < 550 trillion (for QTM, of course). So I concluded this could probably be calculated with rather brute force techniques.
> 
> So I wrote a program, and I got the following values for the number of paths of length n that don't visit a node more than once (for n = 1 to 23). The starting node is considered visited.
> 
> ...



Such big numbers in such a small cube.......
In those more than one billion hamiltonian circuits that exist, is there on that has only two or three types of moves?
The one I posted above (UUUF UUUF' UUUF' UUUF UUUF U'U'U'F) has four types of moves along two axes.

And is there a hamiltonian circuit where every type of move appears exactly four times and not the same move twice in a row?
Again one of the circuits I found (FRU BLD FRU BLU FRU BLD FRU BLU) is close to that goal, but "D" apperas only twice and "U" six times.


----------



## cuBerBruce (Feb 10, 2016)

ortwin said:


> Such big numbers in such a small cube.......
> In those more than one billion hamiltonian circuits that exist, is there on that has only two or three types of moves?
> The one I posted above (UUUF UUUF' UUUF' UUUF UUUF U'U'U'F) has four types of moves along two axes.



There are none that use only two of the six types of quarter turns.

Of the 191,888,384 that start with U, there are 40,768 that use only two axes, and there are 5,736 that use only three different quarter turns. Of the 5,376 using only three types of turns, 656 use only two axes. An example is: UUUR URUU URUR UUUR DRUR URDR



ortwin said:


> And is there a hamiltonian circuit where every type of move appears exactly four times and not the same move twice in a row?
> Again one of the circuits I found (FRU BLD FRU BLU FRU BLD FRU BLU) is close to that goal, but "D" apperas only twice and "U" six times.



Yes, for example:
UFUF URBR DFDF LBRD LDBL URBL

Another example can be divided into 3-move pieces where each piece contains a move on each axis. Note the axes are not in the same order in all 3-move pieces.
UFR UBL DLF DLF UBL UFR DRB DRB

----------------

I'll also note that the most a single type of turn is used is 16. An example is:
UUUF UUUF UUUB UUUB UBUL UFUB


----------



## ortwin (Feb 10, 2016)

@Bruce
Many thanks for sharing all those interesting results! For me there are no further open questions at the moment regarding the 1x1x1.
A visualisation of the Hamiltonian Circuit for the 2x2x2 you found is something that belongs into a different thread......


----------



## ortwin (Feb 12, 2016)

The "moment" that I mentioned in the last post has passed.

Seeing what complications and big numbers the accounting for the full orientaion of the cube led to, I like to consider now only the orientation of the cube regarding lets say the color of the top face. This should result in math that even I can tackle without a computer.
Lets define that position as the solved one, when the white face is on top.
With this you would have only 6 distinct states of the cube. Gods number is 1 in htm and gods number is 2 in qtm.
*In htm the number of all hamiltonian circuits would simply be 5! =120*

In qtm there are eight different hamiltonian circuits that start with a* L *move:

*L F L F L F
L L F L L F
L F L L F L
L F F L F F

L B L B L B
L L B L L B
L B L L B L
L B B L B B
*https://alg.cubing.net/?puzzle=1x1x1&alg=L_F_L_F_L_F%0AL_L_F_L_L_F%0AL_F_L_L_F_L%0AL_F_F_L_F_F%0A%0AL_B_L_B_L_B%0AL_L_B_L_L_B_%0AL_B_L_L_B_L%0AL_B_B_L_B_B%0A
So I if you take in account all four possible starting moves, you have *32 different hamiltonian circuits for a 1x1x1 that is regarded as solved when a specific colour is pointing up.
*

If one considers a cyclic shift to be essentially the same Hamiltonian circuit and one also considers symmetrical variantsto be essentially the same, the count due to these considerations is *reduced to only two circuits:
L F L F L F
L L F L L F
*
I note that one can not combine any of these hamiltonian circuits to get a hamiltonian circuit for the 1x1x1 cube where the full oriantation matters. The reason for that is, that (by chance?) all the hamiltonian circuits here preserve the full orientation of the cube.


----------



## cuBerBruce (Feb 13, 2016)

ortwin said:


> Seeing what complications and big numbers the accounting for the full orientaion of the cube led to, I like to consider now only the orientation of the cube regarding lets say the color of the top face. This should result in math that even I can tackle without a computer.
> Lets define that position as the solved one, when the white face is on top.
> With this you would have only 6 distinct states of the cube. Gods number is 1 in htm and gods number is 2 in qtm.
> *In htm the number of all hamiltonian circuits would simply be 5! =120*
> ...



I think maybe you should just list the order you that the graph vertices are visited, rather than your "LFL..." notation for describing the Hamiltonian circuits. It's like you're saying you are using a 6-vertex graph, but each vertex has 4 different ways of labeling the edges, depending how you reach each vertex.

If we start the circuit going from U to B (corresponding to your initial "L" move), then we get the eight Hamiltonian circuits represented by:
UBLDFR
UBDLFR
UBLDRF
UBLFDR
UBRDFL
UBDRFL
UBRDLF
UBRFDL

If we want to have 6-vertex Cayley graph, we could use a cyclic group of order 6.

For example. we could define a generator "a" of order 6 that cycles through the vertices U, R, F, D, L, B in that order. For our Cayley graph, we can define a 2nd generator b = a[sup]2[/sup]. Then we can describe the Hamiltonian circuits in terms of the "moves" a and b and their inverses a' and b'.


----------



## ortwin (Feb 16, 2016)

cuBerBruce said:


> I think maybe you should just list the order you that the graph vertices are visited, rather than your "LFL..." notation for describing the Hamiltonian circuits.



I guess I did it like that first and then I deduced that LFL... way to describe it from that. The LFL notation can be put directly in to that applett at alg.cubing.net .
Another advantage is that symmetries are easily visible. 
I find it noteworthy that there does exist not a single Hamiltonian circuit that makes use of more than two different types of moves. 
One of these days I have to go more into theory and find out what "Cayley graphs" are and so on...


----------



## ortwin (Feb 24, 2016)

For the 1x1x1 cube the hamiltonian circuit can be depicted by a line on a cube that passes through the 24 positions that need to be brought to the Up/Front position for the cube to go through all possible orientations. Okay, I am not sure this sentence is making sense by itself, but I think the example shown can help.



The example shows a path that is special in that it never intersects itself. It corresponds to the Hamiltonian circuit (UUUR U'U'U'R')x3 .

The faces not shown look quite similar to those shown. The hamiltonian circle here is drawn on a 3x3x3 cube just because it was the easiest way for me to do it, the software I used does not offer an 1x1x1 cube.


----------



## mikebolt (Mar 20, 2016)

ortwin said:


> One of these days I have to go more into theory and find out what "Cayley graphs" are and so on...



You're in luck. Last week I made a visualization of the 1x1x1's Cayley graph as a matrix, right here: https://i.imgur.com/7ci7F6U.png

Here's the actual graph version of it, but it's kind of messy: https://i.imgur.com/8V6Nbiy.png

And I have attached a JSON file with the graph: View attachment cube_rotation_cayley_graph.txt


----------



## Lucas Garron (Mar 20, 2016)

mikebolt said:


> You're in luck. Last week I made a visualization of the 1x1x1's Cayley graph as a matrix, right here: https://i.imgur.com/7ci7F6U.png
> 
> Here's the actual graph version of it, but it's kind of messy: https://i.imgur.com/8V6Nbiy.png



That doesn't really explain the *structure* of the graph.

Consider ortwin's suggestion of tracking where a spot on the cube goes. Let's pick a spot on the outside of the cube:







There are 24 positions where that spot can go when you rotate the cube: exactly one position per distinct cube orientation:






Here's how each of the positions can be transformed by x or x' moves:






Here's how each of the positions can be transformed by y or y' moves:






Here's how each of the positions can be transformed by z or z' moves:






Putting it all together, here's the full Cayley graph of 1x1x1 orientations generated by quarter turns:






And here's a different way of drawing the same visualization, more in the style of ortwin's image (note that only three sides are visible):


----------



## mikebolt (Mar 20, 2016)

Yeah, I like that 3D visualization of the whole graph in a cube much better.

Also, I noticed something about the number of cube orientations:


There are 3 orientations for each corner of the cube: one way to orient the cube for each face sharing a given corner. This gives 8*3=24 orientations.
There are 2 orientations for each edge of the cube: one way to orient the cube for each face sharing a given edge. This gives 12*2=24 orientations.
There are 4 orientations for each face of the cube: one for each orientation of a given face. This gives 6*4=24 orientations.

I imagine that this works for each of the platonic solids: # corners * 3 = # edges * 2 = # faces * edges per face = # of orientations

Also, I think that dual solids have the same rotational groups and number of orientations: The cube and the octahedron have the same number of orientations, and the icosahedron and the dodecahedron have the same number of orientations.


----------



## unsolved (Mar 20, 2016)

mikebolt said:


> Also, I noticed something about the number of cube orientations:
> 
> 
> There are 3 orientations for each corner of the cube: one way to orient the cube for each face sharing a given corner. This gives 8*3=24 orientations.
> ...



I always thought of it this way: The top color can be in 1 of 4 orientations; one for each side of the square facing a particular way. Any one of 6 colors can be on top. 6x4 = 24.


----------

