Home »

How many 26q* maneuvers are there?

Submitted by Bruce Norskog on Sat, 10/20/2012 - 22:17.

How many 26q* maneuvers are there?

Well, obviously we can't say for sure, as it hasn't yet been proved that the 3 known 26q* positions (which are symmetrically equivalent to each other) are the only 26q* positions. In another thread, Herbert Kociemba mentioned that there are "many" such maneuvers, but he did not attempt to generate them all (for the known 26q* positions).

I note that 26q* refers to a maneuver that is 26 quarter turns long and that is known to be optimal in the quarter turn metric. It may also refer to a position that requires a minimum of 26 quarter turns to solve. 26q (without the asterisk) refers to any maneuver 26 quarter turns long, but isn't necessarily optimal for the position it solves.

We also realize that maneuvers can be rather trivially different from one another. We could consider that the total number of 26q maneuvers is 1226, allowing any of the 12 quarter turns at any position in the sequence without any further restrictions. Typically, when there are two or more consecutive moves that commute, we will regard that the order of those particular moves don't matter. For example, U F B R as being essentially the same as U B F R. Also, we often consider that a half turn can be done through either two clockwise quarter turns or two counterclockwise quarter turns. Choosing one or the other is a rather trivial distinction.

So we can talk about canonical sequences where commuting moves are done in a certain order, and half turns are always done using clockwise moves. We can say U layer turns can't follow D layer turns, R layer turns can't follow L layer turns, and F layer turns can't follow B layer turns.

So how many such canonical 26q* maneuvers are there? For the known 26q* positions, I believe the number is 803424. Naturally, the number for each of the known 26q* positions is 1/3 this number, or 267808. We can further break down these maneuvers into maneuvers that are symmetrically similar. So the total number of symmetrically distinct 26q* maneuvers for these positions is 16738.

I used Tom Rokicki's rubsolv program (version 163) to solve many positions 3q away from one of the known 26q* positions. I wrote some perl code to allow me to take the positions produced by Tom's program, expand them to all symmetrical variants, recanonicalize those maneuvers, and eliminate duplicates.

(With the -s option of Tom's program, supposedly a representative of each symmetry class should be generated, but I think it has a flaw as I was not getting representatives of all maneuvers using that mode of the program. This can be more quickly seen with the simpler "four-spot" position that has the same symmetry. So I had to run the program without using the -s option.)

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Equivalence with Dan Hoey's Syllables

Submitted by Jerry Bryan on Sat, 11/10/2012 - 22:24.
I'm a little late to the party on this thread, but I thought I would mention that I believe your criteria for canonical maneuvers could be restated as "maneuvers unique up to Dan Hoey's syllables". In the quarter turn metric, Dan's syllables may be of length 1, 2, 3, or 4. They reflect quarter turns that commute in obvious ways such as FB'=B'F, and they reflect halfway points of identities such as FF=F'F'. And of course they reflect combinations such as B'FF=FB'F=FFB'=B'F'F'=F'B'F'=F'F'B'.

For example, suppose A=B'FF in any of its forms. Then we can write B'FFR as AR. We can maintain the same sense of quarter turn length by declaring A to be 1 move of weight 3 and R to be 1 move of weight 1. Then the length of AR is 2 and the weight is 4. The weight is what we really care about in order to correspond to normal quarter turn lengths.

To make the notation work, we would never write a composite syllable in decomposed form, and we would never write something such as AB'. Rather, we would write AB' as something like E, where E=FFBB. But these are only notational details. The idea remains that your canonical forms are equivalent to writing maneuvers in terms of Dan's syllables.

We might have a problem of running out of enough one letter names for all of Dan's syllables. But remembering that the quarter turns themselves are syllables, a canonical 26* maneuver would be written as syllables with a total weight 26.

Jerry
» login or register to post comments

Can you find a hard QTM position?

Submitted by rokicki on Wed, 10/31/2012 - 18:02.
I will give $50 to the first distance-24 or greater QTM position that anyone finds, that is not in the set of 13,099 positions I'm already aware of.

To let you test what positions I'm aware of, I've put a Perl script at 

   http://tomas.rokicki.com/qtmdb.pl.txt
that you can run with a candidate sequence to see if I know of it already. (The .txt extension is so your browser doesn't try to execute it as a Perl script directly.) For instance, 
rokicki@gym:~$ perl qtmdb.pl  U+U+F+U+U+R-L+F+F+U+F-B-R+L+U+U+R+U+D-R+L-D+R-L-D+D+
Seq [U+U+F+U+U+R-L+F+F+U+F-B-R+L+U+U+R+U+D-R+L-D+R-L-D+D+] is a known 24+ QTM move position.
rokicki@gym:~$ perl qtmdb.pl U+F+R+D+B+L+U+F+R+D+B+L+U+F+R+D+B+L+U+F+R+D+B+L+
Seq [U+F+R+D+B+L+U+F+R+D+B+L+U+F+R+D+B+L+U+F+R+D+B+L+] is not a known 24+ QTM move position.
This script will not test that the position is really at distance 24 or greater; that is up to you to test.

To claim the prize, send the position to me by email at rokicki@gmail.com; I will test them in the order they are received.

If you attempt to claim the prize with a position that is not at distance 24 or greater, or with a position already known by that Perl script, I reserve the right to ignore any further emails from you (so I will not, for instance, test 1000 positions from one person just because they hope one of them might be distance-24 or greater).

I am almost 100% confident that I know only a very small percentage of distance-24 or greater positions, so there are plenty to find.

I encourage discussion of approaches to finding any such positions.

» login or register to post comments

Question

Submitted by secondmouse on Thu, 03/28/2013 - 19:56.
Yes I know its been a few months since this challenge was posted.
As a matter of interest did you have any takers of the prize?

I had a decent go at providing a new 24q* position or greater using the solver of H. Kociemba but I failed miserably. I'm not so sure there are as many to find as you speculate.
» login or register to post comments

Contest

Submitted by rokicki on Wed, 05/29/2013 - 17:21.
No takers at all; not even any interest (yet); I'm glad
at least one person tried!

Would you be willing to share what your approach was?
Did you just try random positions, or was there a method
to your search?

I'm fairly certain there are still millions of 24q* that
are "unknown" to me, but the space is quite large so
finding them with a random search would probably not be
productive.

The contest is still open of course.
» login or register to post comments

How did you guess?

Submitted by secondmouse on Thu, 06/06/2013 - 19:25.
Yes I took as a starting point random 22q* positions and then appended two extra moves as follows:

1) Two to the left
2) One to the left then one to the right
3) Two to the right

I tried several thousand candidate positions but as you surmised this
approach did not pan out (although some were known to your perl script and hence invalid)

I have now got hold of the optiqtm.c source code of H. Kociemba and ported this to Linux using Cygwin. I think there is a chance of tweaking this to search for candidate positions more efficiently.

Paul Timmons
» login or register to post comments

Using Antisymmetry

Submitted by Bruce Norskog on Wed, 10/24/2012 - 20:39.

I note that in addition to symmetry reduction, there are other ways to reduce the number of essentially distinct maneuvers. The first obvious way is using antisymmetry. I note that the known 26q* positions are self-inverse positions, so taking the inverse of a maneuver for one of them will yield a maneuver for the same position. (In any case, the inverse of any optimal maneuver for a position will be an optimal maneuver for the inverse position.) Another possible way of reducing the count is using cyclic shifting. Of course, a cyclic shift may yield a different position in the same conjugacy class, and might not be an optimal maneuver. So probably only a small percentage of cyclic shift cases will result in successfully matching up two 26q* maneuvers.

I have looked at using antisymmetry. I didn't find any 26q* maneuver for which the inverse maneuver (allowing for reordering of commuting moves) was the same. However I found that 64 symmetry classes where the inverse maneuvers were members of the same symmetry class (allowing for reordering of commuting moves). So using antisymmetry in addition to symmetry reduces the count of essentially distinct maneuvers to 8401.

An example of a canonical 26q* maneuver that is symmetric to its inverse (allowing for reordering of commuting moves) is:

U F B U' F' R' F R L' D' L' U R L' D' R U R L' F' L F D F' B' D' (26q*)
» login or register to post comments

Not directly answering your question...

Submitted by secondmouse on Mon, 10/22/2012 - 17:51.
As I'm sure you're aware there is a slideshow presentation by Rokicki
see page 69 in which it is conjectured that the QTM diameter is 26 with
only one position (up to rotational symmetry conjugates so three
really in absolute terms - 4 spot plus superflip three times).

http://cube.stanford.edu/class/files/rokicki_cubecomp.pdf

Equally interesting is the conjecture that the 25q* positions amount to 3 only.
This would allow for a maximum of 72 positions up to rotational symmetry.
What are the known positions of length 25q*? How many in absolute terms
are known? I would like to see the breakdown.

From my experience with Cayley graphs I would be sceptical of this claim
for the 25q* position count. Would expect it to be much larger.
» login or register to post comments

25q* count

Submitted by rokicki on Tue, 10/23/2012 - 16:01.
I have some results to share on this, but I have not yet written them up. So far I stand by this conjecture. The known 25q* are all neighbors of the single known 26q* (mod symmetry). I believe we know all 26q* and all 25q*, but not nearly all 24q*. Right now I know 814 24q* positions mod M+inv, which works out to 13,060 positions. By comparison, I know more than 230,000 20q* positions mod M+inv, which works out to over 18M positions. I'll write this all up probably sometime in November.
» login or register to post comments

25q* count

Submitted by secondmouse on Thu, 10/25/2012 - 03:55.
Actually that seems quite plausible thinking about it. The 25q* positions would be likely to be
in the neighbourhood of 26q* (to put it crudely). I am still curious to how many distinct positions
are postulated for 25q*. You say there are three up to symmetry but how many in total (allegedly)?
» login or register to post comments

Howdy! Very cool question.

Submitted by rokicki on Mon, 10/22/2012 - 15:25.
Howdy!

Very cool question.

If you have a particular run of rubsolv that shows -s not working properly, please let me know.

I do not claim -s and -a work together. Also, note that the way
rubsolv "reduces by symmetry" is nonobvious; it's guaranteed to
yield an optimal solution. I can expand on this if desired.

But I have a hugely faster optimal solver at this point, in QTM,
HTM, and STM; I should probably ask it this question. (At the
moment I'm using the machines I have to generate more 20h* and
24q* positions.)
» login or register to post comments

Raw 26q* count

Submitted by Bruce Norskog on Tue, 10/23/2012 - 10:30.

I have now come up with the total number of raw sequences of 26 quarter turns that are optimal if no other 26q* positions exist. (This assumes I have made no errors along the way or missed any canonical sequences.) This is assuming we consider all 1226 = 11447545997288281555215581184 26q sequences as distinct sequences.

That number is 361,535,616.

As for the rubsolv issue, my assumption was that -a and -s could be used together. In another thread, Tom wrote:

The -a option says give me all solutions; the -s option means analyze the position for symmetry before solving and then only print out representative solutions.
The use of "solutions" in the plural at the end of that quote seems to imply both flags can be used together, since without -a you only get one solution in the output (well, per search, that is).

Anyway, my test case was: ./rubsolv -a -s UD3F2B2UD3L2R2 for which I get 6 solutions:

U+F+F+B+B+U+D-R+R+L+L+D-
U+F+B-U+D-F-B+U+D-F+B-D-
U+D-F+F+B+B+U+D-R+R+L+L+
U+D-F+B-U+D-F-B+U+D-F+B-
F+F+B+B+U+D-R+R+L+L+U+D-
F+F+B+B+U-D+R+R+L+L+U-D+

Without the -s switch, I get 120 solutions. As an example, some of the 120 solutions start with a 3q syllable, while none of the maneuvers output when both switches are used start with a 3q syllable. So it's seems clear you don't necessarily get all symmetry representatives when using both switches. But I guess Tom is now claiming that there is no guarantee that you will get all (symmetry) representative solutions.

» login or register to post comments

All Distinct Paths

Submitted by B MacKenzie on Sat, 10/27/2012 - 09:00.
I modified the path iterator in a solver of mine to not filter out any identities, even the length two identities such as R L = L R and R R = R' R'. With this solver I find 57,344 distinct optimal paths to the above four spot position. These reduce by D4h symmetry to 3584 symmetry distinct paths.
» login or register to post comments

confirming 57,344

Submitted by Bruce Norskog on Sat, 10/27/2012 - 12:30.

I took the 120 maneuvers returned by rubsolv, and my "uncanonicalizer" calculated 57,344 maneuvers for them, in agreement with your result.

Now just try your program using the same position composed with superflip, and see if it reports 120,511,872 optimal maneuvers. :)

» login or register to post comments

Get Real

Submitted by B MacKenzie on Sat, 10/27/2012 - 14:15.
Sure thing. Expect the answer in about 100 years.

With my code and hardware it takes about 20 minutes to find just one 26 turn hermit sequence. This is using the efficient path iterator. Using the dumb path iterator slows things down about five fold. So answering your hermit position question is out of reach. No, I'd say your strategy of working backwards from positions three turns from the hermit position looks better than tackling the problem head on.

Bye the bye, are all the 1068 positions three turns from the 26 turn position 23 turns from identity?
» login or register to post comments

Well, I did use a smiley so y

Submitted by Bruce Norskog on Sat, 10/27/2012 - 16:50.

Well, I did use a smiley so you wouldn't think I was serious.

Because of the symmetry of the 26q* position, I did not need to try all 1068 3q* maneuvers. For example, for the particular 26q* position I used, the first move could be restricted to be either U or F. Maneuvers starting with any of the other 10 moves could be mapped to a maneuver starting with U or F by applying a conjugation by one of the 16 symmetries of the cube that fixes that position. Every 3q* maneuver I tried (and I believe I covered all the necessary ones) required 23 quarter turns.

I note that the three known 26q* positions are 12q* apart from each other. Thus, it would take at least a 6q* maneuver to go from one of these 26q* position to reach a position that was at least as close to a different known 26q* position than the one you start from. Thus, a 2q* maneuver would either reach a 24q* maneuver or a currently unknown 26q* maneuver. Assuming that none of those are 26q*, then going out 3q* from one the known 26q* positions could not reach a 25q* maneuver unless it were an as yet unknown 25q* position.

» login or register to post comments

I would say that using D4h sy

Submitted by B MacKenzie on Sat, 10/27/2012 - 18:40.
I would say that using D4h symmetry to reduce the first turns is valid and your results prove that none of the 1068 positions in question is a new depth 25 position. Oh well.

I've been thinking that I might try iterating through all 5,442,351,625,028 depth 13 positions, p. Exhaustively solving q where h is the 26q position and

q = h * p'

In the rare cases where q is depth 13, exhaustively solve p. The two sets of length 13 sequences could then be combined to give solutions to the 26q positions. I don't know, it might be doable. On the other hand just iterating through all depth 13 positions might not be practical.
» login or register to post comments

an idea for looking for other deep positions

Submitted by Bruce Norskog on Sat, 10/27/2012 - 23:02.

I guess I sort of figured that if there were any other 25q* positions only 3q* away from the known 26q* positions, then they would have already been found to be 25q*. So I'm not really surprised that all were 23q*.

I've been thinking that cyclic shifting of the 361,535,616 26q* maneuvers might be a way of generating potentially good candidates for new 26q* positions. Reducing the 26q* maneuvers by symmetry should yield 7,531,992 maneuvers. Cyclic shifting these 25 ways yields potentially 188,299,800 maneuvers, but there should be many duplicate maneuvers (let alone positions, especially considering symmetrical equivalence), so the actual number of positions reached should be much less. In any case, this would seem to involve checking a very large number of fairly deep positions. Any thoughts on the feasibility of this or on how worthwhile this might be?

» login or register to post comments

Conjugacy Class

Submitted by B MacKenzie on Sun, 10/28/2012 - 14:48.
I used GAP to calculate the size of the conjugacy class of the hermit positions as 2,829,103,200. This is exactly half what I would calculate with pencil and paper--there must be some constraint on the flip. Anyway, this may be reduced with M conjugation to around 58,000,000 positions.
» login or register to post comments

Searching for depth 26 positi

Submitted by B MacKenzie on Sun, 10/28/2012 - 07:28.
Searching for depth 26 positions is like looking for a needle in a gigantic haystack where you're not sure there is a needle. My intuition is that there is no reason to expect that such conjugates will be unusually deep. They will probably come in at 20 or 22 q-turns.

On further thought any construction in the form

t1 * h * t2

where t1 and t2 are q-turns and h is the 26 q-turn hermit position has to be at either depth 24 or depth 26. These 144 hermit derivatives might be worth looking at.

The conjugate R' h R for the hermit position whose principal symmetry axis points up comes in at 24 q-turns by the way. And U' h U = h. So a 1 turn cyclic shift on any hermit turn sequence will either give a 24 q-turn position or give the hermit position back.
» login or register to post comments

I have solved all instances o

Submitted by B MacKenzie on Tue, 10/30/2012 - 11:57.
I have solved all instances of t1 * h * t2 mod 96 and except for the one case where the product is the original 26 q-turn hermit position they all come in at depth 24. So, no new antipodes there.

I have solved all two-turn hermit conjugates (there are only 5 instances after symmetry reduction). There are no 26 q-turn positions formed other than the starting position. So two turn cyclic shifts will not find a new antipode.

I also solved a set of ten random conjugates of the hermit position. Five came in at depth 20 and five came in at depth 22. For random cube positions one would expect a ratio of 2 : 1 depth 20 to depth 22. So on the evidence of this small sample hermit conjugates are somewhat more difficult to solve than random positions.
» login or register to post comments

turn sequence conjugators

Submitted by B MacKenzie on Tue, 10/30/2012 - 21:59.
After mulling over these results I've come to the realization that there is no advantage to messing around with turn sequence conjugators. It can be shown that: 
     s'n * h * sn == s2n * h
If you conjugate the hermit position by a turn sequence of length n, there will be a turn sequence of length 2n which applied to the hermit position gives the same conjugate. The proof is straightforward once you realize that conjugation by the hermit position is equivalent to conjugating by a two fold rotation. 
	p = s'n * h * sn
	p * h' = s'n * h * sn * h ' = s'n *  s‡n  =  s2n
	p =  s2n * h
I had thought that conjugation would get you to a completely different area of the Cayley graph. But actually conjugation by short turn sequences takes you right back to the same area.
» login or register to post comments

rubsolv

Submitted by rokicki on Tue, 10/23/2012 - 15:54.
The way rubsolv reduces by symmetry takes into account antisymmetry of subsequences as well as normal symmetry. Because of this, if you use -a and -s at the same time, you may need to do additional postprocessing to generate all solutions, by taking into account the reductions done by rubsolv. I have not yet released any code that does that postprocessing. I believe rubsolv is doing the correct thing; I may simply not have defined "representative" sufficiently accurately in this context.
» login or register to post comments