FMC minimal parity challenge

[Lucas Garron]

For a while, I've wondered about an optimal BLD parity alg.

So: Exchange any two corners and any two edges of a 3x3x3, but nothing else.

The best I know is a J-perm that's 10HTM, 10STM, 10ATM, and I want to know if it's possible to do better.

I think the problem is that you can't comm low enough. This solution is probably optimal for CE comm + AUF (parity)


Any brilliant ideas?

(I mean you, Per, Johannes, and Stefan. It's FMC-brainpower vs. a trivial exhaustive search. )

 

[mrCage]

For a while, I've wondered about an optimal BLD parity alg.

So: Exchange any two corners and any two edges of a 3x3x3, but nothing else.

The best I know is a J-perm that's 10HTM, 10STM, 10ATM, and I want to know if it's possible to do better.

I think the problem is that you can't comm low enough. This solution is probably optimal for CE comm + AUF (parity)


Any brilliant ideas?

(I mean you, Per, Johannes, and Stefan. It's FMC-brainpower vs. a trivial exhaustive search. )

Hmm. Using ACube you may find optimal alg in all metrics desired. For insertion into a skeleton you may of course fare better - due to achieved turn cancellations. So it really depends what you are after. Speed is yet another consideration, but i assume speed was not really an issue here

On bigger cubes than 3x3x3 there may well be (theoretically at least) better algorithms than for 3x3x3 due to other moves possible.Solely using outer layer turns will remain the same as for 3x3x3.

- Per

(edit)
If you look at a J-perm (10-turn version), any cyclical shift of the sequence for it, will yield another parity alg of same length. The J-perm does not start and end with same layer - so no cancellation can be achieved by a cyclical shift.

Note that ANY conjugation has some cancellation achievable by a cyclical shift!!
(/edit)

 

[Lucas Garron]

But is there a 9-mover? Or a good reason (i.e. short proof) that the shortest is 10?

 

[Kenneth]

I know no 9 turn algs for parity, most are in the range 11-12, here are some:

R' U R U2 Ra' U R U' L U2 ... Well 10 but Ra' is a little cheating, some may think it's two turns (R' L')

R' U2 L U' L' U2 Ra U' L' U ... basicly the same as the last one.

r U r' U F' U F U2 R U' r' U ... Hmmm, 12

(x) U R' U F' U F U2 R U' r' U L ... exactly the same alg as the last one but first turn moved to last

(x2) R2 U2 R U2 L U2 L' U2 (x') U2 L' U2 l' ... my big cubes parity


l2 d' R2 d l2 (y') r2 d L2 d' r2 U ... T-PLL

------

Did some calculations and if we ignore mirrors and reflections it's 3 corner situations, adjacent, digonal 2D and digonal 3D. These situations got 3 orientations each making it 3*3=9 corner cases. From there it's 5 uniqe edge configurations each having two orientations 2*5=10 (if I got it right). So it's a total of 90 uniqe situations.

Can't be that hard to brute force for the shortest alg using ACube.

 

[mrCage]

Can't be that hard to brute force for the shortest alg using ACube.

Well, 90 cases - seems like some automated script would come in handy here.

-Per

(edit)
PS!! A good single layer parity like that would have been found ages ago if it existed. If it exists it must be a non-single layer solution. Not so useful for most methods ...
(/edit)

 

[AvGalen]

This is what I tried in cube explorer (4.30):
0) Switch to WCA color-scheme
1) Right-click both stickers of the UF-edge so they become grey
2) Put the white-green (UF) edge in the first possible position (UR)
3) Right-click all stickers of the first possible position for the corners (UFL and UFR) so they become grey
4) Let cube explorer find solutions. As soon as at is clear that no 9 mover exists (only takes 1 second) I stop the search. Most of the time a 10 mover shows up almost instantly
a) Return to step 3, only use UFL and UBR corners. I have tried all 7+6+5+4+3+2+1 positions of the corners
b) Return to step 2, only use RU edge (same as UR only flipped). I have tried only the first 6 positions (full U-layer)

If someone would like to do the other (8*2)*(7+6+5+4+3+2+1) positions (or be smarter and skip mirrors/reflections) that would be nice, but based on my FMC-experience, logic, feeling and the above testing I don't expect a 9 mover to be possible. I have no idea how to prove any of this, except for brute-forcing all posibilities. Just like I have no idea how to prove that a 3-edge-cycle can be done in 6 moves, a 2*2-edge-cycle also requires 6 moves and a 3-corner-cycle requires 8 (how many does a 2*2-corner-cycle require? I would expect the answer to be 10 and be a variation of H-Perm or R2U2R2U2R2U2)

I would also be interested in the maximum number of moves that would be needed for the F2L and for a 2x2x3-block (I suspect 14 and 10 but have no proof). This is for FMC, not for blind though

 

[Kenneth]

Well, 90 cases - seems like some automated script would come in handy here.

Make it 108, I think I missed one edge configuration.

...based on my FMC-experience, logic, feeling and the above testing I don't expect a 9 mover to be possible...

Jepp, I feel the same.

 

[Kenneth]

Make it easier: is it possible to swap two corners on a 2x2x2 in 9 turns?

If not, then there are no parity algs of 9 turns.

 

[Mike Hughey]

Make it easier: is it possible to swap two corners on a 2x2x2 in 9 turns?

If not, then there are no parity algs of 9 turns.

Very clever, Kenneth!

 

[AvGalen]

And the answer is yes, it can be done in 9 turns (or less) on a 2x2x2. Basically a 3-cycle of corners + layer-correction can be 2-corner-swap. Just try A-Perm (clockwise) and do a U'.

Or try something like F RUR'U' F' (or Sune) + U-correction on a 2x2x2 for even shorter cycles if you don't care about the orientation

 

[Johannes91]

This list uses QTM, but here's a link anyway: http://www.ws.binghamton.edu/fridrich/c2e2.html.

With this logic I can be 100% sure that my logic is almost certainly wrong and/or correct.

based on my [..] logic [..] I don't expect a 9 mover to be possible.

Heh.

I would also be interested in the maximum number of moves that would be needed for a 2x2x3-block (I suspect 10 but have no proof).

See http://cubezzz.homelinux.org/drupal/?q=node/view/116. It seems to be 11.

 

[AvGalen]

That list of QTM moves doesn't prove that 10 moves are necessary, but it does make it even more likely. The first alg is 13 moves QTM and contains 3 half turns

Using my logic you got that 11 moves for 2x2x3 from this sentence:

From superflip, a 3x2x2 block can be built using the following sequence:
U2 R2 F' U' L D' R2 F L' D R

The reason I asked this for FMC was because I "aim" for a 5 move 2x2x2-block (not always possible), an 8 move 2x2x3 block (also not always possible) and a 15 move F2L (no proof, but I suspect this to be always possible). It's kind of funny that I have more trouble finding that 15 move F2L than those other aims

 

[cuBerBruce]

Using my logic you got that 11 moves for 2x2x3 from this sentence:

From superflip, a 3x2x2 block can be built using the following sequence:
U2 R2 F' U' L D' R2 F L' D R

Yes, superflip requires 11 moves (FTM) to create a 2x2x3 block. Because of its symmetry, it doesn't matter which 2x2x3 block. Although I had only done the analysis for solving one particular 2x2x3 block (out of 12 possible), I actually was able to conclude that 11 moves is the worst case for block-neutral 2x2x3 block. I think that hadn't really sunk in yet when I wrote that post.

 

[AvGalen]

I think you are right in assuming 11 moves is the worst case for block-neutral 2x2x3 block, but you cannot conclude/proof that just from the fact that superflip needs 11 moves.

A sequence for building the 3x2x2 block for the position at distance 12 in FTM is:
D F B' U2 F2 U L2 D' L' B' R U2
(Do the inverse to create from a solved cube.) It certainly appears to me that there exists no 3x3x3 position can have this configuration for all 12 possible 3x2x2 blocks. Therefore, no 3x3x3 scramble requires 12 face turns to build some 3x2x2 block.

For that scramble (U2 R' B L D L2 U' F2 U2 B F' D') an 8 mover 2x2x3 block exists: D F B' U' L D' B' R

 

[cuBerBruce]

I think you are right in assuming 11 moves is the worst case for block-neutral 2x2x3 block, but you cannot conclude/proof that just from the fact that superflip needs 11 moves.

A sequence for building the 3x2x2 block for the position at distance 12 in FTM is:
D F B' U2 F2 U L2 D' L' B' R U2
(Do the inverse to create from a solved cube.) It certainly appears to me that there exists no 3x3x3 position can have this configuration for all 12 possible 3x2x2 blocks. Therefore, no 3x3x3 scramble requires 12 face turns to build some 3x2x2 block.

For that scramble (U2 R' B L D L2 U' F2 U2 B F' D') an 8 mover 2x2x3 block exists: D F B' U' L D' B' R

In that post, I forgot to mention which 2x2x3 block was the one requiring 12 moves. You can solve a 2x2x3 block in less than 12 moves simply because you're solving for the wrong block.

Quoting from a follow-up to that post:

By the way, in my original post, the algs listed are for solving the 3x2x2 block with UFL and URF corners. You could figure that out from the superflip alg, but it would not be so obvious for the distance-12 alg.

There is only one such 12-move case, and you can't configure all the pieces so that you have that configuration for all 12 possible 2x2x3 blocks. So there can't be a 12-move block-neutral case.

 

[AvGalen]

I realised that your scramble was for the UF-2x2x3-block. I just wanted to make it clear that for other 2x2x3-blocks shorter sequences are possible.

First you say

It certainly appears to me that there exists no 3x3x3 position can have this configuration for all 12 possible 3x2x2 blocks

Later you say

There is only one such 12-move case, and you can't configure all the pieces so that you have that configuration for all 12 possible 2x2x3 blocks. So there can't be a 12-move block-neutral case.

"certainly seems" is very different from "can't be" (where is the proof for that?). But I agree with you anyway that the limit for this is 11.

Now how about the other limits:
Full F2L?
The original question 2-corners+2-edges?
All corners only (I expect 11 like on 2x2x2, but it might be more because of the centers)
All edges only (at least 20, because of the super-flip, but has it been proven that it cannot be >20?)
Last layer only (should be easy to find because of sites like http://www.ai.univ-paris8.fr/~bh/cube/, but that only gives 12.58 for average)

 

[Kenneth]

I think 16 HTM is the worst LL case (I have no proof). All pices permuted (edges solved) and all four corners twisted, there are two cases (H and pi) but they are equally bad.

 

[ch_ts]

All edges only (at least 20, because of the super-flip, but has it been proven that it cannot be >20?)

14 moves for edges:
http://cubezzz.homelinux.org/drupal/?q=node/view/118

Richard Korf says "It took about 35 days on a dual-processor workstation, with three terabytes of disk storage."

 

[AvGalen]

I wasn't very clear last time and was even inconsistent, so let's try again:

What are the maximum amount of moves needed to:
* Solve F2L, without caring about the last layer? Guess = 15
* Swap 2 corners and 2 edges without caring about their orientation, but without disturbing the rest of the cube? Guess = 10 for minimum amount of moves needed
* Solve all 8 corners, without caring about the edges? Guess = 11
* Solve all 12 edges, without caring about the corners? Answer = 14

Kenneth gave cases for solving the 8 corners, without disturbing the rest of the cube, but I think he was wrong about the two cases (H and pi) being equally bad.
R' U2 R U2 R2 B' D' R' F R2 F' D B U' R' U' (16f*) (I think this is H)
R U2 L2 D L' U2 L2 D' L R' U R2 B2 R2 U' (15f*) (I think this is pi)

I gave a possible limit for solving the 12 edges, without disturbing the rest of the cube, but I wanted to know about the limit for just edges which ch_ts showed to be 14.

 

[cuBerBruce]

* Solve F2L, without caring about the last layer? Guess = 15

695,280,402,432,000 cases, assuming a specific choice for the LL. Symmetry reduction of near 8x could be done. Very challenging to do a God's algorithm calculation for this. This is a much bigger calculation than the one done by Kunkle/Cooperman - about 64x bigger in symmetry-reduced terms.

* Swap 2 corners and 2 edges without caring about their orientation, but without disturbing the rest of the cube? Guess = 10 for minimum amount of moves needed

I believe all 2x2x2 cases with the other 6 corners unaffected are at least 10 moves (HTM). But I am not certain I checked every case. So I think 10 is minimum. I note Jaap's Puzzle Page site has an applet with an HTM-optimal 2x2x2 solver.
http://www.geocities.com/jaapsch/puzzles/cube2.htm

By the way I found this 10-mover in Cube Explorer. U F2 L2 B D B' L2 F U' F (10f*)

* Solve all 8 corners, without caring about the edges? Guess = 11

I'm surprised you're calling this a guess. This has been long known. http://cubezzz.homelinux.org/drupal/text/fullcube.txt contains both the 2x2x2 and 3x3x3 corners calculations.

Kenneth gave cases for solving the 8 corners, without disturbing the rest of the cube, but I think he was wrong about the two cases (H and pi) being equally bad.
R' U2 R U2 R2 B' D' R' F R2 F' D B U' R' U' (16f*) (I think this is H)
R U2 L2 D L' U2 L2 D' L R' U R2 B2 R2 U' (15f*) (I think this is pi)

I note that Silviu Radu found that 22 quarter turns suffice for this. (I confirmed his result.)
http://cubezzz.homelinux.org/drupal/?q=node/view/33