Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum
 It is currently Fri Jul 25, 2014 4:32 pm

 All times are UTC - 5 hours

 Page 1 of 1 [ 28 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's Algorithm)Posted: Wed Jan 29, 2014 4:14 pm

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
I stumbled across some work done by Bruce Norskog where he found an algorithm to visit every state of the 2x2x2 and the 3x3x3 only once. This means that they are 3,674,159 and ~43 quintillion moves long respectively. I personally find this incredibly impressive. You can read more about them and how they were constructed in the links below.
2x2x2
3x3x3

_________________
Real name: Landon Kryger

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Wed Jan 29, 2014 4:21 pm

Joined: Fri Dec 28, 2012 1:50 pm
Location: Near Las Vegas, NV
WOW!!! There really is an algorithm. I wonder if someone would ever be able to memorize it...

_________________
My Shapeways Shop

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Thu Jan 30, 2014 11:35 am

Joined: Sun Nov 23, 2008 2:18 am
Amazing! So how long would it take to execute theses on a speedcube?

Also, are these results sufficient to prove that a Hamiltonian path exists for all N*N*N(or even cuboids in general)?

Also, considering the record for memorizing Pi(I think its in the 10-50k range), I doubt even the 2*2*2 algorithm could be memorized unless there is a lot of repetition contained there-in. Which raises the question: How 'random' are these sequences?

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Thu Jan 30, 2014 12:57 pm

Joined: Sun Aug 04, 2013 4:50 am
Location: The Netherlands
Jeffery Mewtamer wrote:
Amazing! So how long would it take to execute theses on a speedcube?

Also, are these results sufficient to prove that a Hamiltonian path exists for all N*N*N(or even cuboids in general)?

Also, considering the record for memorizing Pi(I think its in the 10-50k range), I doubt even the 2*2*2 algorithm could be memorized unless there is a lot of repetition contained there-in. Which raises the question: How 'random' are these sequences?

This is from the link to the topic at speedsolvers forum:

Quote:
For compactness, I use variables to define sub-sequences of moves.
The following conventions are used.
Upper case letters are used for the basic quarter-turn moves of the 2x2x2 puzzle.
· U represents turning the top face a quarter-turn clockwise.
· V represents turning the top face a quarter-turn counterclockwise (conventionally denoted U').
· R represents turning the right face a quarter-turn clockwise.
· S represents turning the right face a quarter-turn counterclockwise (conventionally denoted R')
· F represents turning the front face a quarter-turn clockwise (used in Appendix B).
· G represents turning the front face a quarter-turn counterclockwise clockwise (conventionally denoted F').

b=URURUR
a=bURUR
i=bbUR
c=VRiiVR
n=VRa
d=nn
e=ncUR
f=URcaVR
g=ncabVR
h=nbcaVR
j=ccaVR
k=bbVR
l=ncc
m=nUR
o=VRUR
s=nbgaVRdblinVReckdbcanbVRmcURmcidoUR
t=URURnUUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaUR
dnVRdmccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbha
UUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRde
RdcabVRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboUReURnbc
mccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbhaodcUR
dVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRdejhhej
gciVRcgncgcaURdVRddURURckURjURceURncabdVRccdcURfURURlURVRicaURdnVRdmc
w=cVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnU
u=krVRsURtwF
v=uuuuuuuuaVRrVRsURtwUUG
p=FVw't'SVs'RRRUr'SUSVb'SFRbURVRrVSSSsURtwUG
q=GVw't'SVs'SUr'SUa'SFVVw't'SVs'SUr'SUa'FRrVRsUSSStwUaG
x=krVRsURtcVRijaVRhcVRijaVRnbefaodURURglfaVRnVRUpbURUpbURUpbockdcURfabVRVR
kaboURUpbURUpbURUpURdURURdnUFkrVRsURtVRUpaabVRVRijaVRhcVRicnaUpbdVRnbefa
odURURgnoURUpbURUpbURUpURVRcfaVReckVpaVRUpbURcURURcURUpbnbVRVRkabnbURUpb
URdURURdnUFaVRrVRsURtVRUpaabVRVRijaVRhcVRijaVRnbeURoUpaidodURURglfaVRenb
URUqbURVRknVRUpbURnabURVpURfabVRVRkURUpUpbUpUpcUpURUpUpURVRbUpbVRbURUpVR
UpbURoUpbUUUG
z=vvvvvvuuuuuux

Variables denoted with lower case letters represent sequences of multiple moves.
Many of them are defined in terms of other lower case variables.
So recursive expansion is requred to get a plain sequence of individual moves.
If a letter is followed by an apostrophe, then the inverse of the indicated sequence is to be used.
This means that the order of the moves and direction of the moves must be reversed.
A line with a letter and an equal sign starts the definition for a maneuver.
The definition may extend over several lines until there is a line where another definition is started.
The variable z is used to represent the entire Hamiltonian circuit.

EDIT: I have added the fully expanded Hamiltonian Circuit below!

 Attachments: File comment: Hamiltonian Circuit Written Out Completely Hamiltonian Circuit Full.txt [506.17 KiB] Downloaded 28 times

_________________
- Eric
Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Thu Jan 30, 2014 1:32 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jeffery Mewtamer wrote:
Amazing! So how long would it take to execute theses on a speedcube?

A Rubik's cube is 57mm to an edge so this makes it easy to calculate the diameter of the circle that the farthest part of a face travels through as it's turned.

Making the ridiculous assumption that you can turn the faces so fast that the outer portion of the face travels at the speed of light, and that acceleration is infinite between starting and stopping a turn so that there is no delay between turns, then:

(((8! * 12!) / 2) * (3^8 / 3) * (2^12 / 2)) * (((((57 mm) * (sqrt(2))) * Pi) / 4) / c) = 289.4 years

Maybe your speed cube goes a bit slower than this?

Jeffery Mewtamer wrote:
Also, are these results sufficient to prove that a Hamiltonian path exists for all N*N*N(or even cuboids in general)?
I'm pretty sure most twisty puzzles that form a group have a Hamiltonian circuit. The issues wasn't whether one existed, it was whether it was reasonably findable. Larger NxNxN cubes don't form a group because they have identical centers. The "Super" version of NxNxN puzzles do form a group though.

Jeffery Mewtamer wrote:
Also, considering the record for memorizing Pi(I think its in the 10-50k range), I doubt even the 2*2*2 algorithm could be memorized unless there is a lot of repetition contained there-in. Which raises the question: How 'random' are these sequences?

I had the same question yesterday so I made some very huge images out of some of the sequences to try to find patterns. The images were too big and where some sequences were interspersed looked pretty random to me.

A computer program found the sequences though so clearly there is some relatively compact description of the sequences. If you memorized all of the computer programs and ran them in your head you could generate the sequence.

Another measure of the sequence is how well the description of it compresses. I was able to compress the (already relatively compact) sequence description to 3079964 bytes so:

3079964 * log(2^8) / log(10) = 7,417,292 decimal digits.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Thu Jan 30, 2014 2:06 pm

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
This is unbelievable! I was wondering if anyone would ever come up with a Devil's algorithm. I'll have to try to digest this at some point.

-d

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sat Feb 01, 2014 12:44 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
WOW!!! I always thought finding god's algorithm would happen before finding the devil's algorithm for the 3x3x3. Seeing just how long the algorithm is I really don't see how its possible to verify this claim but I haven't made an honest effort to try and understand how this was generated. Even if I did I suspect I'd fry too many brain cells before I understood it.

But I am sort of disapointed... I read this:
Quote:
The last of these subgroups, of course, is actually the whole cube group. The entire Hamiltonian circuit consists of turns of only five face layers. No turns of back layer are used!
This means this is the devil's algorithm for the normal 3x3x3 but NOT the super 3x3x3. I personally find it sad that everyone always wants to ignore the face center orientation. The 3x3x3 only has 3 piece types (corners, edges, and face centers) and it feels like you are ignoring a third of the puzzle to ignore the face centers.

Then again if I had the Hamiltonian circuit for the Super 3x3x3, I suppose I'd then want the Hamiltonian circuit for the Complex 3x3x3.

Carl

_________________
-

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sat Feb 01, 2014 2:08 pm

Joined: Fri Dec 20, 2013 11:47 pm
wwwmwww wrote:
WOW!!! I always thought finding god's algorithm would happen before finding the devil's algorithm for the 3x3x3. Seeing just how long the algorithm is I really don't see how its possible to verify this claim but I haven't made an honest effort to try and understand how this was generated. Even if I did I suspect I'd fry too many brain cells before I understood it.

The way I understand it, God's algorithm is supposed to be the shortest path to a solved state. Would this not mean that every scramble of the 3x3 would have a different God's algorithm, a different shortest path to a solved state?

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sat Feb 01, 2014 2:39 pm

Joined: Sat Sep 15, 2012 7:42 am
garathnor wrote:
The way I understand it, God's algorithm is supposed to be the shortest path to a solved state. Would this not mean that every scramble of the 3x3 would have a different God's algorithm, a different shortest path to a solved state?

No. You are correct that every scrambled state would have a unique solution of 20 moves or less. God's algorithm, though, would be a general process to find the shortest solution for an arbitrary scramble. God's algorithm is not the solution itself. It's the algorithm for finding the solution.

_________________
Call me Seth

Named 3x3x3 Bandaging Patterns

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sat Feb 01, 2014 3:37 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
themathkid wrote:
garathnor wrote:
The way I understand it, God's algorithm is supposed to be the shortest path to a solved state. Would this not mean that every scramble of the 3x3 would have a different God's algorithm, a different shortest path to a solved state?

No. You are correct that every scrambled state would have a unique solution of 20 moves or less. God's algorithm, though, would be a general process to find the shortest solution for an arbitrary scramble. God's algorithm is not the solution itself. It's the algorithm for finding the solution.

This is a bit general. Given your definition, brute force would classify as a particular instance of "God's algorithm". I'd add some additional qualifies like "must be non-trivial" and "must be reasonably achievable now or at some point in the future".

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sat Feb 01, 2014 3:56 pm

Joined: Sat Sep 15, 2012 7:42 am
Brandon Enright wrote:
This is a bit general. Given your definition, brute force would classify as a particular instance of "God's algorithm". I'd add some additional qualifies like "must be non-trivial" and "must be reasonably achievable now or at some point in the future".

Can you give an example of a puzzle with a God's algorithm that doesn't involve brute force? I have never seen a discussion on God's algorithm or God's number that didn't hinge on extensive computer searching, excepting some simple puzzles like Towers of Hanoi. Certainly not a twisty puzzle. Is this perhaps because the number of states of a twisty puzzle is typically extremely large?

_________________
Call me Seth

Named 3x3x3 Bandaging Patterns

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sat Feb 01, 2014 4:04 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
themathkid wrote:
Can you give an example of a puzzle with a God's algorithm that doesn't involve brute force? I have never seen a discussion on God's algorithm or God's number that didn't hinge on extensive computer searching, excepting some simple puzzles like Towers of Hanoi. Certainly not a twisty puzzle. Is this perhaps because the number of states of a twisty puzzle is typically extremely large?

Practical optimal solutions solutions to the Rubik's cube have been known for a very long time. They do use some brute force to prove that there isn't any shorter solution however they've very smart about how they brute force and they use lots of additional criteria about how to prune the search so that they know when enough brute-force has been done.

I'm pretty sure they also use meet-in-the-middle tricks and other stuff. Check out the readme / help for CubeExplorer. It goes into a lot of details about some of the tricks it uses.

Edit: http://kociemba.org/math/optimal.htm

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sat Feb 01, 2014 4:28 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Just thought of a question...

Since this Hamiltonian circuit for the 3x3x3 doesn't consider face center orientation, if you apply the whole circuit to a solved Super 3x3x3 can you tell if the face centers are solved at the end? The back face center obviously is as its never turned but what about the others?

Regarding god's algorithm for the 3x3x3, I know there are people actively working toward a proof and I would certainly expect to see one in my lifetime if not within the next decade. Till I saw this post, I had no idea anyone was even looking for the devil's algorithm.

Carl

_________________
-

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sun Feb 02, 2014 12:11 pm

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
wwwmwww wrote:

Regarding god's algorithm for the 3x3x3, I know there are people actively working toward a proof and I would certainly expect to see one in my lifetime if not within the next decade. Till I saw this post, I had no idea anyone was even looking for the devil's algorithm.

Carl

I'm I misunderstanding you? I thought it was proven to be 20. In fact there was a post here not too long ago (For the life of me, I can't find it though) But http://www.cube20.org/ has info on it. Or were you talking about God's algorithm for a super cube?

-d

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sun Feb 02, 2014 12:57 pm

Joined: Fri Dec 20, 2013 11:47 pm
darryl wrote:
wwwmwww wrote:

Regarding god's algorithm for the 3x3x3, I know there are people actively working toward a proof and I would certainly expect to see one in my lifetime if not within the next decade. Till I saw this post, I had no idea anyone was even looking for the devil's algorithm.

Carl

I'm I misunderstanding you? I thought it was proven to be 20. In fact there was a post here not too long ago (For the life of me, I can't find it though) But http://www.cube20.org/ has info on it. Or were you talking about God's algorithm for a super cube?

-d

There is a small difference in what you are thinking about. I think you are thinking about God's number, which is the absolute most the 3x3 can be scrambled where God's algorithm is the shortest path to solution no matter what.

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sun Feb 02, 2014 1:00 pm

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
Ah yes, that makes sense. I figured I was misunderstanding.

-d

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sun Feb 02, 2014 5:00 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
darryl wrote:
I thought it was proven to be 20. In fact there was a post here not too long ago (For the life of me, I can't find it though) But http://www.cube20.org/ has info on it. Or were you talking about God's algorithm for a super cube?
As has been pointed out you are mixing up god's number with god's algorithm. And when talking about god's number, one needs to specify what metric one is using. Gods number for the normal Rubik's cube using the quarter turn metric I believe is 20. Gods number for the Super 3x3x3 using the quarter turn metric I believe is also known and if I recall correctly it is 24.

Back to the Hamiltonian Circuits for 2x2x2 and 3x3x3. The one for the 2x2x2 is stated to be 3,674,159 moves long. Since it takes an even number of moves to restore the puzzle to the solved state if one starts at the solved state would I be correct that to complete the circuit one must make 3,674,160 moves? This would visit the solved state twice so I'm assuming one move was dropped to avoid this. Still, based on what I know about electrical circuits, I find it hard to call this a circuit unless you end up back where you started. The midpoint of this circuit would be after 1,837,080 moves. Looking here I see gods number for the 2x2x2, using the quarter turn metric, is 14. This also shows why its important to specify the metric as gods number for the 2x2x2 using the face turn metric is 11. Always I see that there are 276 states of a 2x2x2 that are 14 quarter turns away from solved. I'm now curious if the state that is 1,837,080 moves into this Hamiltonian Circuits for the 2x2x2 is one of these 276 states. Its the point that is furthest from solved in the circuit, but if I had to guess I don't think that really says anything about how far away that state is from solved in the general sense. It could be a two quarter turns away from solved as far as I know. I know its NOT a single quarter turned away from solved... bonus points if you can tell me how I know that.

Doing some math to think about just how hard it is to visualize these Hamiltonian Circuits let's stick with the 2x2x2 for a bit longer. The fastest 2x2x2 solve I see is this one:
In it he makes 4 quarter turns in 0.69 seconds.

So 3,674,160moves * (0.69seconds/4moves) * (1minute/60seconds) * (1hour/60minutes) * (1day/24hours) = 7.3355625 days which is 7 days 8 hours 3 minutes and 12.6 seconds

So much for me even watching a video of this circuit on a 2x2x2 and Brandon has already proven the 3x3x3 circuit is physically beyond anyone ones reach. Still there are lots of interesting questions I can think to ask about them.

(1) What do their mid-points look like? Are they interesting or spark any new insight?
(2) There are 276 states of a 2x2x2 that are 14 quarter turns away from solved. Are these states equally distributed along this Hamiltonian Circuit? Are they randomly distributed?
(3) A single quarter turn either takes you 1 move closer or 1 move further away from the solution. So if we numbered all 3,674,160 states in this circuit from 1 to 3,674,160 (let's call this number x) we could define a function f(x) which would look like this:

f(0) = 0 --------- The 2x2x2 is solved before any moves are applied.
f(1) = 1 --------- We are now one move away from the solution.
f(2) = 2 --------- We are now 2 moves away from the solution. We know each state is only visited once so we know we didn't step back and visit the solution.
f(3) = 3 or 1 --- My guess would be 3 but I'd need to go look at the move list to be sure.
....
f(x) = assumes the values 1 to 14
....
f(3,674,158) = 2
f(3,674,159) = 1
f(3,674,160) = 0

So my question would be is f(x) symmetric? What does it look like? How difficult would it be to plot that function?

I'd love to ask all these questions about the 3x3x3 as well but finding answers for the 2x2x2 I suspect is more then hard enough already.

Carl

_________________
-

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sun Feb 02, 2014 5:19 pm

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
wwwmwww wrote:
Gods number for the normal Rubik's cube using the quarter turn metric I believe is 20.
No. It's 20 for the face turn metric where 2 quarter turns on the same face are counted as 1 turn. The God number for quarter turn metric is expected to be 26 but hasn't been proven.

_________________
Real name: Landon Kryger

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sun Feb 02, 2014 5:33 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
GuiltyBystander wrote:
wwwmwww wrote:
Gods number for the normal Rubik's cube using the quarter turn metric I believe is 20.
No. It's 20 for the face turn metric where 2 quarter turns on the same face are counted as 1 turn. The God number for quarter turn metric is expected to be 26 but hasn't been proven.
That's what I get for not looking it up. Thanks for the correction... and again this highlights the importance of stating the metric. The 24 figure that was I thinking of... is that gods number for the Super 3x3x3 in the face turn metric?

And come to think of it... just how many standard metrics for the 3x3x3 do we have?

Quarter Turn = Only 90 degree turns of the faces are allowed. They can be clockwise or counter-clockwise I believe.
Face Turn = Allows 90 degree CW or CCW face turns and 180 degree face turns.

If I had to guess we also have something like these but I'm not sure these are the standard names:

Quarter Slice Turn = Same as Quarter Turn but now quarter turns of the slice layer are allowed as well.
Slice Turn = Same as Face Turn but now 90 degree and 180 degree slice turns are allowed as well.
Clockwise = Only 90 degree clockwise face turns are allowed.

Are there any others that may be of interest? The two most talked about are the top two. Are the last 3 ever used? And if so do they have official names?

Carl

_________________
-

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Sun Feb 02, 2014 6:52 pm

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
I've heard of slice turn metric and that's expected to be 18 for the 3x3 but again, unproven. Nothing comes to mind about what the stats for the super 3x3x3. I don't think the others have been used much if at all. At least it isn't a larger cube where there's a ton more metrics.

I got the original link from this site (which I in turn originally got from Brandon). It's not very active, but it has a lot of interesting analysis from lots of different puzzles and subsets. Some of the cube20 guys have posted stuff there. They may have the answers you're looking for.
http://cubezzz.dyndns.org/drupal/

_________________
Real name: Landon Kryger

Top

 Post subject: rePosted: Mon Feb 03, 2014 10:27 am

Joined: Sun Nov 23, 2008 2:18 am
Are these Circuits open or closed? In other words, is the end position adjacent to the start position?

I too would be interested in statisstics on how positions N steps from solved are distributed throughout the circuit.

Given how surprising it is that one could find a Hamiltonian circuit for such large graphs, am I correct in thinking that counting the number of such circuits would be impossible in any reasonable amount of time? Could such be done for the 1*3*3?

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Mon Feb 03, 2014 12:06 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Jeffery Mewtamer wrote:
Are these Circuits open or closed? In other words, is the end position adjacent to the start position?
Great question... I've assumed "yes" simply based on the fact that its called a circuit. But you know what they say about making assumptions.
Jeffery Mewtamer wrote:
Given how surprising it is that one could find a Hamiltonian circuit for such large graphs, am I correct in thinking that counting the number of such circuits would be impossible in any reasonable amount of time? Could such be done for the 1*3*3?
I can't answer either question but I feel safe in saying that this circuit isn't unique. I suspect there are more circuits then there are states and I wouldn't even venture a guess as to how to go about counting them. I honestly don't understand how this one was found. If this circuit is closed (as I suspect that it is) you also have the issue of checking that a new circuit isn't this same circuit just starting at a different point or traveling around the circuit in a different direction. That sounds trivial but considering the size of these circuits I suspect that it is anything but trivial. And come to think of it, it would be nice to check that one hasn't simply found the mirror of this circuit. Not sure if that would be considered a new circuit or not.

Carl

_________________
-

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Mon Feb 03, 2014 7:41 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
Jeffery Mewtamer wrote:
Are these Circuits open or closed? In other words, is the end position adjacent to the start position?
Great question... I've assumed "yes" simply based on the fact that its called a circuit. But you know what they say about making assumptions.

Bruce Norskog wrote:
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.

It's clear that it forms a closed loop. I'm not sure which move is needed to put it back in the start position though. You'd have to apply that move before you could run through the circuit again.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Thu Feb 13, 2014 9:06 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Hello Guys,

I've been able to make contact with Bruce and we've talked some. What he says I believe would be of general interest here so I asked if he minded if I reposted out conversation here. I'll also add that he has now applied for membership at TwistyPuzzles so he may be here soon himself.

Quote:
Hi Carl,

Yes, I noticed the thread on the Twisty Puzzles forum a little while after my previous reply to you. I am not a member of that forum. You can certainly share what I say on the forum. I suppose I'll try registering. It seems to me some time ago, there were times where either new members weren't being allowed, or needed a recommendation from another member or something like that. I never bothered to try to register. Perhaps now someone just has to convince the administrators that one is not a spammer to get approved, so maybe I'll give it a try.

I felt that the Hamiltonian circuit problem was an easier problem than the God's number problem. The God's number problem (for face turn metric) was solved first, but it took a huge amount of computer processing power to accomplish it. The Hamiltonian circuit problem, on the other hand, did not require very much computer processing power, and I only needed to use my own computers. So I still think this was an easier problem. The way the Cayley graph can be said to look the same from any node (and similarly for each subgroup) is a key that allows this big problem to be divided up into smaller problems.

I kept quiet about working on the problem since I didn't want to get extra attention to the problem and might challenge others to try to beat me to a solution.

I have only "published" it online. I have not had it published in a mathematical journal. Nor has anyone yet independently validated it to my knowledge. I may have to look to getting it published in a peer-reviewed journal in order to get it independently validated.

I was not familiar with the complex 3x3x3. Currently, I don't feel that this puzzle is of sufficient general interest to make me feel it worth my time to work on a Hamiltonian circuit for it. I've taken a look at Andreas's GAP file, and from that it looks like it's still 6 generators and 3 pairs of commuting generators. So it looks to me that you have the same number of levels, but very much larger numbers of cosets at each level. So one would need to subdivide these levels somehow so as to deal with reasonable size numbers.

I might add that the other day I considered looking at what it would take to find a Hamiltonian circuit for the Megaminx. The Megaminx requires turning at least 9 faces to generate all possible positions. While on the 3x3x3, only opposite face turns commute, the Megaminx has 6 face turns that commute with any given face turn. Hence, the Megaminx can be divided into a nested set of subgroups, where each larger subgroup adds a generator that commutes with at least one generator already used. I believe this means it should be relatively "easy" to generate a Hamiltonian circuit for each successive level of the subgroup hierarchy. Still, the large number of cosets at several of the levels may make this still be a significant amount of work.

- Bruce

Carl Hoff wrote:
--------------------
Hello Bruce,

Thanks for the reply and the information. This is being talked about here:
http://twistypuzzles.com/forum/viewtopic.php?f=8&t=26792

My user ID is wwwmwww in those forums. Would you mind if I shared this info with the group there? Any chance you are a member of TwistyPuzzles? We'd certainly welcome you and would love the opportunity to discuss this with you there?

May I ask what prompted you to do this in the first place? It is very interesting but to be honest I had no idea anyone was even working on this. The circuit is so long on a 3x3x3 that no one could complete it in a lifetime. Have you got this published?

The Normal 3x3x3 has 2 piece types (corners and edges) and this is the one you solved. The Super 3x3x3 has 3 piece types (add face centers to the mix) and you've discussed that here. The Multi 3x3x3 has 4 piece types with the 4th being the core but it would be the same problem as the Super3x3x3 from this perspective. Are you aware of the Complex 3x3x3? It has 10 piece types, the 4 of the Multi 3x3x3 plus 6 more. It was first discussed in this thread:
http://twistypuzzles.com/forum/viewtopic.php?f=1&t=15667
and Andreas first calculated the number of permutations for the Complex 3x3x3 here:
http://twistypuzzles.com/forum/viewtopic.php?f=1&t=18470

If you ever did find the hamiltonian circuit for the Super 3x3x3 I'd be curious if you thought the Complex 3x3x3 was doable? The Super 3x3x3 is a subset of the Complex 3x3x3 but the Complex 3x3x3 is so much bigger that I'm guessing not but then again I wouldn't have thought the Normal 3x3x3 was doable either until you did it.

Again thanks for your time and congratulations on this accomplishment,
Carl

Bruce Norskog wrote:
--------------------
Hi Carl,

I think the super 3x3x3 Hamiltonian circuit problem can be solved through a similar approach. Most of the coset spaces are four times bigger in size for the supercube. It appears to me the trickiest part would be in connecting up the 8192 cosets within the <U,R,D,L,F> subgroup. This was the trickiest part of the solution for me for the regular 3x3x3 cube, and there it was only 2048 cosets. Of course, the supercube needs one more phase, since the B face must also be turned. The <U,R,D,L,F,B> phase will only have 4 cosets to connect, and can be connected up one at a time, so that part would be trivial.

So basically, I think what you ask is doable, but it appears to be enough work that I've not considered it to be high enough priority to invest my time at it.

- Bruce Norskog

_________________
-

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Thu Feb 13, 2014 9:25 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
So who here knew this?
Quote:
The Megaminx requires turning at least 9 faces to generate all possible positions.
I don't recall knowing this before. Who here can keep 3 face centers fixed (never rotated) and post the move sequences needed to make a 72 degree clockwise face turn of each of the 3 fixed faces (one at a time). That would be enough to prove this.

Its obvious that non of the 3 faces can be adjacent or the edge between them would never move so there really is only 1 unique arrangement of faces to try. And for the face turns above I don't believe 3 sequences are needed to prove this. Two should be fine... no make that just one sequence. If you can make a 72 degree clockwise face turn of just one of the 3 fixed faces then the puzzle has the symmetry needed that you can just make a global reorientation of the entire puzzle (such that the 3 faces that don't rotate are in the same 3 positions) and apply the same sequence again to get other faces rotated.

Very interesting...

I wonder what effect this property has on gods number for the 3x3x3.

God's number for the 3x3x3 using the face turn metric is 20. But I believe this is with being able to turn all 6 faces. If one can only turn 5 faces all the same states are reachable (remember we are talking about a normal 3x3x3 not a super 3x3x3) but what would god's number be for this new puzzle where only 5 faces could be turned?

Carl

_________________
-

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Thu Feb 13, 2014 11:17 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
So who here knew this?
Quote:
The Megaminx requires turning at least 9 faces to generate all possible positions.
I don't recall knowing this before. Who here can keep 3 face centers fixed (never rotated) and post the move sequences needed to make a 72 degree clockwise face turn of each of the 3 fixed faces (one at a time). That would be enough to prove this.

This is really easy actually. I constructed one by hand that only needs 7 faces to turn one of the forbidden ones, of course without using any of the forbidden ones. In GB syntax:

Code:
[F', B'2, C'2, D'2, E'2, D2, C2, B2, F'2, I, B, I', F, B'2, H2, B2, C', D'2, F, E'2, F', D2, C, B'2, H'2, B2, F', I, B', I', F, B'2, H2, B2, C', D'2, F, E2, F', D2, C, B'2, H'2, B2, F, B'2, C'2, D'2, E2, D2, C2, B2, F, E', F'2, B', C, D', E'2, B', F', B, C', F', B'2, C'2, D'2, E'2, D2, C2, B2, F'2, I, B, I', F, B'2, H2, B2, C', D'2, F, E'2, F', D2, C, B'2, H'2, B2, F', I, B', I', F, B'2, H2, B2, C', D'2, F, E2, F', D2, C, B'2, H'2, B2, F, B'2, C'2, D'2, E2, D2, C2, B2, F, C, B', F, B, E2, D, C', B, F2, E]

Although to turn any one of them only takes me 7 face, to turn another takes a different 7 and when you stack up all three you end up using all 9 possible faces for the generator.

Just to prove I can turn all three of them arbitrary without using any of them, this sequence turns each 1/5th CCW and only uses the 9 other faces:

Code:
[F', B'2, C'2, D'2, E'2, D2, C2, B2, F'2, I, B, I', F, B'2, H2, B2, C', D'2, F, E'2, F', D2, C, B'2, H'2, B2, F', I, B', I', F, B'2, H2, B2, C', D'2, F, E2, F', D2, C, B'2, H'2, B2, F, B'2, C'2, D'2, E2, D2, C2, B2, F, E', F'2, B', C, D', E'2, B', F', B, C', F', B'2, C'2, D'2, E'2, D2, C2, B2, F'2, I, B, I', F, B'2, H2, B2, C', D'2, F, E'2, F', D2, C, B'2, H'2, B2, F', I, B', I', F, B'2, H2, B2, C', D'2, F, E2, F', D2, C, B'2, H'2, B2, F, B'2, C'2, D'2, E2, D2, C2, B2, F, C, B', F, B, E2, D, C', B, F2, E, L', I'2, F'2, E'2, K'2, E2, F2, I2, L'2, H, I, H', L, I'2, B2, I2, F', E'2, L, K'2, L', E2, F, I'2, B'2, I2, L', H, I', H', L, I'2, B2, I2, F', E'2, L, K2, L', E2, F, I'2, B'2, I2, L, I'2, F'2, E'2, K2, E2, F2, I2, L, K', L'2, I', F, E', K'2, I', L', I, F', L', I'2, F'2, E'2, K'2, E2, F2, I2, L'2, H, I, H', L, I'2, B2, I2, F', E'2, L, K'2, L', E2, F, I'2, B'2, I2, L', H, I', H', L, I'2, B2, I2, F', E'2, L, K2, L', E2, F, I'2, B'2, I2, L, I'2, F'2, E'2, K2, E2, F2, I2, L, F, I', L, I, K2, E, F', I, L2, K, C', H'2, L'2, K'2, D'2, K2, L2, H2, C'2, B, H, B', C, H'2, I2, H2, L', K'2, C, D'2, C', K2, L, H'2, I'2, H2, C', B, H', B', C, H'2, I2, H2, L', K'2, C, D2, C', K2, L, H'2, I'2, H2, C, H'2, L'2, K'2, D2, K2, L2, H2, C, D', C'2, H', L, K', D'2, H', C', H, L', C', H'2, L'2, K'2, D'2, K2, L2, H2, C'2, B, H, B', C, H'2, I2, H2, L', K'2, C, D'2, C', K2, L, H'2, I'2, H2, C', B, H', B', C, H'2, I2, H2, L', K'2, C, D2, C', K2, L, H'2, I'2, H2, C, H'2, L'2, K'2, D2, K2, L2, H2, C, L, H', C, H, D2, K, L', H, C2, D]

The concepts behind constructing this are the focus of an upcoming post and video series of mine about twisting pieces, pure. You can confirm on Gelatinbrain's 1.1.1b (Super Megaminx) that none of the centers twist after applying this sequence. Only the faces <B,C,D,E,F,H,I,K,L> are used. A, J, and G are left out.

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Fri Feb 14, 2014 1:51 am

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
wwwmwww wrote:
God's number for the 3x3x3 using the face turn metric is 20. But I believe this is with being able to turn all 6 faces. If one can only turn 5 faces all the same states are reachable (remember we are talking about a normal 3x3x3 not a super 3x3x3) but what would god's number be for this new puzzle where only 5 faces could be turned?
Using the same counting method that sets the lower bound for the FTM of the 3x3x3 to 18, you can find a lower bound for the 5-FTM to be 19. So that argument isn't terribly useful.

For 5-QTM, Bruce again comes to the rescue saying that there are some states that require 28q turns (and increase from the expected god number of 26 for QTM). A good read and more details here: http://cubezzz.dyndns.org/drupal/?q=node/view/524
In my brief search I didn't find anything about FTM.

Brandon Enright wrote:
Code:
algorithmic voodoo
I said it in IRC privately, but figured I should say it publicly. That's pretty awesome.

_________________
Real name: Landon Kryger

Top

 Post subject: Re: Hamiltonian Circuit for 2x2x2 and 3x3x3 (Devil's AlgoritPosted: Fri Feb 14, 2014 7:21 am

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
I couldn't resist doing this challenge myself...

49 moves for a single face turn on face A without turning A, J, or G (also doesn't use K):

(E',F'2,I2,L',H',I2,F',I',F,B,F,B',F',I,F',E2,C2,H2,F,I2,D,C2,F'2,B,F,I',F,B,F,B',F',I,F'2,B',C'2,D',F2,I'2,H'2,C'2,F',E'2,F,I'2,H,L,I'2,F2,E)

EDIT: 36 moves: (F,E2,K,D,E',C',D'2,E,D,E',D2,C,D',E,D',K',E'2,F',C,B2,I,F,B',E',F'2,B,F,B',F2,E,F',B,F',I',B'2,C')

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 28 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 5 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic