What is the minimum number of algorithms needed for 2 look last layer?

[10461394944000]

What about partial edge control (sexy or sledge)? That would eliminate all dot OLLs

what is the minumum number of algorithms needed such that for any last layer case, you can apply 2 algorithms and solve the cube?

no because edge control is not LL

 

[Hypocrism]

You could even 1-look with a beginner's method if you predict where the irrelevant pieces go after each algorithm. So, for a 2-look that is practically doable, you just need 4

1st look:
FURU'R'F + Sune (you predict the sune case before FURU'R'F' algorithm)

2nd look:
A perm + U perm (predict the edge case before A-perm combination)

And I'm sure that you could do it with fewer in a similar way!

For a speedsolving method, obviously this isn't a practical choice, but it's legitimate if you don't assume 1 case -> 1 algorithm.

 

[Deleted member 36445]

until now the winner is CLL+ELL with 71 cases

 

[Tempus]

what is the minumum number of algorithms needed such that for any last layer case, you can apply 2 algorithms and solve the cube?

it's probably some really silly thing that would be silly to recognize but it seems like an interesting question.

what about 3 look?

I can't really think of a way of finding such a method so i'll let the puzzle theory people find it instead

I think this is a fascinating quesiton. So fascinating, in fact, that I already thought of it before joining this forum. A few months ago, when I started getting into cubing again, I wrote a crude program to try to answer questions such as this using a Monte Carlo algorithm. The problem is that it requires a vast amount of processing time. Even running on eight cores, it takes a long time to get any kind of result, and that result will never be perfect because it's using a Monte Carlo approach. Still, I have hauled the code out of mothballs and am trying to at least establish an upper bound. It will take time, however...

 

[qqwref]

I really like the idea of having some shared cases between the two sets - Lucas suggests maybe a few, but I'm thinking of having only one bigger set of algs, so that we can solve the LL by doing some two of them in sequence. It would be like a crazy version of the "two sunes" beginner method to OCLL. Unfortunately there is no obvious way to construct such a set of algs.

Using the same alg for multiple cases is also an interesting idea, although pretty much only 2-corner twists can be used if we restrict ourselves to the last layer. (It does save an OLL, though.) I wonder if there is some kind of other geometry we could get the pieces into on the first step, which would have more symmetries than the LL. I would say that any rotations between steps are allowed, BTW.

I think this is a fascinating quesiton. So fascinating, in fact, that I already thought of it before joining this forum. A few months ago, when I started getting into cubing again, I wrote a crude program to try to answer questions such as this using a Monte Carlo algorithm. The problem is that it requires a vast amount of processing time. Even running on eight cores, it takes a long time to get any kind of result, and that result will never be perfect because it's using a Monte Carlo approach. Still, I have hauled the code out of mothballs and am trying to at least establish an upper bound. It will take time, however...

Ooh, cool. Do you remember anything more specific about how your program worked?

edge control while doing f2l the you have corners to solve for oll (first look) and then PLL ( for second look)

What about partial edge control (sexy or sledge)? That would eliminate all dot OLLs

You could even 1-look with a beginner's method if you predict where the irrelevant pieces go after each algorithm. So, for a 2-look that is practically doable, you just need 4

until now the winner is CLL+ELL with 71 cases

Please! Read the thread!!!

 

[Tempus]

Ooh, cool. Do you remember anything more specific about how your program worked?

Given n and m, it uses a Monte Carlo approach to generate a set of n algorithms which is sufficient to solve the last layer in m looks. It is currently processing, and I will post some results when I have them, although I do need to tidy up the output routines to make it produce something presentable. This program was written only for my own use, and as a result its user interface is very rough around the edges.

 

[cubernya]

Just thought of this (technically correct) no-look method for any LL: Devil's Algorithm

Obviously this is not what is wanted, but I just want to throw that out there.

 

[uberCuber]

Just thought of this (technically correct) no-look method for any LL: Devil's Algorithm

Obviously this is not what is wanted, but I just want to throw that out there.

It's not really no-look though. If you don't look, how can you know when the cube is solved? In fact, it could be up to a 43-quintillion-look method, since the process is:
Perform one move
Look to see if the cube is solved
If it's not solved, repeat.

 

[IRNjuggle28]

People should have to apply to post in the puzzle theory forum IMO. Spam elsewhere isn't a big deal, but this is getting ridiculous. If people don't know what they're talking about, they should shut up. That's why I virtually never post in here. I don't know much about puzzle theory. But at least I know that I don't know. Come on.

All last layer cases means all last layer cases. Proposing a pre-LL substep that eliminates LL cases is exactly what Ben didn't want. He is specifically asking about LL uninfluenced by F2L. You guys are coming up with ideas that are good for speedcubing. That's not what this is. It's a math question.

 

[Kirjava]

61

Was not optimised for low alg count, can be done.

 

[kinch2002]

I would have thought that you can get a lot lower than the theoretical 62 that Lucas proposed, by having overlapping alg sets for the 2 steps. I don't believe that anything was specified to say that the first step must reduce the cube to an easily-defined subset of states i.e. we can use an approach like Kirjava's LL stuff. Therefore a new theoretical lower limit would be 31 algs that are used as both the first and second step?

 

[Kirjava]

I think you could brute force a much better answer with my approach with some code and a lot of processing time.

 

[cmhardw]

I would have thought that you can get a lot lower than the theoretical 62 that Lucas proposed, by having overlapping alg sets for the 2 steps. I don't believe that anything was specified to say that the first step must reduce the cube to an easily-defined subset of states i.e. we can use an approach like Kirjava's LL stuff. Therefore a new theoretical lower limit would be 31 algs that are used as both the first and second step?

I find the argument convincing that an alg could be used in either phase I or phase II or this proposed LL approach. However, how do you jump from 62 down to 31? It's not intuitively obvious to me that all 31 algs could be dual purpose algs like this. Is this a conjecture on your part, or do you have some insight that you can give to help me to see it too?

@Kir - Your results in the post you link really changed my perspective on this topic. I thought Lucas' argument was convincing that 62 was the minimum. The idea of algorithms serving both phase I and phase II functions makes sense as to how to optimize this LL method to have fewer than 62 algorithms.

 

[irontwig]

I find the argument convincing that an alg could be used in either phase I or phase II or this proposed LL approach. However, how do you jump from 62 down to 31? It's not intuitively obvious to me that all 31 algs could be dual purpose algs like this. Is this a conjecture on your part, or do you have some insight that you can give to help me to see it too?

Well, think about how you would solve the reverse of some case...

 

[kinch2002]

I find the argument convincing that an alg could be used in either phase I or phase II or this proposed LL approach. However, how do you jump from 62 down to 31? It's not intuitively obvious to me that all 31 algs could be dual purpose algs like this. Is this a conjecture on your part, or do you have some insight that you can give to help me to see it too?

@Kir - Your results in the post you link really changed my perspective on this topic. I thought Lucas' argument was convincing that 62 was the minimum. The idea of algorithms serving both phase I and phase II functions makes sense as to how to optimize this LL method to have fewer than 62 algorithms.

I meant that 31 is a lower bound for the answer, not that 31 is definitely possible. You'd need at least 31 algs otherwise you can't cover all LL cases - using Lucas' calculation of (4*31 + 1)(4*31 + 1) = 15625.

I'm now having second thoughts on the accuracy of this - need to think about the whole AUF/rotation thing for a bit longer. Also, the use of skips in the calculation, when your sets of algorithms overlap

EDIT: I now think 32 is a lower bound because assuming that we now have one pool of n algorithms, we can only reach 4*n states with 1 algorithm and 4 states with 0 algorithms, so we require (4*n)(4*n)+4*n+4 >= 15552, simplified to 16n^2+4n-15548 = 0. This gives the solution n=31.05, thus 32 algorithms are required.

 

[Tempus]

One pass of my program takes several hours to complete. It was able to arrive at a solution for n=67 in one pass. It's done about 4 passes now at n=66 and the best it's managed so far is to cover 62200 of the 62208 cases. As you can guess from that number, it does not take any symmetries into account, however it does make allowances for AUF before, between, and after algorithms. It considers neither mirrors nor inverses to be equivalent, so the 67 algorithms might contain mirrors and/or inverses, except that it's formulated to use F, R, and U moves exclusively, so identifying mirrors a glance might be tricky. More data to come after further processing...

 

[cmhardw]

Well, think about how you would solve the reverse of some case...

Do I understand correctly: The case count reduces by half since every alg and it's inverse solve a different case?

Just to clarify: Are we counting the inverse of an algorithm in our list as a different algorithm?

I meant that 31 is a lower bound for the answer, not that 31 is definitely possible. You'd need at least 31 algs otherwise you can't cover all LL cases - using Lucas' calculation of (4*31 + 1)(4*31 + 1) = 15625.

I'm now having second thoughts on the accuracy of this - need to think about the whole AUF/rotation thing for a bit longer. Also, the use of skips in the calculation, when your sets of algorithms overlap

EDIT: I now think 32 is a lower bound because assuming that we now have one pool of n algorithms, we can only reach 4*n states with 1 algorithm and 4 states with 0 algorithms, so we require (4*n)(4*n)+4*n+4 >= 15552, simplified to 16n^2+4n-15548 = 0. This gives the solution n=31.05, thus 32 algorithms are required.

I misread your first post. It is clear to me now that you meant this (now updated) number to be a lower bound.

 

[cuBerBruce]

I meant that 31 is a lower bound for the answer, not that 31 is definitely possible. You'd need at least 31 algs otherwise you can't cover all LL cases - using Lucas' calculation of (4*31 + 1)(4*31 + 1) = 15625.

I'm now having second thoughts on the accuracy of this - need to think about the whole AUF/rotation thing for a bit longer. Also, the use of skips in the calculation, when your sets of algorithms overlap

EDIT: I now think 32 is a lower bound because assuming that we now have one pool of n algorithms, we can only reach 4*n states with 1 algorithm and 4 states with 0 algorithms, so we require (4*n)(4*n)+4*n+4 >= 15552, simplified to 16n^2+4n-15548 = 0. This gives the solution n=31.05, thus 32 algorithms are required.

I agree that with 32 being a lower bound.

Initial state: 1 state
AUF + 1 alg applied: 4*31 = 124 states
AUF + 1st alg + AUF + 2nd alg: 124*4*31 = 15376 states
Max total reached states: 1 + 124 + 15376 = 15501 < 15552
So 31 not sufficient:
For 32, I get 1 + 128 + 16384 = 16513 > 15552; so it seems 32 could work.

 

[cmhardw]

I agree that with 32 being a lower bound.

Initial state: 1 state
AUF + 1 alg applied: 4*31 = 124 states
AUF + 1st alg + AUF + 2nd alg: 124*4*31 = 15376 states
Max total reached states: 1 + 124 + 15376 = 15501 < 15552
So 31 not sufficient:
For 32, I get 1 + 128 + 16384 = 16513 > 15552; so it seems 32 could work.

I like this calculation, that's a neat way to verify 32 as a lower bound. Also, this confirms Daniel's calculation. I think a 32 alg lower limit is pretty clear

 

[kinch2002]

I agree that with 32 being a lower bound.

Initial state: 1 state
AUF + 1 alg applied: 4*31 = 124 states
AUF + 1st alg + AUF + 2nd alg: 124*4*31 = 15376 states
Max total reached states: 1 + 124 + 15376 = 15501 < 15552
So 31 not sufficient:
For 32, I get 1 + 128 + 16384 = 16513 > 15552; so it seems 32 could work.

I think you forgot AUF and no algs (3 states). That would give you the same calculation as mine: 4n*4n+4n+4

Of course no difference to the result