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

sample51_1.gif

sample51_2.gif

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...
 
Last edited:

AlphaSheep

Member
Joined
Nov 11, 2014
Messages
1,083
Location
Gauteng, South Africa
WCA
2014GRAY03
This is great!

How quickly does the typical move count grow with N?

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

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

Member
Joined
Dec 24, 2015
Messages
2,877
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.
 
Joined
Nov 29, 2008
Messages
214
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).

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

Member
Joined
Apr 25, 2008
Messages
251
What's your procedure for the 3rd phase (finish centers phase)?
 
Joined
Nov 29, 2008
Messages
214
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

Member
Joined
Oct 31, 2008
Messages
301
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.
 
Joined
Nov 29, 2008
Messages
214
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.
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.
sample51_3.gif
 
Joined
Nov 29, 2008
Messages
214
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:
sample51_4.gif
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...
 
Last edited:

abunickabhi

Member
Joined
Jan 9, 2014
Messages
6,687
Location
Yo
WCA
2013GHOD01
YouTube
Visit Channel
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

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