1. 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 30,000+ people from around the world today!
    Dismiss Notice

5x5x5, 6x6x6, 7x7x7 or NxNxN solvers

Discussion in 'Software Area' started by dwalton76, Jan 16, 2017.

  1. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    There is a bug in the screenshot, near the bottom it should read "110 steps to group edges", not 68 steps.
     
  2. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    I found this post on AvG edge pairing
    https://www.speedsolving.com/forum/threads/arnauds-5x5x5-edge-pairing-method-examples.1447/

    and loaded up the 57 move scramble. I am able to pair the edges in 72 moves so what I am doing seems pretty comparable in terms of the move count (his 'expert' number was 73 moves). I do:
    • pair the outside wings via 4x4x4 edge pairing
    • attempt to pair 3 edges on a Uw slice and pair three more on the Uw' slice back...sometimes the stars align and I can pair 4 at once on either the slice forward or slice back.
    • pair all remaining edges via https://i.imgur.com/wsTqj.png No 1, 5, 6, 7, or 8
     
    abunickabhi likes this.
  3. xyzzy

    xyzzy Member

    1,124
    578
    Dec 24, 2015
    AvG uses a few more moves than freeslice (as implemented on a human being, so no backtracking or deep lookahead), in exchange for having less stuff to keep track of.

    Here's two different human solves of the same scramble: [1] [2]

    First one is freeslice (67 moves), second one is freestyle chain pairing (57 moves).

    Solving the wings then matching them to the midges is necessarily significantly less efficient than most other methods that don't do that (freeslice, chain pairing, 3-cycles), although it certainly is a much simpler algorithm if we have a 4×4×4 edge pairing black box to exploit.
     
    Last edited: May 1, 2017
    abunickabhi likes this.
  4. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    57 moves is impressive
     
  5. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    First solve of a 6x6x6. This is only the last few moves, there were 239 moves total, it took the robot about 10-12 minutes.
     
  6. Malkom

    Malkom Member

    520
    162
    May 22, 2016
    Sweden
    WCA:
    2016ANDE17
    YouTube:
    channel/UCSCZ2BsupnT5FoxOMNOf_kQ
    it looks like 4 edges are swapped in the back, is it just the lighting?
     
    Dr_Detonation likes this.
  7. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    They are, the code that crunches the RGB values to figure out the colors got red and orange backwards on two squares. Red vs orange has been difficult I have some more work to do there. So not 100% solved but "solved" in terms of the solving algorithm and mechanics of the robot working.
     
  8. Dr_Detonation

    Dr_Detonation Member

    134
    63
    Apr 26, 2017
    Over da Rainbow
    WCA:
    2017ECKS02
    That is awesome. Coolest thing I've seen in my life. Or at least this week
     
    abunickabhi likes this.
  9. xyzzy

    xyzzy Member

    1,124
    578
    Dec 24, 2015
    Would it work better with, say, a stickerless cube? (Or worse, if the detection algorithm needs to have a border around each facelet?)
     
  10. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    So there are two phases at play here
    1. Take photos of all six sides, find all of the facelets, get the mean (red, green, blue) values of each facelet. Having clear borders around the facelets def makes them easier to find here but I have it working even if there are white facelets separated by a white border. Sticker vs stickerless I don't think would matter much. Example of white on white: [​IMG]
    2. Take the RGB values for each facelet and ID each facelet as U,L,F,R,B, or D
    Phase 2 is where the red vs. orange confusion is. The way this part works is
    • ID "anchor" facelets which will act as our color point of reference for each side. For odd cubes this is easy we just take the middle facelet of each side. For even cubes we take a corner to get the first three anchors then we find the other corner that has the greatest "color distance" from our first corner, that gives us the other three anchors.
    • "color distance" is calculated by https://en.wikipedia.org/wiki/Color_difference#CIEDE2000
    • Build a list of the color combos we need for corners
    • Build lists of the color combos we need for each orbit of edges
    • Build lists of the colors we need for the various types of center facelets
    So for corners say we know we need a Green, White, Red corner, we look at all of the corner facelets and find the corner that matches the Green, White, Red anchor facelet colors with the smallest color distance. We do this same basic thing for all of the corners, then all of the edges, etc.
     
    abunickabhi likes this.
  11. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
  12. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    [​IMG]

    Can now solve a 7x7x7!!!
     
    ch_ts and sqAree like this.
  13. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    Misc update
    • For 5x5x5 edge pairing I am no longer starting out by using 4x4x4 edge pairing to pair all of the outside edges. This dropped the average number of moves for pairing 5x5x5 edges by about 20 moves.
    • I had an IDA bug that led me to building my lookup tables much larger than they needed to be. With that IDA bug fixed all of my lookup tables are now small enough to include in the repo on github. The repo is about 700M though so the git clone takes a few minutes and takes a bit of RAM. This is big news because now anyone can just git clone the repo and use the solver, they no longer need to download massive tables from dropbox.
    • Lots of performance improvements
      • 4x4x4 takes ~200ms to solve
      • 5x5x5 about 5s
      • 6x6x6 about 7s
      • 7x7x7 about 7s
    • Move counts are down
      • 4x4x4 averages 65 moves
      • 5x5x5 averages 119 moves
      • 6x6x6 averages 214 moves
      • 7x7x7 averages 304 moves
    • I've started working on NxNxN even support by trying to solve a 14x14x14...not working yet
    • A few other people have started using the solver, filing bugs, etc
     
    abunickabhi likes this.
  14. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    Major milestone today, I have NxNxN working!! :)

    14x14x14
    [​IMG]
    [​IMG]


    15x15x15
    [​IMG]

    [​IMG]
     
  15. ruwix

    ruwix Member

    89
    22
    Jun 3, 2012
    Oxford, UK
    YouTube:
    modusbeke
  16. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    That would be cool :) Let me know if you need any changes made to make it easier to incorporate into your site.
     
    abunickabhi likes this.
  17. ruwix

    ruwix Member

    89
    22
    Jun 3, 2012
    Oxford, UK
    YouTube:
    modusbeke
    Could you please provide a PHP or JavaScript function that takes the scrambled fields as input and returns the rotations? I will take care of the rest.
     
  18. dwalton76

    dwalton76 Member

    37
    37
    Jan 2, 2017
    I think the best thing to do would be to have php do a
    shell_exec() call to run rubiks-cube-solver.py. You pass rubiks-cube-solver.py the state of the cube via a "--state" arg and it prints out the solution.
     
  19. abunickabhi

    abunickabhi Member

    253
    46
    Jan 9, 2014
    Yo
    WCA:
    2013GHOD01
    YouTube:
    abunickabhi
    Great work in tracking the colours of big cubes.
    I have started out learning image processing in my coursework, and using color distance is great.
    The natural approach would be image segmentation , but then building the list of color combos for the various types of pieces will be lengthy.
     

Share This Page