• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Hamiltonian Circuit for a 1x1x1 cube

ortwin

Member
Joined
Sep 26, 2010
Messages
30
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 ?
 
  • Like
Reactions: qwr

whauk

Member
Joined
Sep 28, 2008
Messages
464
Location
Germany
WCA
2008KARL02
YouTube
Visit Channel
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

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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.

Code:
  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

Member
Joined
Jun 16, 2015
Messages
2,923
Location
192.168. 0.1
YouTube
Visit Channel
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))).
 
Last edited:

Cale S

Member
Joined
Jan 18, 2014
Messages
2,421
Location
Iowa, USA
WCA
2014SCHO02
YouTube
Visit Channel
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
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

Member
Joined
Jun 16, 2015
Messages
2,923
Location
192.168. 0.1
YouTube
Visit Channel
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

Member
Joined
Jan 18, 2014
Messages
2,421
Location
Iowa, USA
WCA
2014SCHO02
YouTube
Visit Channel
So... Was my intuition correct?
yeah

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

Member
Joined
Sep 26, 2010
Messages
30
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.

Code:
  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.

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

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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

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

Member
Joined
Sep 26, 2010
Messages
30
@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

Member
Joined
Sep 26, 2010
Messages
30
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

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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

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

Member
Joined
Sep 26, 2010
Messages
30
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

Member
Joined
Sep 26, 2010
Messages
30
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.

Zwischenablage01.jpg

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

Member
Joined
Feb 24, 2016
Messages
12
Location
San Luis Obispo

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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:

attachment.php


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

attachment.php


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

attachment.php


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

attachment.php


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

attachment.php


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

attachment.php


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):

attachment.php
 

Attachments

  • cayley3.jpg
    cayley3.jpg
    65.3 KB · Views: 107
  • cayley4.jpg
    cayley4.jpg
    64.9 KB · Views: 107
  • cayley5.jpg
    cayley5.jpg
    62.9 KB · Views: 107
  • cayley6.jpg
    cayley6.jpg
    103.5 KB · Views: 106
  • cayley1.png
    cayley1.png
    124.2 KB · Views: 7
  • cayley2.jpg
    cayley2.jpg
    32.8 KB · Views: 5
  • cayley-1x1x1.jpg
    cayley-1x1x1.jpg
    146.8 KB · Views: 103
  • cayley1.png
    cayley1.png
    126.3 KB · Views: 100
  • cayley2.png
    cayley2.png
    191.9 KB · Views: 99
Last edited:

mikebolt

Member
Joined
Feb 24, 2016
Messages
12
Location
San Luis Obispo
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:

  1. 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.
  2. 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.
  3. 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

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Also, I noticed something about the number of cube orientations:

  1. 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.
  2. 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.
  3. 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 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.
 
Thread starter Similar threads Forum Replies Date
C Puzzle Theory 60
C Puzzle Theory 37
Top