# 5x5x5, 6x6x6, 7x7x7 or NxNxN solvers

Discussion in 'Software Area' started by dwalton76, Jan 16, 2017.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

1. ### dwalton76Member

34
18
Jan 2, 2017
I've move the solver to its own repo here:
https://github.com/dwalton76/rubiks-cube-NxNxN-solver

The lookup tables for 2x2x2 and 4x4x4 are small enough that gzipped them and checked them into the repo. The lookup tables for 5x5x5 and 6x6x6 are several gigs so I cannot put them in the repo but I have them in a dropbox folder that I can share...ping me if you want access.

I've been working on 6x6x6 centers, I can stage them now

The algorithm for staging 6x6x6 centers is
• stage the UD inner x-centers
• pair the UD oblique edges (the edges in the centers, between the outer x-centers)....kudos to xyzzy for this idea
• at this point the UD centers have been reduced to 5x5x5 centers so use the 5x5x5 solver to stage the UD outer x-centers
• stage the LR inner x-centers and LR oblique edges
• at this point the LR centers have been reduced to 5x5x5 centers so use the 5x5x5 solver to stage the LR outer x-centers

2. ### Herbert KociembaMember

168
40
Nov 29, 2008
Nice, I will have a look at it soon! Meanwhile my 3x3x3 Python solver is almost finished and the code just needs a bit to be polished up and documented. I consists of a server you can run on any machine and which takes the cube definition string from the client and returns the solving maneuver to the client. You can connect to the server with telnet for example or easier with a simple GUI-interface I also provide. The performance is better than I expected with the combination Python/Raspberry PI3. Running the server on the RaspberryPi3 with a time limit of 3 seconds per solve I got the following results for 100 random cubes:
18: 4, 19: 31, 20: 48 and 21:17. So the average solving length is less than 20 moves on the Raspi if 3 secons of "thinking" is allowed.

I also will upload it to Github soon and I think it is better to open a new thread for discussions concerning the solver since it seems a bit misplaces in this thread which deals with 5x5x5 and higher.

3. ### dwalton76Member

34
18
Jan 2, 2017
Sounds cool, I'm looking forward to trying it out

4. ### dwalton76Member

34
18
Jan 2, 2017

Can now solve 6x6x6 centers...next step is to reduce the edges to a 4x4x4

5. ### qqwrefMember

7,828
27
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
Cool to see the development of more good NxNxN solvers! Many of the ones in the past have been private or never got released, so there are actually very few out there.

Sounds pretty good for reduction! I think in the 4x4x4 FMC challenge some people had solvers that could reduce the 4x4x4 in not much move than 25 moves, but that probably requires a lot of searching.

You definitely want to fix parity while solving centers here. In fact, that's a good idea for all big cubes; 4x4/5x5 have one parity type, 6x6/7x7 have two, and so on. You can generally do this by adding an extra slice move somewhere in the centers stage. Then the final two wings can only have some very simple "slice, flip edge, slice back" solutions, or you could just solve everything at the same time.

6. ### abunickabhiMember

158
21
Jan 9, 2014
Yo
WCA:
2013GHOD01
abunickabhi
good to hear that a feasible solver for 5x5 can be constructed.

7. ### xyzzyMember

777
337
Dec 24, 2015
Yeah, that's something I brought up too, but honestly I'm not sure if solving slice parity is that useful with redux. (Compared to "subgroup descent" methods, as in solvers that go from the full group into smaller subgroups defined by a restricted move set, e.g. mine. You can sort of see what it's doing in the video dwalton76 posted on the first page of the thread.)

On the 555, there's the 9-move parity fix (r U2)5 which can solve 3 wings at once if you spend a bunch of moves to set up the pieces appropriately. It's worse than using 3-cycles (5 moves to solve 2 wings), but not that much worse. Solving parity at the start would probably save only about 2 moves on average. For the last two edges, the parity cases are also only about 3-4 moves longer on average (iirc). (Compare this (non-parity; 10 moves optimal) with this (parity; 12 moves).)

Also, doing L2E/L4E on 555 the same way we do it for speedsolving is actually pretty bad in terms of move count, because slice-flip-unslice costs 7 moves, or 8 if you need to set it up. In contrast, most wing 3-cycles are either 5 or 6 moves, so if you let the unpaired wings be anywhere on the cube instead of just the 2U/2D layers, the move count just magically drops. On the flip side, solving the wings with 3-cycles is not compatible with freeslice, and almost everyone seems to think that freeslice is the best way to do edge pairing on 666 and up. I don't have data on this (yet).

8. ### Herbert KociembaMember

168
40
Nov 29, 2008
I uploaded my 3x3x3 Python solver to https://github.com/hkociemba/RubiksCube-TwophaseSolver now.
For me it was the fun way to learn Python but I would appreciate if anybody with more experience with Python would have a look at the code and give me some suggestions for improvements. Maybe dwalton76 has use of it for the last phase of his NxNxN solver or some other persons who want to build a cube solving robot.

9. ### dwalton76Member

34
18
Jan 2, 2017
I tried it out, this is pretty cool. I haven't had a chance to look at the code yet but just some quick feedback:
• Have you thought about including the tables in the repo so the user doesn't have to build them? If you 'gzip --best' they are only about 40M, thats plenty small enough to check into github.
Code:
[email protected] ~/l/RubiksCube-TwophaseSolver> ls -lh *.gz
-rw-rw-r-- 1 dwalton dwalton  54K Apr 29 11:00 co_classidx.gz
-rw-rw-r-- 1 dwalton dwalton  37K Apr 29 10:59 conj_twist.gz
-rw-rw-r-- 1 dwalton dwalton 1.2M Apr 29 11:00 conj_ud_edges.gz
-rw-rw-r-- 1 dwalton dwalton 2.2K Apr 29 10:58 coord.py.gz
-rw-rw-r-- 1 dwalton dwalton 5.0K Apr 29 11:00 co_rep.gz
-rw-rw-r-- 1 dwalton dwalton  12K Apr 29 11:00 co_sym.gz
-rw-rw-r-- 1 dwalton dwalton 1.7M Apr 29 11:00 fs_classidx.gz
-rw-rw-r-- 1 dwalton dwalton  96K Apr 29 11:00 fs_rep.gz
-rw-rw-r-- 1 dwalton dwalton  14K Apr 29 11:00 fs_sym.gz
-rw-rw-r-- 1 dwalton dwalton 1.3M Apr 29 11:01 move_corners.gz
-rw-rw-r-- 1 dwalton dwalton 308K Apr 29 11:01 move_d_edges.gz
-rw-rw-r-- 1 dwalton dwalton  45K Apr 29 11:00 move_flip.gz
-rw-rw-r-- 1 dwalton dwalton 311K Apr 29 11:01 move_slice_sorted.gz
-rw-rw-r-- 1 dwalton dwalton 1.5K Apr 29 10:58 moves.py.gz
-rw-rw-r-- 1 dwalton dwalton  53K Apr 29 11:00 move_twist.gz
-rw-rw-r-- 1 dwalton dwalton 838K Apr 29 11:01 move_ud_edges.gz
-rw-rw-r-- 1 dwalton dwalton 308K Apr 29 11:01 move_u_edges.gz
-rw-rw-r-- 1 dwalton dwalton  29M Apr 29 11:25 phase1_prun.gz
[email protected] ~/l/RubiksCube-TwophaseSolver>

• For the gui, is there a way to specify the default center colors?
• start_server.py reports 'Error while receiving data. Connection closed' but I do get the correct response
Code:
[email protected][RubiksCube-TwophaseSolver]# curl 'http://localhost:8080/?DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL'
D2 L3 D3 L2 U1 R2 F1 B1 L1 B1 D3 B2 R2 U3 R2 U3 F2 R2 U3 L2 (20f)
</body></html>
[email protected][RubiksCube-TwophaseSolver]#


10. ### Herbert KociembaMember

168
40
Nov 29, 2008
I am not sure if this is works The problem is that the endianess might be different in different operating systems and this could break the program since some tables store information on the bit level. So it is saver to build the tables on the system where the server is running.
No, the gui is intented only as a very simple demonstration how to interact with the server.
You savely can comment out the corresponding print-line in the try-except block in sockets.py if this is irritating.

Last edited: Apr 29, 2017
11. ### xyzzyMember

777
337
Dec 24, 2015
Is there a reason you're using a signed long array instead of, say, an unsigned long or unsigned char array? Using an unsigned type would get rid of some of the weird checks you have for ix%16 == 15, and using char would get rid of endianness concerns.

12. ### Herbert KociembaMember

168
40
Nov 29, 2008
I suppose you address issues in the module pruning.py .
Indeed both issues you address were also part of my considerations and what you propose was exactly what I tried in my original coding attempts.
1. Using char instead for the arrays flipslice_twist_depth3 and corners_ud_edges_depth3: Yes this would be possible. But the generation of the two pruning tables (which take the most time to generate) really was much faster using "long" instead, mainly because it is much faster for the lower depths where the tables are sparsely populated (if not backsearch and idx % 16 == 0 and corners_ud_edges_depth3[idx // 16] == -1...).

2. I know the lines in set_flipslice_twist_depth3 and in set_corners_ud_edges_depth3 look weird but using unsigned long which I tried first simply did not work. If I remember correctly I could not get around problems similar to what happens here:

import array
test = array.array('L', [0] *5)
test[0] = ~(3 << 30)

If you run this code you get an OverflowError: can't convert negative value to unsigned int.
But thanks, I will give the unsigned approach another try, I think this will simplify the code because I now have the extra handling for << 30 also in the signed version!

Last edited: Apr 30, 2017
13. ### xyzzyMember

777
337
Dec 24, 2015
Hm, I knew there had to be a catch somewhere. Would it be better to generate the tables as long (or even long long) and then convert them to char when saving them to disk?

I haven't looked at the code very closely, but I'm assuming you use the corners_ud_edges_depth3[idx // 16] == -1 test to simultaneously check 16 entries at once? That's pretty cool.
Python 3's ~ operator works almost as though we're in the 2-adics. The ~ of any positive number will have "infinitely many" 1s to the left of it, so it'd be treated as a negative number, which Python refuses to implicitly convert to an unsigned int; you need to mask it with 0xFFFFFFFF to get it to be a 32-bit unsigned int.

14. ### mark49152Super ModeratorStaff Member

4,097
2,208
Oct 29, 2012
UK
WCA:
2015RIVE05
mark49152
Or you could solve inner edges like a 4x4 then outers like 5x5.

15. ### Gold CuberMember

119
21
Apr 13, 2017
In a house
WCA:
2017SIMC01
Gold Cuber
that would probably be an easier stratagie but i don't know how to make a cube robot so...

16. ### Herbert KociembaMember

168
40
Nov 29, 2008
That's indeed the reason. I changed to unsigned long again and committed and pushed the changes. Really looks much nicer now. In the moment I do not do the mask you proposed but just make an extra handling for <<30 . But I also will try your approach today. With unsigned long long I am not sure how this performs on 32 bit systems because it extends the native int size. So maybe I better leave it as it is now.

Edit: Used the mask operation you proposed now. Even seems to be a tiny bit faster.

Last edited: Apr 30, 2017
17. ### dwalton76Member

34
18
Jan 2, 2017
@Herbert Kociemba want to announce your 3x3x3 python solver in another thread so we don't end up with two conversations in this one?

18. ### dwalton76Member

34
18
Jan 2, 2017
yep, I ended up doing that for 6x6x6. This also made me realize that I could simplify my 5x5x5 edge pairing code a good deal by using my 4x4x4 edge pairing code to pair all of the outer wings. That eliminates quite a few scenarios for pairing the last two edges 5x5x5, you only have to take care of 1, 5, 6, 7, and 8 from here:

19. ### dwalton76Member

34
18
Jan 2, 2017
VICTORY!! Or something like that

20. ### mark49152Super ModeratorStaff Member

4,097
2,208
Oct 29, 2012
UK
WCA:
2015RIVE05
mark49152
I guess it depends whether there's any advantage to you in reducing slices or phases. If you look at each wing and pair it up with its midge you have a single phase to reduce to the last 2-3 tredges using outer block moves only. (Search AvG edge pairing.)