• 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!

nxnxn cube solver

Joined
Nov 29, 2008
Messages
214
Hi guys, after 6 years (!) I returned to my unfinished project and want to finish it now. It really was no fun trying to understand the code I wrote 6 years ago. At least I am now back at the point where I left the project, with some improvements:
1. The source code is on GitHub https://github.com/hkociemba/RubikNxNxNSolver
2. It is written with the free Lazarus IDE which is available for Windows and Linux. So at least in principle it should be possible to make it work on both platforms.
3. I could combine one of the steps to a single step which reduces the number of moves.

I now do the following steps:
Phase 1: U Centers and D centers to the U face or D face.
Phase 2: F Centers and B centers to the F face or B face.
The R centers and L centers now are automatically in the R or L face.
Phase 3: Simultanuously put the R, L, F and B centers into their correct faces.
Phase 4: Put the U and D centers into their correct faces.
Now all centers are solved.
Each phase has three substeps. Solve the Plus-centers, then all center orbits (x,y) and (y,x) with x<y<N/2 simultanuously and finally the X-centers.
In the Plus center solving substep of phase 2 also the parity of all edge orbits gets fixed. Parity of the edges does not change any more for any subsequent steps so the still missing edge pairing part in Phase 5 should be possible with 3 cycles for example. I really hope I will get a result within the next weeks.
The centers of a 101x101x101 cube were solved within less than 70,000 moves within a couple of hours, the data also is in the Github files (testcube101_Ph1Solve.txt etc.)
In the task manager the program showed a memory usage of about 14 GB, so I hope 16 GB RAM are enough to run the program (my machine has 64 GB of RAM).
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Wow, under a move per cubie! That's a lot better than the other huge-cube solvers I'm aware of (but I think they generally use a lot less memory and run a lot faster). Can you give a move-count breakdown for the various phases and subphases?
 
  • Like
Reactions: qwr

qwr

Member
Joined
Jul 24, 2019
Messages
3,371
YouTube
Visit Channel
In the task manager the program showed a memory usage of about 14 GB, so I hope 16 GB RAM are enough to run the program (my machine has 64 GB of RAM).
How does memory usage compare with c++? Pascal is compiled like java right? (the only Pascal code I've seen is from academics a few decades ago)
I would think C++ and non-garbage-collecting languages would be much better at memory management, especially comparing the memory requirements of a python list versus a c++ vector, but I don't have any hare evidence of that.
 

ender9994

Member
Joined
Nov 12, 2008
Messages
610
Location
Hopewell NJ
WCA
2008GROM01
YouTube
Visit Channel
How does memory usage compare with c++? Pascal is compiled like java right? (the only Pascal code I've seen is from academics a few decades ago)
I would think C++ and non-garbage-collecting languages would be much better at memory management, especially comparing the memory requirements of a python list versus a c++ vector, but I don't have any hare evidence of that.
Pascal is compiled, and there is no interpreter like with Java. pascal and C are pretty similar, and I am assuming object pascal and c++ are also similar.

I should say, I have essentially zero experience with pascal, though I do a large amount of work in C++. I am not sure what flavor of pascal he is using, haven't gotten around to looking at the code yet.

That being said, I doubt c++ would offer anything huge in terms of performance
 
Joined
Nov 29, 2008
Messages
214
Wow, under a move per cubie! That's a lot better than the other huge-cube solvers I'm aware of (but I think they generally use a lot less memory and run a lot faster). Can you give a move-count breakdown for the various phases and subphases?
Ok, the 101x101x101 has 58800 centers in 2450 orbits, so it is about 28.5 moves for each 24-center orbit. To do the statistics, I added some code and now rerun the computation which will take a couple of hours . In the Github files I did not fix the edge parity in phase 2 yet, but this will only increase the total move count by about 50 moves I think.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
That's a lot better than the other huge-cube solvers I'm aware of (but I think they generally use a lot less memory and run a lot faster).
Mine (*) is probably much slower, but also seems to be a bit more efficient (~0.96 moves OBTM per oblique centre, or ~23.1 moves per orbit).

stats from a 25^3 solve

n = 12
size = 2n+1

macrophase 1: solving UD centres

phase 1A: solve (composite) t-centres and x-centres
110 / 11 = 10.00 moves
executed n-1 times

phase 1B: oblique pairing
(811-110) / 55 = 12.75 moves
executed (n-1)(n-2)/2 times

macrophase 2: solving RL, FB centres + parity

phase 2A: solve (composite) t-centres and x-centres + parity
101 / 11 = 9.18 moves
executed n-1 times

phase 2B: oblique pairing
(585-101) / 55 = 8.80 moves
executed (n-1)(n-2)/2 times

macrophase 3: setting up centres

1357 / 55 = 24.67 moves
executed (n-1)(n-2)/2 times

macrophase 4: solving like 555

445 / 11 = 40.45 moves
executed n-1 times

macrophase 5: solving like 333

22 moves

(*) Append a lowercase letter to the URL to get the correct decryption key. The code is kinda bad and I'm embarrassed about it.
 

qwr

Member
Joined
Jul 24, 2019
Messages
3,371
YouTube
Visit Channel
(*) Append a lowercase letter to the URL to get the correct decryption key. The code is kinda bad and I'm embarrassed about it.
I don't know what this means
Anyway you should'nt be embarrassed about code quality for a hobby project. It can't be nearly as bad as cstimer which borders on indecipherable. It's much more beneficial to the community to start with messy code than no code at all.
 
Joined
Nov 29, 2008
Messages
214
I rerun the code for the 101x101x101 and here is some more detailed statistics:

+cross phase1: 372 moves, 7.59 moves/orbit on average
(x,y),(y,x) orbits phase1: 17688 moves, 15.04 moves/orbit on average
xcross phase1: 431 moves, 8.80 moves/orbit on average

+cross phase 2: 341 moves, 6.96 moves/orbit on average. In this subphase also the edge parities get fixed.
(x,y),(y,x) orbits phase 2: 15907 moves, 6.76 moves/orbit on average
xcross phase 2: 395 moves, 8,06 moves/orbit on average

+cross phase 3: 246 moves, 5,02 moves/orbit on average
(x,y),(y,x) orbits phase 3: 19727 moves, 8.39 moves/orbit on average
xcross phase 3: 486 moves, 9.92 moves/orbit on average.

+cross phase 4: 192 moves, 3.92 moves/orbit on average
(x,y),(y,x) orbits phase 4: 13655 moves, 5.81 moves/orbit on average
x-cross phase 4: 337 moves, 6.88 moves/orbit on average

Total +cross: 1151 moves, 23.5 moves/orbit
Total (x,y),(y,x) orbits: 66977 moves, 28.5 moves/orbit
Total x-cross: 1649 moves, 33.7 moves/orbit

Total: 69777 moves for 2450 center orbits, 28.5 moves/orbit on average.
 

ch_ts

Member
Joined
Apr 25, 2008
Messages
251
I don't know what this means
Anyway you should'nt be embarrassed about code quality for a hobby project. It can't be nearly as bad as cstimer which borders on indecipherable. It's much more beneficial to the community to start with messy code than no code at all.

It means you should add a letter to the provided URL to get the correct URL and then you can download the code

Add 'o'
 
Joined
Nov 29, 2008
Messages
214
For the remaining step - edge pairing - I decided to use the freeslice method which seems to be superiour compared to using three-cycles of edges for the first substep. The first substep is to pair 8 edges and store them in the U and D face. To pair the 8(N-3) edge pieces for odd N I need less than 4 moves/edge for N=7. Surprisingly this average drops severly for large cubes.
So the edge paring for the 8 edges of the N=101 cube took only 1125 moves, which is 1.43 moves/edge. There are many edges pieces which can be sliced into their "home edge" with one move.

To pair the remaining 4(N-3) edge pieces one method would be using three-cycles, which till take longer of course, xyzzy says 9 moves/three cycle. I am not sure of the second part of the usual freeslice method would beat this.
 
Last edited:
Top