From mreid@ptc.com Thu Feb 22 17:10:57 1996 Return-Path: Received: from poster (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19958; Thu, 22 Feb 96 17:10:57 EST Received: from ducie.ptc.com by poster (5.x/SMI-SVR4-NN) id AA20333; Thu, 22 Feb 1996 17:06:31 -0500 Message-Id: <9602222206.AA20333@poster> Received: by ducie.ptc.com (1.38.193.4/16.2.nn) id AA11649; Thu, 22 Feb 1996 17:38:03 -0500 Date: Thu, 22 Feb 1996 17:38:03 -0500 From: michael reid To: cube-lovers@ai.mit.edu Subject: "simplest" solution of the cube? mark writes > This brings up the idea of a "Rubik's Tour". Such a tour would > touch on a set of interesting patterns within a given subgroup, > or potentially the entire cube group. Of course, "God's Tour" > would not only touch on all the interesting patterns, it would > also sequence all the patterns AND orient them in space such that > the number of q turns would be minimal for the tour! I am currently > working on "God's Tour" for some of the lesser subgroups, touching on > say a dozen patterns for the square's group. If humans and computers > ever resolve "God's Algorithm" there is some solace that there are > problems even more intractible. there's a general graph theory conjecture that cayley graphs are hamiltonian (i.e. have hamiltonian circuits). if we take the cayley graph formed by generators {F, F', L, L' U, U', R, R', B, B', D, D'}, the conjecture asserts that there is a sequence of N quarter turns that visits every position exactly once and returns to START. (here N = 43252003274489856000 is the order of the group.) so the proposed "simplest" solution to the cube is to apply such a hamiltonian sequence. at some point, in the middle of the sequence, the cube will be solved! no need to continue with the rest of the sequence. i don't think the general conjecture is close to being proved, but it is known for some special groups and generators. it would be interesting to know if anyone can verify the conjecture for the cube group with quarter turn generators. (face turn generators would also be interesting.) mike