# nxnxn cube solver



## Herbert Kociemba (Sep 19, 2016)

I am currently working on a general NxNxN cube solver for large N. For large N the main work is to fix the 6*(N-2)^2 centerpieces so I will concentrate on fixing the centers. I also ignore even N in the moment and hence I assume that N is odd for the time being.

A corner piece has three visible facelets, an edge piece has two visible facelets and a centerpiece has only one visible facelet. When talking about the centers I will use the terms "facelet" and "centerpiece" interchangeable.

Using an appropriate coordinate system for each of the 6 faces with coordinates ranging from (0,0) to (N-1,N-1) a facelet at position (x,y) will go to a position (y,N-1-x), (N-1-x,N-1-y) or (N-1-y,x) on the same face when applying a face move and on a different face when applying a slice move. This will lead to 24 different positions of a facelet, except in the case x=y=(N-1)/2 where we only have 6 different positions.
For center facelets the 24 different positions correspond to 24 different centerpieces which constitute the center cluster C(x,y). If we assume without loss of generality 1<=x,y<=(N-1)/2 each center cluster is uniquely determined by x and y.


In the first step we fix all center clusters C(x,y) such that the U and D centers are in the U and D face.
First we solve the "+cross" clusters C(x,(N-1)/2), 1<=x< (N-1)/2. Since there are only Binomial[24,8] different positions, this is done in almost no time.
For x<>y we solve C(x,y) and C(y,x) simultaneously. This is the hardest part because there are Binomial(24,8)^2 different states and there is the additional restriction that the other clusters may not be affected. Usually it takes something from a few seconds to several minutes to solve a single pair C(x,y) and C(y,x).
At the end we solve the "x-cross" clusters C(x,x), 1<=x< (N-1)/2. Again there are only Binomial[24,8] states and the solution can be computed almost instantaneously,

The two pictures show an example for N=51. It took 4211 single face or slice moves within about 4 hours to fix the 4800 U and D facelets in 600 clusters.



Spoiler









In the second step we put the R and L centers into the R and L faces using only 180 degree turns for the R, L, F and B face and slice moves so that the U and D faces will not be destroyed again. More to come...


----------



## spyr0th3dr4g0n (Sep 19, 2016)

Interesting work, how well does it work for n == 4 or n == 5? What sort of benchmarks do you get?


----------



## genericcuber666 (Sep 19, 2016)

cool can it do 2x2


----------



## Herbert Kociemba (Sep 19, 2016)

spyr0th3dr4g0n said:


> Interesting work, how well does it work for n == 4 or n == 5? What sort of benchmarks do you get?


Let us wait until the solver is fully functional. What it does in the moment is quite trivial for 4x4x4 or 5x5x5.


----------



## AlphaSheep (Sep 19, 2016)

This is great!

How quickly does the typical move count grow with N?



genericcuber666 said:


> cool can it do 2x2


What is described in this thread is a means of solving all U and D centre pieces to the U and D faces, so if you look at the images in the spoiler, you'd realise that's not particularly useful for solving a 2x2. Writing a solver for the corners of an NxNxN is far far easier than the centres, which is why Herbert Kociemba is working on the centres first. Presumably corners will be solved in a later phase or phases.


----------



## Herbert Kociemba (Sep 19, 2016)

AlphaSheep said:


> How quickly does the typical move count grow with N?


The average move count to solve an C(x,y)|C(y,x) cluster pair with x<>y for the phase I described is less than 16 moves for a *single* cluster pair. The way the algorithm is programmed this average drops when many clusters are solved. Since there are (N-3)(N-5)/8 such pairs this part takes less than (N-3)(N-5)*2 moves on average. The number of xcross and +cross clusters is (N-3)/2 each and this takes an average of less than (N-3)*8 moves for both. So on average (and for N > some No presumably for all cases) you need less than 2(N-3)(N-1) moves for this phase.


----------



## shadowslice e (Sep 19, 2016)

So for this will you be developing an n-phase algorithm? If so how many do you expect to use and what would the phases be?


----------



## Herbert Kociemba (Sep 19, 2016)

shadowslice e said:


> If so how many do you expect to use and what would the phases be?


I hope that these 5 phases will work:
1. U,D centers to U,D faces
2. R,L centers to R,L faces, implies also F,B centers to F, B faces
3. Solve centers
4. Pair edges
5. Finish solve like 3x3x3

Currently I have I clear idea how to do this except for phase 4.


----------



## qqwref (Sep 20, 2016)

I was expecting an unsolved thread from the title, but I'm very pleasantly surprised. This is extremely cool stuff and I'm excited to see how it goes forward.

When you finish I'd be interested to know how this compares to other NxNxN algorithms. I think IAssemble or one of his friends has a pretty good NxNxN solver that solves the centers in orbits starting from the middle and going outward, using some kind of lookup table magic. As a non-computer benchmark, I did a 20x20x20 FMC in 3643 slice moves, and my 128x128x128 took 157318 moves. My method scales with O(N^2) for an NxNxN, as I expect yours does.


----------



## xyzzy (Sep 20, 2016)

Herbert Kociemba said:


> 4. Pair edges
> 
> Currently I have I clear idea how to do this except for phase 4.



Phase 4 would be the easiest of the reduction phases, I think. After all, not counting parity algs, you can always do a 3-cycle on the wings in 9 moves, and the highest number of 3-cycles you need to decompose an even permutation on 24 elements is 12, so solving all the wings (in the sense of matching them to their respective midges for odd n, or in the sense of matching them to each other for even n) takes 108⌊n/2⌋=O(n) moves, and this is probably going to be dwarfed by the O(n^2) moves for the centres.

In practice I get move counts of around 48 for one wing orbit just by choosing the shortest 3-cycle (plus lookahead to try to avoid the nine-move cases) and incrementally solving a few wings at a time, so the upper bound above is pretty loose. I imagine that on cubes larger than 5x5x5 you can work on the wings of multiple orbits simultaneously to cut the move count down even further, rather than solving them orbit by orbit.

Alternatively, freeslice also looks like an attractive option for dealing with the edges.

Maybe you can deal with parity while you solve the outer orbits of centre pieces in phase 2, but this saves only O(n) moves and might not be worth the effort.


----------



## AlphaSheep (Sep 20, 2016)

Herbert Kociemba said:


> So on average (and for N > some No presumably for all cases) you need less than 2(N-3)(N-1) moves for this phase.


That works out to the number of centre facelets + 2... That's fascinating.


----------



## Herbert Kociemba (Sep 20, 2016)

qqwref said:


> My method scales with O(N^2) for an NxNxN, as I expect yours does.


Yes, surely my method will be O(N^2) too. Eric Demaine showed in his paper http://erikdemaine.org/papers/Rubik_ESA2011/paper.pdf that it is possible in O(N^2/Log(N)) and that this is the best you can do. It is a really beautiful result but for cubes of any practical size N it is useless since it relies on the fact that you solve bunchs of center clusters C(x,y) which have *all the same configuration *in parallel. Since there are 24!/(4!)^6 = 3246670537110000 different configuration even for N=1000 the probability, that you have at least two clusters with the same configuration is less than 10^-5 (birthday problem).



xyzzy said:


> After all, not counting parity algs, you can always do a 3-cycle on the wings in 9 moves, and the highest number of 3-cycles you need to decompose an even permutation on 24 elements is 12, so solving all the wings (in the sense of matching them to their respective midges for odd n, or in the sense of matching them to each other for even n) takes 108⌊n/2⌋=O(n) moves, and this is probably going to be dwarfed by the O(n^2) moves for the centres.


You are right. Doing 3-cycles is definitely a good way if N is sufficently large. Maybe there is something else which also scales good for smaller N.


----------



## ch_ts (Sep 20, 2016)

What's your procedure for the 3rd phase (finish centers phase)?


----------



## Herbert Kociemba (Sep 20, 2016)

ch_ts said:


> What's your procedure for the 3rd phase (finish centers phase)?


I will try something similar to what I described for the first phase but now using only square moves. I do not know if this will work since the search space has considerably more states.


----------



## rokicki (Sep 20, 2016)

It would be fun to have a long-running contest on solving huge cubes (say, a variety of sizes, including 4, 9, 16, 25, 36, 49, 64, 81, 100, just to pick some values). We'll need an agreed-on set of random scrambles somehow, perhaps generated by some standard pseudo-random number generator. Consider it a platform for trying different ideas.


----------



## campos20 (Sep 23, 2016)

Herbert Kociemba said:


> (...) More to come...



Great work! Out of curiosity, in what language are you programming? Are you publishing parcial results in an article or just when you finish it?


----------



## Herbert Kociemba (Sep 23, 2016)

campos20 said:


> Great work! Out of curiosity, in what language are you programming? Are you publishing parcial results in an article or just when you finish it?


I program in Delphi for the simple reason that it is very easy to implement some graphical user interface and I am used to it.
I yet have not plan to publish any results in more detail yet. Maybe some better ideas evolve in the discussion.


rokicki said:


> It would be fun to have a long-running contest on solving huge cubes (say, a variety of sizes, including 4, 9, 16, 25, 36, 49, 64, 81, 100, just to pick some values).


In the moment I personally prefer just to make my solver fully working. In a second step it would be great of course to discuss other approaches and share ideas to improve the solving algorithms.

Meanwhile a finished phase 2 without encountering any problems. I took the same approach: Solving the +cross-Clusters (max 9 moves/cluster), solving all pairs C(x,y)|C(y,x) with x<>y (max. 19 moves/cluster pair) and solving the xcross clusters(max 11 moves/cluster). Since it is possible to use pruning tables which give the exact distance to the goalstate for each of the clustertypes, the search time is almost negligible (<1s for the example). This part took 3809 moves which is in the same order as the number of moves in phase 1.


Spoiler


----------



## Herbert Kociemba (Oct 2, 2016)

Phase 3 is working now. It took additional 9462 moves to sort the colors of the opposite faces. and the cube now looks like this:


Spoiler






I'm not completely satisfied with the result and there is still room for improvements here.

In principle I did it in the same way as in the phases 1 and 2:
solve the +cross-clusters C(x,(N-1)/2), the C(x,y)|C(y,x),x<>y cluster pairs and finally the xcross-clusters C(x,x).
But I solved the C(x,y)|C(y,x) cluster pairs in three substeps: First solve the UD face colors of all cluster pairs, then the RL face colors and finally the FB face colors. This is computationally quite inxepensive with the advantage that the complete process is finished within a couple of seconds.
But it would save a lot of moves it all the faces of a cluster pair in phase 3 could be solved in one step. The search space is quite large in this case and it is not clear if this computation is manageable in a reasonable time.
The next step well be the edge pairing. I think I will try a few different things here. This will take some time...


----------



## abunickabhi (Apr 27, 2017)

It is good to find the center cluster algorithms and techniques being generated.
I plan to develop to better method to solve 4bld and 5bld centers since the current method to solve it as 3 cycles is very tedious.


----------



## dwalton76 (Jul 25, 2017)

Herbert Kociemba said:


> The next step well be the edge pairing. I think I will try a few different things here. This will take some time...



@Herbert Kociemba I've been working on making my solver work for NxNxN, my test cube is 14x14x14. I have not finished solving centers yet but decided to skip ahead to pair the edges since I had an idea in my head. For an even cube I reduce the inner most edges to a 4x4x4 cube and use my 4x4x4 solve to pair those edges. From there I can pair the next orbit of edges by reducing them to a 5x5x5 cube and use my 5x5x5 solver to pair those edges...I just repeat this for each orbit of edges, at that point all edges are paired. So basically start with the inside orbit of edges and work your way out.

Nothing ground breaking but figured I would share what I did here.


----------



## Herbert Kociemba (Sep 18, 2022)

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 (Sep 19, 2022)

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?


----------



## qwr (Sep 20, 2022)

Herbert Kociemba said:


> 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 (Sep 20, 2022)

qwr said:


> 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


----------



## qwr (Sep 20, 2022)

ender9994 said:


> That being said, I doubt c++ would offer anything huge in terms of performance


it would if pascal doesn't have as good of a compiler as c++, in particular one that vectorizes well (order of magnitude faster)


----------



## Herbert Kociemba (Sep 20, 2022)

rokicki said:


> 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 (Sep 20, 2022)

rokicki said:


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



Spoiler: some old notes



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 (Sep 20, 2022)

xyzzy said:


> (*) 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.


----------



## Herbert Kociemba (Sep 21, 2022)

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 (Sep 21, 2022)

qwr said:


> 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



Spoiler



Add 'o'


----------



## Herbert Kociemba (Sep 27, 2022)

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.


----------

