• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

5x5x5, 6x6x6, 7x7x7 or NxNxN solvers

dwalton76

Member
Joined
Jan 2, 2017
Messages
71
YouTube
Visit Channel
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
i-DwVXHLC-M.png

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
 
Joined
Nov 29, 2008
Messages
214
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.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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.

4x4x4 solver is down to 66 moves on average
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.

5x5x5 solver is down to 128 moves [...] 45 steps to pair the first 22 wings and 27 steps to pair the final two...there are some savings to be had here.
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.
 

abunickabhi

Member
Joined
Jan 9, 2014
Messages
6,687
Location
Yo
WCA
2013GHOD01
YouTube
Visit Channel
I am working on a lego robot that can solve various size rubiks cube, I have it working for 2x2x2, 3x3x3 and 4x4x4. The robot is large enough to handle a 5x5x5, 6x6x6 and mini 7x7x7 but I am struggling to find solvers for those sizes. I found various threads about NxNxN solvers but haven't found one that produces a low enough number of moves for me to feasibly do with a robot. https://github.com/aditya-r-m/Rubiks-Cube for instance appears to work but produces 700+ moves to solve a reasonably scrambled 5X5X5, that would take my robot about 35 minutes execute.

Any recomendations on solvers for these sizes (or NxNxN)? Ideally it would be something I can run from the command line and would be lightweight enough to run on a raspberry Pi3 but I realize that may be wishful thinking.
good to hear that a feasible solver for 5x5 can be constructed.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
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.

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).
 
Joined
Nov 29, 2008
Messages
214
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.
client.jpg
 

dwalton76

Member
Joined
Jan 2, 2017
Messages
71
YouTube
Visit Channel

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:
dwalton@laptop ~/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
dwalton@laptop ~/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:
dwalton@laptop[RubiksCube-TwophaseSolver]# curl 'http://localhost:8080/?DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL'
<html><head><title>Answer from Cubesolver</title></head><body>
D2 L3 D3 L2 U1 R2 F1 B1 L1 B1 D3 B2 R2 U3 R2 U3 F2 R2 U3 L2 (20f)
</body></html>
dwalton@laptop[RubiksCube-TwophaseSolver]#
 
Joined
Nov 29, 2008
Messages
214
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.
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.
For the gui, is there a way to specify the default center colors?
No, the gui is intented only as a very simple demonstration how to interact with the server.
start_server.py reports 'Error while receiving data. Connection closed' but I do get the correct response
You savely can comment out the corresponding print-line in the try-except block in sockets.py if this is irritating.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
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.

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.
 
Joined
Nov 29, 2008
Messages
214
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.

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:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
ut 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

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.
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 did 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.

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.
 
Joined
Nov 29, 2008
Messages
214
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.

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:

dwalton76

Member
Joined
Jan 2, 2017
Messages
71
YouTube
Visit Channel
Or you could solve inner edges like a 4x4 then outers like 5x5.

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:
wsTqj.png
 

mark49152

Premium Member
Joined
Oct 29, 2012
Messages
4,719
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
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.
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.)
 
Top