nxnxn cube solver

Discussion in 'Puzzle Theory' started by Herbert Kociemba, Sep 19, 2016.

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!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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: Sep 19, 2016
    Teoidus, Logiqx, AlexMaass and 7 others like this.
  2. spyr0th3dr4g0n

    spyr0th3dr4g0n Member

    148
    1
    Jun 17, 2011
    Dublin, Ireland
    WCA:
    2012HAMM01
    YouTube:
    spyr0th3dr4g0n
    Interesting work, how well does it work for n == 4 or n == 5? What sort of benchmarks do you get?
     
  3. genericcuber666

    genericcuber666 Member

    223
    36
    Aug 5, 2016
  4. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    Let us wait until the solver is fully functional. What it does in the moment is quite trivial for 4x4x4 or 5x5x5.
     
  5. AlphaSheep

    AlphaSheep Member

    983
    441
    Nov 11, 2014
    Gauteng, South Africa
    WCA:
    2014GRAY03
    This is great!

    How quickly does the typical move count grow with N?

    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.
     
  6. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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: Sep 19, 2016
    abunickabhi, Teoidus and AlphaSheep like this.
  7. 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?
     
  8. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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.
     
  9. qqwref

    qqwref Member

    7,830
    27
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    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.
     
    abunickabhi likes this.
  10. xyzzy

    xyzzy Member

    654
    261
    Dec 24, 2015
    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.
     
  11. AlphaSheep

    AlphaSheep Member

    983
    441
    Nov 11, 2014
    Gauteng, South Africa
    WCA:
    2014GRAY03
    That works out to the number of centre facelets + 2... That's fascinating.
     
  12. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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).

    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.
     
    abunickabhi likes this.
  13. ch_ts

    ch_ts Member

    181
    15
    Apr 25, 2008
    What's your procedure for the 3rd phase (finish centers phase)?
     
  14. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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.
     
  15. rokicki

    rokicki Member

    254
    3
    Oct 31, 2008
    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.
     
    abunickabhi likes this.
  16. campos20

    campos20 Member

    23
    11
    Dec 26, 2015
    Brazil, MG
    WCA:
    2015CAMP17
    YouTube:
    user/afonsocampos20
    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?
     
  17. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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.
    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
     
    Teoidus and Logiqx like this.
  18. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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: Oct 2, 2016
  19. abunickabhi

    abunickabhi Member

    147
    15
    Jan 9, 2014
    Yo
    WCA:
    2013GHOD01
    YouTube:
    abunickabhi
    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.
     
  20. dwalton76

    dwalton76 Member

    31
    12
    Jan 2, 2017
    @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.
     

Share This Page