# Request for 4x4x4 LL scrambler.



## DavidWoner (Jun 30, 2011)

ELL is by far my worst phase of K4 and I'd like to improve since I have poor time management when it comes to cubing. I'd like to practice it without having to go through all that F3L stuff first. As I've pointed out in previous requests, I can't program my way out of a paper bag so once again I have to ask someone else.

I'd assume the easiest implementation is to choose from a list of pre-generated algs for LL positions. If this is the case then just an ELL scrambler would be much easier than a full LL scrambler.

If someone can do this I would <3 them and even possibly give them a hug (or not if that is their preference).


----------



## Kirjava (Jun 30, 2011)

If someone makes it I'll do lots more of this


----------



## Zarxrax (Jul 1, 2011)

I might be willing to try adapting support for 4x4x4 into this, but I'm not too familiar with 4x4x4 notation, though I do know that there are several varieties of notation out there.
It does support double layer turns already [r, u, d, etc] but this was intended for 3x3x3, so I have no idea what effect it would have on 4x4.


----------



## Kirjava (Jul 1, 2011)

You still have to find a way of generating algs for the 40320 ELL cases that there are.

If we had a list of algs this would be easy.


----------



## Zarxrax (Jul 1, 2011)

Oh, I thought there were cases for this >.> 
carry on then.


----------



## qqwref (Jul 1, 2011)

If someone's willing to give me a bunch of algs I could whip up something similar to the old random-state pyraminx scrambler The program would imagine a random ELL state and then solve it in 3 looks in a mechanized way (such as L edge - R edge - F/B edges) and output the solve. It would be a lot of moves, but a lot less than doing a solve and unsolve, and it would definitely be random.

If you want me to do this, I'll need to make a list of all possible scenarios for those cases. Are the ones in [wiki]KBCM Step 6[/wiki] any good?


----------



## Kirjava (Jul 1, 2011)

The problem with that is that it's quite obvious to tell when you're going to get parity. 

Lots of moves is annoying too. Someone else made a crappy one of these and my solutions were shorter than the scrambles.


----------



## vcuber13 (Jul 1, 2011)

what about doing something like RrFU scrambles then optimally solve the rest of F3L? or something similar


----------



## StachuK1992 (Jul 1, 2011)

Someone should just make kSolve not suck.
Ideas here?


----------



## qqwref (Jul 1, 2011)

Kirjava said:


> The problem with that is that it's quite obvious to tell when you're going to get parity.


Pretty sure there's no way around this. It's the same idea as asking for a post-reduction 4x4 scrambler - parity situations will always take longer just because of the constraints that are set up.



Kirjava said:


> Lots of moves is annoying too. Someone else made a crappy one of these and my solutions were shorter than the scrambles.


To be fair, the movecount would probably be something like 30-35 slice moves on average - not TOO bad. You could even try a more intelligent way, where if some pieces are solved it will work around those to only solve what it needs to. But I think that would require a lot more thought, and be a lot more annoying to program.


----------



## cuBerBruce (Jul 1, 2011)

StachuK1992 said:


> Someone should just make kSolve not suck.
> Ideas here?


 
ksolve can generate <U,r> solutions for the LL edges, but probably a little too slow for what you would want for this application. Also, I don't know if ksolve can be told to stop after the first solution found.


----------



## StachuK1992 (Jul 1, 2011)

I know it can do that, which is why I said we should make it *better*.

I'm hoping someone had an idea of *how* to make it faster. As in, a rewrite of sorts for the program.


----------



## cuBerBruce (Jul 1, 2011)

StachuK1992 said:


> I know it can do that, which is why I said we should make it *better*.
> 
> I'm hoping someone had an idea of *how* to make it faster. As in, a rewrite of sorts for the program.


 
Well, I haven't seen the source code for ksolve. It would certainly be easier to write a custom <U,r> or <U,Rw> solver program than to write a new and better "ksolve" from scratch.


----------



## deepSubDiver (Jul 1, 2011)

Can we generate parity situations with just <U,r>? If we can, I'll probably have a look into this.


----------



## qqwref (Jul 1, 2011)

deepSubDiver said:


> Can we generate parity situations with just <U,r>? If we can, I'll probably have a look into this.


 
r U2 r U2 r U2 r U2 r


----------



## MaeLSTRoM (Jul 1, 2011)

What also would be good is maybe a <r,l,u> scrambler that then solves the centres and DF/DB. that might potentially give a better scrambler for K4 ELL. just a thought.


----------



## deepSubDiver (Jul 1, 2011)

MaeLSTRoM said:


> What also would be good is maybe a <r,l,u> scrambler that then solves the centres and DF/DB. that might potentially give a better scrambler for K4 ELL. just a thought.


That is the basic idea I had, but <r,l,U> is probably a little too much to compute for just generating a scramble. The search tree would get a value of 6 (9 initially) in width and we had to track 16 pieces.


----------



## cuBerBruce (Jul 1, 2011)

MaeLSTRoM said:


> What also would be good is maybe a <r,l,u> scrambler that then solves the centres and DF/DB. that might potentially give a better scrambler for K4 ELL. just a thought.


 


deepSubDiver said:


> That is the basic idea I had, but <r,l,U> is probably a little too much to compute for just generating a scramble. The search tree would get a value of 6 (9 initially) in width and we had to track 16 pieces.



I think MaeLSTRoM meant generating a random sequence of perhaps 25 or 30 <r,l,U> moves (similar to vcuber13's idea), not writing an <r,l,U> solver. Care would be needed so that solving the edge D Layer edges doesn't affect the probability distribution of the 8 LL edge pieces. (And, of course, an AUF would be needed to solve the corners, assuming you want them solved. If you want corners scrambled, then an extra move sequence for scrambling the corners would be needed.)



cmowla said:


> Keep in mind whether or not you want a scrambler that only "preserves" the centers on the 4x4x4 or works for all big cube sizes too. If so, then the scrambles will need to be longer and many optimal <U, r> algorithms that work on the 4x4x4 won't be able to work on other big cube sizes.



We've not been talking about any cubes other than 4x4x4 in this thread. And I've been assuming that centers on a given face are to be considered indistinguishable.



cmowla said:


> If anyone really wants a scrambler that has any chance of using fewer moves than a human solution, you must allow more types of moves than just <U, r>.



<U,r> seems to generate solutions of around 25 moves. I think that this would be adequate for what David asked for, even if the sequences might be longer in some cases than what a person would need to solve them.



cmowla said:


> What counts as an ELL scramble? Surely we all can agree that if 2, 3, or 4 (and probably 5) wings unsolved is not considered a scramble. So, the maker of this software should know if indeed 6 or more wings messed up is a scramble or not. That definitely would lessen the number of algs to be found.


I've been assuming the scrambler would generate any of the 40320 cases with equal probability - well, except probably rejecting the solved case. If additional easy cases are to be rejected, it is easy to do that when using a random state generator. With a generic <U,r> solver, you would not need to find any algs up front (assuming it can generate them fast enough). You only need to find algs up front if you are using an n-phase solver approach like what qqwref suggested.


----------



## cuBerBruce (Jul 2, 2011)

I wanted to see if a custom search program could find <U,r> solutions significantly faster than ksolve. I now have some working code, and indeed a significant improvement was achieved. I used a test case that was generated from manually scrambling a cube and solving the first 3 layers and the corners. This particular test case had a 25-move optimal solution in <U,r> for either center pure or center non-pure. The test runs were done on the same computer (a fairly fast computer).


```
Solver                 First solution    Finish depth-25 search

ksolve (center-pure)       80 sec            122 sec
ksolve (non-center-pure)  171 sec            443 sec
custom (non-center-pure)    3 sec              7 sec
```

I think this test may have a higher than average move count, so typical solves may be faster. However, I'm concerned that worst case solutions may require significantly longer because of exponential time growth with respect to number of moves.


----------



## deepSubDiver (Jul 2, 2011)

I didn't check too many scrambles, but those seem okay (nice distribution of the pieces, about 50% orientation and about 50% permutation parity). It is also pretty efficient, but not optimal.

Edit, I forgot to mention: Scramble length can be easily increased for more randomness, but I think 35 moves is okay.

```
Loaded pruning table: centers, nodes: 18900
Loaded pruning table: edges, nodes: 90

Number of scrambles: 25

 1: U2 r' U' r U' r U' r U2 r2 U' r2 U2 r2 U2 r U r2 U r2 U r' U r U2 r U r U' r U r' U r  (34 BTM)
 2: r U r U2 r2 U' r2 U' r U' r2 U2 r U' r2 U2 r U' r' U' r' U2 r U' r U' r U' r2 U r U2 r  (33 BTM)
 3: r2 U2 r2 U2 r U r2 U' r' U r' U r' U2 r' U' r U2 r' U' r' U' r2 U' r' U' r U2 r' U r2 U2 r  (33 BTM)
 4: r' U r' U r U2 r U r U2 r U r2 U' r2 U r2 U2 r' U r2 U' r' U2 r2 U r' U r U r2 U2 r  (33 BTM)
 5: r U2 r2 U2 r U' r2 U' r' U' r2 U2 r' U' r2 U r U2 r2 U r' U' r' U r2 U2 r U r2 U' r U r'  (33 BTM)
 6: U r2 U' r' U r U2 r' U' r' U2 r2 U2 r U r' U2 r U2 r' U2 r' U r U' r2 U r2 U' r U2 r  (32 BTM)
 7: r U r2 U' r U' r' U' r U2 r2 U' r2 U' r2 U' r U2 r2 U' r2 U r' U' r2 U2 r' U r U' r' U2 r  (33 BTM)
 8: r2 U' r2 U' r' U r2 U' r2 U2 r' U r2 U' r' U' r U r U' r' U r' U2 r' U r2 U r U2 r U' r  (33 BTM)
 9: U' r2 U' r' U r' U r U r2 U' r2 U' r' U' r' U' r' U r' U2 r2 U2 r' U2 r U r2 U' r' U' r  (32 BTM)
10: r2 U' r' U2 r U' r U' r U r U' r' U2 r' U2 r2 U r2 U r U r' U2 r' U2 r' U' r' U2 r U r2  (33 BTM)
11: U2 r U r U' r2 U2 r2 U2 r' U2 r2 U' r' U' r U2 r U' r' U r' U r U r2 U' r' U r U' r2 U2 r'  (34 BTM)
12: U' r U2 r2 U r U r2 U' r' U' r' U2 r U' r U r' U2 r U2 r U2 r' U' r2 U2 r' U' r2  (30 BTM)
13: U2 r U2 r2 U2 r' U2 r U r' U' r' U2 r' U r2 U' r2 U' r' U' r2 U r2 U' r2 U2 r U2 r' U' r'  (32 BTM)
14: r' U' r' U' r U2 r' U r' U' r2 U' r U2 r' U r2 U2 r2 U2 r2 U' r2 U2 r' U2 r U r U' r2 U r'  (33 BTM)
15: U r' U r U' r U' r U2 r2 U r' U r2 U' r2 U r2 U2 r' U2 r' U' r2 U' r U' r' U2 r' U' r  (32 BTM)
16: r U2 r' U r2 U2 r' U r' U r2 U r2 U r U2 r2 U' r' U' r U r' U2 r2 U r' U r' U r U2 r  (33 BTM)
17: U r U2 r2 U r U' r U r' U r2 U' r U' r2 U2 r U r U r2 U r2 U r U r U' r U2 r' U r2  (34 BTM)
18: r2 U r2 U2 r U' r' U r' U' r2 U' r2 U2 r2 U' r U2 r2 U r U r' U r U r2 U' r2 U r2 U r'  (33 BTM)
19: U r2 U' r' U r2 U2 r U2 r U2 r2 U2 r2 U r' U2 r2 U' r U r' U2 r2 U2 r2 U r2 U' r  (30 BTM)
20: r U2 r2 U' r' U' r' U r' U2 r U r2 U' r' U r2 U r' U r' U' r U2 r2 U2 r U r2  (29 BTM)
21: U2 r U r' U2 r2 U r2 U r U2 r2 U' r U2 r2 U' r U2 r2 U r' U2 r2 U r U' r U2 r2 U r' U2 r2  (34 BTM)
22: U' r' U2 r' U' r U r U' r U2 r' U r2 U' r' U r' U' r2 U2 r' U r2 U2 r2 U r2 U2 r U2 r  (32 BTM)
23: U' r' U2 r U2 r' U' r2 U r2 U r U2 r2 U r U r U r U r U' r U r U' r2 U r' U2 r'  (32 BTM)
24: U' r2 U' r' U' r' U' r2 U r' U2 r U2 r U2 r2 U2 r' U r2 U2 r U r U r2 U' r' U2 r U2 r  (32 BTM)
25: r2 U2 r2 U2 r U r U r2 U2 r2 U' r2 U' r2 U' r U r' U2 r2 U2 r2 U r2 U' r2 U r U' r2 U' r'  (33 BTM)

Time computed: 0,106 seconds (average: 0,00424 seconds)
```


----------



## Owen (Jul 2, 2011)

Just use a regular 4x4x4 scramble, and solve everything but the last layer. Wow people, don't be lazy.


----------



## irontwig (Jul 2, 2011)

Owen said:


> Just use a regular 4x4x4 scramble, and solve everything but the last layer. Wow people, don't be lazy.



I don't think that the fact that some people might want to use their practice times efficiently has a lot to do with laziness.


----------



## Kirjava (Jul 2, 2011)

cmowla said:


> Surely we all can agree that if 2, 3, or 4 (and probably 5) wings unsolved is not considered a scramble.



I disagree with this. No current cube scrambler does this and I don't see why ELL should be any different.



deepSubDiver said:


> I didn't check too many scrambles, but those seem okay (nice distribution of the pieces, about 50% orientation and about 50% permutation parity). It is also pretty efficient, but not optimal.



In this context, only one type of parity exists. 

However, holy ****. This seems to be pretty much exactly what we were after. Any chance you could release the program? It would be useful if you released the source too so we could incorporate this into Nibblr or Minxy.



Owen said:


> Just use a regular 4x4x4 scramble, and solve everything but the last layer. Wow people, don't be lazy.



Well done, you missed the entire point of the thread.


----------



## cuBerBruce (Jul 2, 2011)

deepSubDiver said:


> I didn't check too many scrambles, but those seem okay (nice distribution of the pieces, about 50% orientation and about 50% permutation parity). It is also pretty efficient, but not optimal.
> 
> Edit, I forgot to mention: Scramble length can be easily increased for more randomness, but I think 35 moves is okay.


 
So, clearly this is not a random-state based scrambler. It looks like you are making some number of random <U,r> moves (alternating the axis on each move, of course) and then solving (also in <U,r>) the F3L pieces with a depth-first search. You seem to ignore the LL corners, so typically an AUF is needed to solve them. This probably doesn't matter much, except that randomness of the edge configurations needs to be checked with respect to the LL corners rather than with respect to the F3L.


----------



## cuBerBruce (Jul 3, 2011)

I have generated optimal <U,r> scrambles for all 40319 cases of the 4x4x4 with everything solved except for the last layer edges. The number of moves required ranges from 12 moves to 27 moves. Only 2 configurations require 27 moves. These two cases were solved with my program on my computer in under 20 seconds each. On average, about 1.2 seconds was needed per case. The average number of moves is about 22.526.

The 12-movers are the canonical H-Perm and the UF-UB dedge swap.

The complete distribution:


Spoiler





```
moves  count   count if final AUF ignored
 11       0         2
 12       2         1
 13      11        14
 14       4        14
 15      86       108
 16      56       240
 17     414       290
 18     162       600
 19    1495      1593
 20    1170      3443
 21    6146      6486
 22    5589      9851
 23   15269     12888
 24    7108      3978
 25    2729       807
 26      76         4
 27       2         0
      -----     -----
      40319     40319
```




EDIT: I've updated the table in the spoiler to give the distribution when AUF maneuvers at the end of a scramble are ignored.


----------



## qqwref (Jul 3, 2011)

Interesting distribution. I'm a bit surprised at how quickly it drops off, and how the odd numbers seem to be higher than the next even number.

I think, for speed purposes, it would not be too crazy to hard-code in the 26 and 27 move cases, and then only search up to 25 moves. What do you think? (Also: If we don't count AUF before and after, how does that improve the search speed?)


----------



## Kirjava (Jul 3, 2011)

cuBerBruce: can you paste the list somewhere? this is pretty much exactly what we need


----------



## chicken9290 (Jul 3, 2011)

use yau its a better method (i learned it in a day and started averaging sub 65 seconds)


----------



## Cool Frog (Jul 3, 2011)

chicken9290 said:


> use yau its a better method (i learned it in a day and started averaging sub 65 seconds)


 
Ignorance is bliss.


----------



## cuBerBruce (Jul 3, 2011)

qqwref said:


> Interesting distribution. I'm a bit surprised at how quickly it drops off, and how the odd numbers seem to be higher than the next even number.
> 
> I think, for speed purposes, it would not be too crazy to hard-code in the 26 and 27 move cases, and then only search up to 25 moves. What do you think? (Also: If we don't count AUF before and after, how does that improve the search speed?)


 I could change the code to consider there to be 4 solved states instead of 1. This would allow eliminating the AUF at the end of a scramble. For some cases, all optimal <U,r> scrambles start with a U layer move. For example, for the UL-UR dedge swap, all optimal <U,r> scrambles start with a U or U' move. So you can't assume the scramble can start with an r layer move.



Kirjava said:


> cuBerBruce: can you paste the list somewhere? this is pretty much exactly what we need


 Kirjava, can I email you a half-megabyte zip file at the email address on your K4 page? Also, I would like to know what data you want. I have generated all optimal scrambles (for the corners solved states) as well as 1 per case. Right now, my one per case data set has cases where the scramble could be replaced by a maneuver where an AUF could be omitted at the end. So if you want scrambles that are "optimized" in this way, I can send the maneuvers after I regenerate the data in that manner.


----------



## Kirjava (Jul 3, 2011)

cuBerBruce said:


> Kirjava, can I email you a half-megabyte zip file at the email address on your K4 page? Also, I would like to know what data you want. I have generated all optimal scrambles (for the corners solved states) as well as 1 per case. Right now, my one per case data set has cases where the scramble could be replaced by a maneuver where an AUF could be omitted at the end. So if you want scrambles that are "optimized" in this way, I can send the maneuvers after I regenerate the data in that manner.


 
Yeah, just send it over to [email protected]. Half a meg doesn't seem that big.

I'd just like one scramble per case. Preferably one on a line each with no other data on the line. Please keep the AUF in as we would like corners solved.

Thanks!


----------



## cuBerBruce (Jul 4, 2011)

I have now calculated "optimized" <U,r> move sequences if you want to allow the corners to be an AUF move from solved. The edge permutation is considered to use the corner pieces as reference, so a U layer turn is not considered to change what edge permutation case you have. I have added this move count distribution to the spoiler in my [post=601369]post[/post] earlier in the thread.

I also note that of the of the 11 cases that require 13 moves (where corners are kept fixed, not AUF'ed), 2 of those were odd parity. These are inverses of each other, and 4-cycle the UF and UB dedge pieces. I note these are also palindromes. (These are known manuevers. I am not claiming them to be newly discovered.)

r U2 r2 U2 r' U2 r U2 r' U2 r2 U2 r
r' U2 r2 U2 r U2 r' U2 r U2 r2 U2 r'

Given qqwref showed that there are 9-move 4-cycles (involving non-LL edge pieces), I guess it should not be too surprising to find 4-cycles among the 13-move maneuvers affecting only LL edges. (Yeah, I know these 4-cycles really also have hidden effects on center pieces as well.)


----------



## cuBerBruce (Jul 5, 2011)

Attached is the source code that I used for generating the optimal <U,r> maneuvers for the various ELL cases. The file is intended to be the primary file in a "Win32 Console Project" for Microsoft Visual Studio, so if you are using another compiler, just delete the line with #include "stdafx.h" and it should probably compile fine.


----------



## Isaac VM (Nov 4, 2022)

Sorry for bumping this thread.
I haven't been able to find an online K4 ELL scrambler and I am not familiar with visual studio so I don't know if the file that cuBerBruce shared is a scrambler or how does it work. I also noticed mentioned in the wiki that there is a rubik IRC bot which is able to provide k4ell scrambles but I also don't know how to use it.

Thanks in advance!


----------

