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

Announcing: New 4x4x4 Brute Force Solver

Status
Not open for further replies.

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
I believe Clément Gallet had once made an optimal solver, good enough to solve dedge flip. I also several years ago, hacked up an optimal solver of limited use (fairly limited search depth in a reasonable amount of time) and no way to enter a scramble or position to be solved. (I needed to edit/recompile the program to specify the scramble and/or what moves are allowed.)

There are a few multi-phase solvers that do not generate optimal solutions. C.W. Tsai had 7- and 8-phase solvers (http://www.cubing.net/software/). I have a 5-phase solver (http://www.speedsolving.com/forum/showthread.php?18615-Five-Step-4x4x4-Solver). And of course the WCA scramble program uses an internal multi-phase solver. I believe it uses 3 phases to reduce to a pseudo-3x3x3, and then invokes a 2-phase 3x3x3 solver.

I have also made custom solvers for optimally changing OLL parity while preserving reduction. I used both depth-first search and meet-in-the-middle breadth-first search approaches. These programs did not need to use full 4x4x4 state information. The meet-in-the-middle solver used a big hash table to store the positions. Because the two trees were symmetrically related, I only actually had to build (and store) one tree. I discussed the results in this thread: http://www.speedsolving.com/forum/s...e-a-shorter-alg-that-doesn-t-preserve-corners

I was amazed at what I saw. Thank you!

And, since it is against the 10 commandments to make a new post, God forbid, here is a dump of moves actually pruned during the search. I think this covers most of the bases that were discussed earlier, but my game tree is not nearly as trimmed as has been suggested. Anybody see anything obvious that I am missing?

Code:
 U D' U 
 U D' U- 
 U D' U2 
 U D' d' U 
 U D' d' U- 
 U D' d' U2 
 U D' d U 
 U D' d U- 
 U D' d U2 
 U D' d2 U 
 U D' d2 U- 
 U D' d2 U2 
 U D U 
 U D U- 
 U D U2 
 U D d' U 
 U D d' U- 
 U D d' U2 
 U D d U 
 U D d U- 
 U D d U2 
 U D d2 U 
 U D d2 U- 
 U D d2 U2 
 U D2 U 
 U D2 U- 
 U D2 U2 
 U D2 d' U 
 U D2 d' U- 
 U D2 d' U2 
 U D2 d U 
 U D2 d U- 
 U D2 d U2 
 U D2 d2 U 
 U D2 d2 U- 
 U D2 d2 U2 
 U d' U 
 U d' U- 
 U d' U2 
 U d' D' U 
 U d' D' U- 
 U d' D' U2 
 U d' D U 
 U d' D U- 
 U d' D U2 
 U d' D2 U 
 U d' D2 U- 
 U d' D2 U2 
 U d U 
 U d U- 
 U d U2 
 U d D' U 
 U d D' U- 
 U d D' U2 
 U d D U 
 U d D U- 
 U d D U2 
 U d D2 U 
 U d D2 U- 
 U d D2 U2 
 U d2 U 
 U d2 U- 
 U d2 U2 
 U d2 D' U 
 U d2 D' U- 
 U d2 D' U2 
 U d2 D U 
 U d2 D U- 
 U d2 D U2 
 U d2 D2 U 
 U d2 D2 U- 
 U d2 D2 U2 
 U- D' U 
 U- D' U- 
 U- D' U2 
 U- D' d' U 
 U- D' d' U- 
 U- D' d' U2 
 U- D' d U 
 U- D' d U- 
 U- D' d U2 
 U- D' d2 U 
 U- D' d2 U- 
 U- D' d2 U2 
 U- D U 
 U- D U- 
 U- D U2 
 U- D d' U 
 U- D d' U- 
 U- D d' U2 
 U- D d U 
 U- D d U- 
 U- D d U2 
 U- D d2 U 
 U- D d2 U- 
 U- D d2 U2 
 U- D2 U 
 U- D2 U- 
 U- D2 U2 
 U- D2 d' U 
 U- D2 d' U- 
 U- D2 d' U2 
 U- D2 d U 
 U- D2 d U- 
 U- D2 d U2 
 U- D2 d2 U 
 U- D2 d2 U- 
 U- D2 d2 U2 
 U- d' U 
 U- d' U- 
 U- d' U2 
 U- d' D' U 
 U- d' D' U- 
 U- d' D' U2 
 U- d' D U 
 U- d' D U- 
 U- d' D U2 
 U- d' D2 U 
 U- d' D2 U- 
 U- d' D2 U2 
 U- d U 
 U- d U- 
 U- d U2 
 U- d D' U 
 U- d D' U- 
 U- d D' U2 
 U- d D U 
 U- d D U- 
 U- d D U2 
 U- d D2 U 
 U- d D2 U- 
 U- d D2 U2 
 U- d2 U 
 U- d2 U- 
 U- d2 U2 
 U- d2 D' U 
 U- d2 D' U- 
 U- d2 D' U2 
 U- d2 D U 
 U- d2 D U- 
 U- d2 D U2 
 U- d2 D2 U 
 U- d2 D2 U- 
 U- d2 D2 U2 
 U2 D' U 
 U2 D' U- 
 U2 D' U2 
 U2 D' d' U 
 U2 D' d' U- 
 U2 D' d' U2 
 U2 D' d U 
 U2 D' d U- 
 U2 D' d U2 
 U2 D' d2 U 
 U2 D' d2 U- 
 U2 D' d2 U2 
 U2 D U 
 U2 D U- 
 U2 D U2 
 U2 D d' U 
 U2 D d' U- 
 U2 D d' U2 
 U2 D d U 
 U2 D d U- 
 U2 D d U2 
 U2 D d2 U 
 U2 D d2 U- 
 U2 D d2 U2 
 U2 D2 U 
 U2 D2 U- 
 U2 D2 U2 
 U2 D2 d' U 
 U2 D2 d' U- 
 U2 D2 d' U2 
 U2 D2 d U 
 U2 D2 d U- 
 U2 D2 d U2 
 U2 D2 d2 U 
 U2 D2 d2 U- 
 U2 D2 d2 U2 
 U2 d' U 
 U2 d' U- 
 U2 d' U2 
 U2 d' D' U 
 U2 d' D' U- 
 U2 d' D' U2 
 U2 d' D U 
 U2 d' D U- 
 U2 d' D U2 
 U2 d' D2 U 
 U2 d' D2 U- 
 U2 d' D2 U2 
 U2 d U 
 U2 d U- 
 U2 d U2 
 U2 d D' U 
 U2 d D' U- 
 U2 d D' U2 
 U2 d D U 
 U2 d D U- 
 U2 d D U2 
 U2 d D2 U 
 U2 d D2 U- 
 U2 d D2 U2 
 U2 d2 U 
 U2 d2 U- 
 U2 d2 U2 
 U2 d2 D' U 
 U2 d2 D' U- 
 U2 d2 D' U2 
 U2 d2 D U 
 U2 d2 D U- 
 U2 d2 D U2 
 U2 d2 D2 U 
 U2 d2 D2 U- 
 U2 d2 D2 U2 
 F B' F 
 F B' F' 
 F B' F2 
 F B' b' F 
 F B' b' F' 
 F B' b' F2 
 F B' b F 
 F B' b F' 
 F B' b F2 
 F B' b2 F 
 F B' b2 F' 
 F B' b2 F2 
 F B F 
 F B F' 
 F B F2 
 F B b' F 
 F B b' F' 
 F B b' F2 
 F B b F 
 F B b F' 
 F B b F2 
 F B b2 F 
 F B b2 F' 
 F B b2 F2 
 F B2 F 
 F B2 F' 
 F B2 F2 
 F B2 b' F 
 F B2 b' F' 
 F B2 b' F2 
 F B2 b F 
 F B2 b F' 
 F B2 b F2 
 F B2 b2 F 
 F B2 b2 F' 
 F B2 b2 F2 
 F b' F 
 F b' F' 
 F b' F2 
 F b' B' F 
 F b' B' F' 
 F b' B' F2 
 F b' B F 
 F b' B F' 
 F b' B F2 
 F b' B2 F 
 F b' B2 F' 
 F b' B2 F2 
 F b F 
 F b F' 
 F b F2 
 F b B' F 
 F b B' F' 
 F b B' F2 
 F b B F 
 F b B F' 
 F b B F2 
 F b B2 F 
 F b B2 F' 
 F b B2 F2 
 F b2 F 
 F b2 F' 
 F b2 F2 
 F b2 B' F 
 F b2 B' F' 
 F b2 B' F2 
 F b2 B F 
 F b2 B F' 
 F b2 B F2 
 F b2 B2 F 
 F b2 B2 F' 
 F b2 B2 F2 
 F' B' F 
 F' B' F' 
 F' B' F2 
 F' B' b' F 
 F' B' b' F' 
 F' B' b' F2 
 F' B' b F 
 F' B' b F' 
 F' B' b F2 
 F' B' b2 F 
 F' B' b2 F' 
 F' B' b2 F2 
 F' B F 
 F' B F' 
 F' B F2 
 F' B b' F 
 F' B b' F' 
 F' B b' F2 
 F' B b F 
 F' B b F' 
 F' B b F2 
 F' B b2 F 
 F' B b2 F' 
 F' B b2 F2 
 F' B2 F 
 F' B2 F' 
 F' B2 F2 
 F' B2 b' F 
 F' B2 b' F' 
 F' B2 b' F2 
 F' B2 b F 
 F' B2 b F' 
 F' B2 b F2 
 F' B2 b2 F 
 F' B2 b2 F' 
 F' B2 b2 F2 
 F' b' F 
 F' b' F' 
 F' b' F2 
 F' b' B' F 
 F' b' B' F' 
 F' b' B' F2 
 F' b' B F 
 F' b' B F' 
 F' b' B F2 
 F' b' B2 F 
 F' b' B2 F' 
 F' b' B2 F2 
 F' b F 
 F' b F' 
 F' b F2 
 F' b B' F 
 F' b B' F' 
 F' b B' F2 
 F' b B F 
 F' b B F' 
 F' b B F2 
 F' b B2 F 
 F' b B2 F' 
 F' b B2 F2 
 F' b2 F 
 F' b2 F' 
 F' b2 F2 
 F' b2 B' F 
 F' b2 B' F' 
 F' b2 B' F2 
 F' b2 B F 
 F' b2 B F' 
 F' b2 B F2 
 F' b2 B2 F 
 F' b2 B2 F' 
 F' b2 B2 F2 
 F2 B' F 
 F2 B' F' 
 F2 B' F2 
 F2 B' b' F 
 F2 B' b' F' 
 F2 B' b' F2 
 F2 B' b F 
 F2 B' b F' 
 F2 B' b F2 
 F2 B' b2 F 
 F2 B' b2 F' 
 F2 B' b2 F2 
 F2 B F 
 F2 B F' 
 F2 B F2 
 F2 B b' F 
 F2 B b' F' 
 F2 B b' F2 
 F2 B b F 
 F2 B b F' 
 F2 B b F2 
 F2 B b2 F 
 F2 B b2 F' 
 F2 B b2 F2 
 F2 B2 F 
 F2 B2 F' 
 F2 B2 F2 
 F2 B2 b' F 
 F2 B2 b' F' 
 F2 B2 b' F2 
 F2 B2 b F 
 F2 B2 b F' 
 F2 B2 b F2 
 F2 B2 b2 F 
 F2 B2 b2 F' 
 F2 B2 b2 F2 
 F2 b' F 
 F2 b' F' 
 F2 b' F2 
 F2 b' B' F 
 F2 b' B' F' 
 F2 b' B' F2 
 F2 b' B F 
 F2 b' B F' 
 F2 b' B F2 
 F2 b' B2 F 
 F2 b' B2 F' 
 F2 b' B2 F2 
 F2 b F 
 F2 b F' 
 F2 b F2 
 F2 b B' F 
 F2 b B' F' 
 F2 b B' F2 
 F2 b B F 
 F2 b B F' 
 F2 b B F2 
 F2 b B2 F 
 F2 b B2 F' 
 F2 b B2 F2 
 F2 b2 F 
 F2 b2 F' 
 F2 b2 F2 
 F2 b2 B' F 
 F2 b2 B' F' 
 F2 b2 B' F2 
 F2 b2 B F 
 F2 b2 B F' 
 F2 b2 B F2 
 F2 b2 B2 F 
 F2 b2 B2 F' 
 F2 b2 B2 F2 
 R L' R 
 R L' R' 
 R L' R2 
 R L' l' R 
 R L' l' R' 
 R L' l' R2 
 R L' l R 
 R L' l R' 
 R L' l R2 
 R L' l2 R 
 R L' l2 R' 
 R L' l2 R2 
 R L R 
 R L R' 
 R L R2 
 R L l' R 
 R L l' R' 
 R L l' R2 
 R L l R 
 R L l R' 
 R L l R2 
 R L l2 R 
 R L l2 R' 
 R L l2 R2 
 R L2 R 
 R L2 R' 
 R L2 R2 
 R L2 l' R 
 R L2 l' R' 
 R L2 l' R2 
 R L2 l R 
 R L2 l R' 
 R L2 l R2 
 R L2 l2 R 
 R L2 l2 R' 
 R L2 l2 R2 
 R l' R 
 R l' R' 
 R l' R2 
 R l' L' R 
 R l' L' R' 
 R l' L' R2 
 R l' L R 
 R l' L R' 
 R l' L R2 
 R l' L2 R 
 R l' L2 R' 
 R l' L2 R2 
 R l R 
 R l R' 
 R l R2 
 R l L' R 
 R l L' R' 
 R l L' R2 
 R l L R 
 R l L R' 
 R l L R2 
 R l L2 R 
 R l L2 R' 
 R l L2 R2 
 R l2 R 
 R l2 R' 
 R l2 R2 
 R l2 L' R 
 R l2 L' R' 
 R l2 L' R2 
 R l2 L R 
 R l2 L R' 
 R l2 L R2 
 R l2 L2 R 
 R l2 L2 R' 
 R l2 L2 R2 
 R' L' R 
 R' L' R' 
 R' L' R2 
 R' L' l' R 
 R' L' l' R' 
 R' L' l' R2 
 R' L' l R 
 R' L' l R' 
 R' L' l R2 
 R' L' l2 R 
 R' L' l2 R' 
 R' L' l2 R2 
 R' L R 
 R' L R' 
 R' L R2 
 R' L l' R 
 R' L l' R' 
 R' L l' R2 
 R' L l R 
 R' L l R' 
 R' L l R2 
 R' L l2 R 
 R' L l2 R' 
 R' L l2 R2 
 R' L2 R 
 R' L2 R' 
 R' L2 R2 
 R' L2 l' R 
 R' L2 l' R' 
 R' L2 l' R2 
 R' L2 l R 
 R' L2 l R' 
 R' L2 l R2 
 R' L2 l2 R 
 R' L2 l2 R' 
 R' L2 l2 R2 
 R' l' R 
 R' l' R' 
 R' l' R2 
 R' l' L' R 
 R' l' L' R' 
 R' l' L' R2 
 R' l' L R 
 R' l' L R' 
 R' l' L R2 
 R' l' L2 R 
 R' l' L2 R' 
 R' l' L2 R2 
 R' l R 
 R' l R' 
 R' l R2 
 R' l L' R 
 R' l L' R' 
 R' l L' R2 
 R' l L R 
 R' l L R' 
 R' l L R2 
 R' l L2 R 
 R' l L2 R' 
 R' l L2 R2 
 R' l2 R 
 R' l2 R' 
 R' l2 R2 
 R' l2 L' R 
 R' l2 L' R' 
 R' l2 L' R2 
 R' l2 L R 
 R' l2 L R' 
 R' l2 L R2 
 R' l2 L2 R 
 R' l2 L2 R' 
 R' l2 L2 R2 
 R2 L' R 
 R2 L' R' 
 R2 L' R2 
 R2 L' l' R 
 R2 L' l' R' 
 R2 L' l' R2 
 R2 L' l R 
 R2 L' l R' 
 R2 L' l R2 
 R2 L' l2 R 
 R2 L' l2 R' 
 R2 L' l2 R2 
 R2 L R 
 R2 L R' 
 R2 L R2 
 R2 L l' R 
 R2 L l' R' 
 R2 L l' R2 
 R2 L l R 
 R2 L l R' 
 R2 L l R2 
 R2 L l2 R 
 R2 L l2 R' 
 R2 L l2 R2 
 R2 L2 R 
 R2 L2 R' 
 R2 L2 R2 
 R2 L2 l' R 
 R2 L2 l' R' 
 R2 L2 l' R2 
 R2 L2 l R 
 R2 L2 l R' 
 R2 L2 l R2 
 R2 L2 l2 R 
 R2 L2 l2 R' 
 R2 L2 l2 R2 
 R2 l' R 
 R2 l' R' 
 R2 l' R2 
 R2 l' L' R 
 R2 l' L' R' 
 R2 l' L' R2 
 R2 l' L R 
 R2 l' L R' 
 R2 l' L R2 
 R2 l' L2 R 
 R2 l' L2 R' 
 R2 l' L2 R2 
 R2 l R 
 R2 l R' 
 R2 l R2 
 R2 l L' R 
 R2 l L' R' 
 R2 l L' R2 
 R2 l L R 
 R2 l L R' 
 R2 l L R2 
 R2 l L2 R 
 R2 l L2 R' 
 R2 l L2 R2 
 R2 l2 R 
 R2 l2 R' 
 R2 l2 R2 
 R2 l2 L' R 
 R2 l2 L' R' 
 R2 l2 L' R2 
 R2 l2 L R 
 R2 l2 L R' 
 R2 l2 L R2 
 R2 l2 L2 R 
 R2 l2 L2 R' 
 R2 l2 L2 R2 
 D' U D' 
 D' U D 
 D' U D2 
 D' U u D' 
 D' U u D 
 D' U u D2 
 D' U u' D' 
 D' U u' D 
 D' U u' D2 
 D' U u2 D' 
 D' U u2 D 
 D' U u2 D2 
 D' U- D' 
 D' U- D 
 D' U- D2 
 D' U- u D' 
 D' U- u D 
 D' U- u D2 
 D' U- u' D' 
 D' U- u' D 
 D' U- u' D2 
 D' U- u2 D' 
 D' U- u2 D 
 D' U- u2 D2 
 D' U2 D' 
 D' U2 D 
 D' U2 D2 
 D' U2 u D' 
 D' U2 u D 
 D' U2 u D2 
 D' U2 u' D' 
 D' U2 u' D 
 D' U2 u' D2 
 D' U2 u2 D' 
 D' U2 u2 D 
 D' U2 u2 D2 
 D' u U D' 
 D' u U D 
 D' u U D2 
 D' u U- D' 
 D' u U- D 
 D' u U- D2 
 D' u U2 D' 
 D' u U2 D 
 D' u U2 D2 
 D' u D' 
 D' u D 
 D' u D2 
 D' u' U D' 
 D' u' U D 
 D' u' U D2 
 D' u' U- D' 
 D' u' U- D 
 D' u' U- D2 
 D' u' U2 D' 
 D' u' U2 D 
 D' u' U2 D2 
 D' u' D' 
 D' u' D 
 D' u' D2 
 D' u2 U D' 
 D' u2 U D 
 D' u2 U D2 
 D' u2 U- D' 
 D' u2 U- D 
 D' u2 U- D2 
 D' u2 U2 D' 
 D' u2 U2 D 
 D' u2 U2 D2 
 D' u2 D' 
 D' u2 D 
 D' u2 D2 
 D U D' 
 D U D 
 D U D2 
 D U u D' 
 D U u D 
 D U u D2 
 D U u' D' 
 D U u' D 
 D U u' D2 
 D U u2 D' 
 D U u2 D 
 D U u2 D2 
 D U- D' 
 D U- D 
 D U- D2 
 D U- u D' 
 D U- u D 
 D U- u D2 
 D U- u' D' 
 D U- u' D 
 D U- u' D2 
 D U- u2 D' 
 D U- u2 D 
 D U- u2 D2 
 D U2 D' 
 D U2 D 
 D U2 D2 
 D U2 u D' 
 D U2 u D 
 D U2 u D2 
 D U2 u' D' 
 D U2 u' D 
 D U2 u' D2 
 D U2 u2 D' 
 D U2 u2 D 
 D U2 u2 D2 
 D u U D' 
 D u U D 
 D u U D2 
 D u U- D' 
 D u U- D 
 D u U- D2 
 D u U2 D' 
 D u U2 D 
 D u U2 D2 
 D u D' 
 D u D 
 D u D2 
 D u' U D' 
 D u' U D 
 D u' U D2 
 D u' U- D' 
 D u' U- D 
 D u' U- D2 
 D u' U2 D' 
 D u' U2 D 
 D u' U2 D2 
 D u' D' 
 D u' D 
 D u' D2 
 D u2 U D' 
 D u2 U D 
 D u2 U D2 
 D u2 U- D' 
 D u2 U- D 
 D u2 U- D2 
 D u2 U2 D' 
 D u2 U2 D 
 D u2 U2 D2 
 D u2 D' 
 D u2 D 
 D u2 D2 
 D2 U D' 
 D2 U D 
 D2 U D2 
 D2 U u D' 
 D2 U u D 
 D2 U u D2 
 D2 U u' D' 
 D2 U u' D 
 D2 U u' D2 
 D2 U u2 D' 
 D2 U u2 D 
 D2 U u2 D2 
 D2 U- D' 
 D2 U- D 
 D2 U- D2 
 D2 U- u D' 
 D2 U- u D 
 D2 U- u D2 
 D2 U- u' D' 
 D2 U- u' D 
 D2 U- u' D2 
 D2 U- u2 D' 
 D2 U- u2 D 
 D2 U- u2 D2 
 D2 U2 D' 
 D2 U2 D 
 D2 U2 D2 
 D2 U2 u D' 
 D2 U2 u D 
 D2 U2 u D2 
 D2 U2 u' D' 
 D2 U2 u' D 
 D2 U2 u' D2 
 D2 U2 u2 D' 
 D2 U2 u2 D 
 D2 U2 u2 D2 
 D2 u U D' 
 D2 u U D 
 D2 u U D2 
 D2 u U- D' 
 D2 u U- D 
 D2 u U- D2 
 D2 u U2 D' 
 D2 u U2 D 
 D2 u U2 D2 
 D2 u D' 
 D2 u D 
 D2 u D2 
 D2 u' U D' 
 D2 u' U D 
 D2 u' U D2 
 D2 u' U- D' 
 D2 u' U- D 
 D2 u' U- D2 
 D2 u' U2 D' 
 D2 u' U2 D 
 D2 u' U2 D2 
 D2 u' D' 
 D2 u' D 
 D2 u' D2 
 D2 u2 U D' 
 D2 u2 U D 
 D2 u2 U D2 
 D2 u2 U- D' 
 D2 u2 U- D 
 D2 u2 U- D2 
 D2 u2 U2 D' 
 D2 u2 U2 D 
 D2 u2 U2 D2 
 D2 u2 D' 
 D2 u2 D 
 D2 u2 D2 
 B' F B' 
 B' F B 
 B' F B2 
 B' F f B' 
 B' F f B 
 B' F f B2 
 B' F f' B' 
 B' F f' B 
 B' F f' B2 
 B' F f2 B' 
 B' F f2 B 
 B' F f2 B2 
 B' F' B' 
 B' F' B 
 B' F' B2 
 B' F' f B' 
 B' F' f B 
 B' F' f B2 
 B' F' f' B' 
 B' F' f' B 
 B' F' f' B2 
 B' F' f2 B' 
 B' F' f2 B 
 B' F' f2 B2 
 B' F2 B' 
 B' F2 B 
 B' F2 B2 
 B' F2 f B' 
 B' F2 f B 
 B' F2 f B2 
 B' F2 f' B' 
 B' F2 f' B 
 B' F2 f' B2 
 B' F2 f2 B' 
 B' F2 f2 B 
 B' F2 f2 B2 
 B' f F B' 
 B' f F B 
 B' f F B2 
 B' f F' B' 
 B' f F' B 
 B' f F' B2 
 B' f F2 B' 
 B' f F2 B 
 B' f F2 B2 
 B' f B' 
 B' f B 
 B' f B2 
 B' f' F B' 
 B' f' F B 
 B' f' F B2 
 B' f' F' B' 
 B' f' F' B 
 B' f' F' B2 
 B' f' F2 B' 
 B' f' F2 B 
 B' f' F2 B2 
 B' f' B' 
 B' f' B 
 B' f' B2 
 B' f2 F B' 
 B' f2 F B 
 B' f2 F B2 
 B' f2 F' B' 
 B' f2 F' B 
 B' f2 F' B2 
 B' f2 F2 B' 
 B' f2 F2 B 
 B' f2 F2 B2 
 B' f2 B' 
 B' f2 B 
 B' f2 B2 
 B F B' 
 B F B 
 B F B2 
 B F f B' 
 B F f B 
 B F f B2 
 B F f' B' 
 B F f' B 
 B F f' B2 
 B F f2 B' 
 B F f2 B 
 B F f2 B2 
 B F' B' 
 B F' B 
 B F' B2 
 B F' f B' 
 B F' f B 
 B F' f B2 
 B F' f' B' 
 B F' f' B 
 B F' f' B2 
 B F' f2 B' 
 B F' f2 B 
 B F' f2 B2 
 B F2 B' 
 B F2 B 
 B F2 B2 
 B F2 f B' 
 B F2 f B 
 B F2 f B2 
 B F2 f' B' 
 B F2 f' B 
 B F2 f' B2 
 B F2 f2 B' 
 B F2 f2 B 
 B F2 f2 B2 
 B f F B' 
 B f F B 
 B f F B2 
 B f F' B' 
 B f F' B 
 B f F' B2 
 B f F2 B' 
 B f F2 B 
 B f F2 B2 
 B f B' 
 B f B 
 B f B2 
 B f' F B' 
 B f' F B 
 B f' F B2 
 B f' F' B' 
 B f' F' B 
 B f' F' B2 
 B f' F2 B' 
 B f' F2 B 
 B f' F2 B2 
 B f' B' 
 B f' B 
 B f' B2 
 B f2 F B' 
 B f2 F B 
 B f2 F B2 
 B f2 F' B' 
 B f2 F' B 
 B f2 F' B2 
 B f2 F2 B' 
 B f2 F2 B 
 B f2 F2 B2 
 B f2 B' 
 B f2 B 
 B f2 B2 
 B2 F B' 
 B2 F B 
 B2 F B2 
 B2 F f B' 
 B2 F f B 
 B2 F f B2 
 B2 F f' B' 
 B2 F f' B 
 B2 F f' B2 
 B2 F f2 B' 
 B2 F f2 B 
 B2 F f2 B2 
 B2 F' B' 
 B2 F' B 
 B2 F' B2 
 B2 F' f B' 
 B2 F' f B 
 B2 F' f B2 
 B2 F' f' B' 
 B2 F' f' B 
 B2 F' f' B2 
 B2 F' f2 B' 
 B2 F' f2 B 
 B2 F' f2 B2 
 B2 F2 B' 
 B2 F2 B 
 B2 F2 B2 
 B2 F2 f B' 
 B2 F2 f B 
 B2 F2 f B2 
 B2 F2 f' B' 
 B2 F2 f' B 
 B2 F2 f' B2 
 B2 F2 f2 B' 
 B2 F2 f2 B 
 B2 F2 f2 B2 
 B2 f F B' 
 B2 f F B 
 B2 f F B2 
 B2 f F' B' 
 B2 f F' B 
 B2 f F' B2 
 B2 f F2 B' 
 B2 f F2 B 
 B2 f F2 B2 
 B2 f B' 
 B2 f B 
 B2 f B2 
 B2 f' F B' 
 B2 f' F B 
 B2 f' F B2 
 B2 f' F' B' 
 B2 f' F' B 
 B2 f' F' B2 
 B2 f' F2 B' 
 B2 f' F2 B 
 B2 f' F2 B2 
 B2 f' B' 
 B2 f' B 
 B2 f' B2 
 B2 f2 F B' 
 B2 f2 F B 
 B2 f2 F B2 
 B2 f2 F' B' 
 B2 f2 F' B 
 B2 f2 F' B2 
 B2 f2 F2 B' 
 B2 f2 F2 B 
 B2 f2 F2 B2 
 B2 f2 B' 
 B2 f2 B 
 B2 f2 B2 
 L' R L' 
 L' R L 
 L' R L2 
 L' R r L' 
 L' R r L 
 L' R r L2 
 L' R r' L' 
 L' R r' L 
 L' R r' L2 
 L' R r2 L' 
 L' R r2 L 
 L' R r2 L2 
 L' R' L' 
 L' R' L 
 L' R' L2 
 L' R' r L' 
 L' R' r L 
 L' R' r L2 
 L' R' r' L' 
 L' R' r' L 
 L' R' r' L2 
 L' R' r2 L' 
 L' R' r2 L 
 L' R' r2 L2 
 L' R2 L' 
 L' R2 L 
 L' R2 L2 
 L' R2 r L' 
 L' R2 r L 
 L' R2 r L2 
 L' R2 r' L' 
 L' R2 r' L 
 L' R2 r' L2 
 L' R2 r2 L' 
 L' R2 r2 L 
 L' R2 r2 L2 
 L' r R L' 
 L' r R L 
 L' r R L2 
 L' r R' L' 
 L' r R' L 
 L' r R' L2 
 L' r R2 L' 
 L' r R2 L 
 L' r R2 L2 
 L' r L' 
 L' r L 
 L' r L2 
 L' r' R L' 
 L' r' R L 
 L' r' R L2 
 L' r' R' L' 
 L' r' R' L 
 L' r' R' L2 
 L' r' R2 L' 
 L' r' R2 L 
 L' r' R2 L2 
 L' r' L' 
 L' r' L 
 L' r' L2 
 L' r2 R L' 
 L' r2 R L 
 L' r2 R L2 
 L' r2 R' L' 
 L' r2 R' L 
 L' r2 R' L2 
 L' r2 R2 L' 
 L' r2 R2 L 
 L' r2 R2 L2 
 L' r2 L' 
 L' r2 L 
 L' r2 L2 
 L R L' 
 L R L 
 L R L2 
 L R r L' 
 L R r L 
 L R r L2 
 L R r' L' 
 L R r' L 
 L R r' L2 
 L R r2 L' 
 L R r2 L 
 L R r2 L2 
 L R' L' 
 L R' L 
 L R' L2 
 L R' r L' 
 L R' r L 
 L R' r L2 
 L R' r' L' 
 L R' r' L 
 L R' r' L2 
 L R' r2 L' 
 L R' r2 L 
 L R' r2 L2 
 L R2 L' 
 L R2 L 
 L R2 L2 
 L R2 r L' 
 L R2 r L 
 L R2 r L2 
 L R2 r' L' 
 L R2 r' L 
 L R2 r' L2 
 L R2 r2 L' 
 L R2 r2 L 
 L R2 r2 L2 
 L r R L' 
 L r R L 
 L r R L2 
 L r R' L' 
 L r R' L 
 L r R' L2 
 L r R2 L' 
 L r R2 L 
 L r R2 L2 
 L r L' 
 L r L 
 L r L2 
 L r' R L' 
 L r' R L 
 L r' R L2 
 L r' R' L' 
 L r' R' L 
 L r' R' L2 
 L r' R2 L' 
 L r' R2 L 
 L r' R2 L2 
 L r' L' 
 L r' L 
 L r' L2 
 L r2 R L' 
 L r2 R L 
 L r2 R L2 
 L r2 R' L' 
 L r2 R' L 
 L r2 R' L2 
 L r2 R2 L' 
 L r2 R2 L 
 L r2 R2 L2 
 L r2 L' 
 L r2 L 
 L r2 L2 
 L2 R L' 
 L2 R L 
 L2 R L2 
 L2 R r L' 
 L2 R r L 
 L2 R r L2 
 L2 R r' L' 
 L2 R r' L 
 L2 R r' L2 
 L2 R r2 L' 
 L2 R r2 L 
 L2 R r2 L2 
 L2 R' L' 
 L2 R' L 
 L2 R' L2 
 L2 R' r L' 
 L2 R' r L 
 L2 R' r L2 
 L2 R' r' L' 
 L2 R' r' L 
 L2 R' r' L2 
 L2 R' r2 L' 
 L2 R' r2 L 
 L2 R' r2 L2 
 L2 R2 L' 
 L2 R2 L 
 L2 R2 L2 
 L2 R2 r L' 
 L2 R2 r L 
 L2 R2 r L2 
 L2 R2 r' L' 
 L2 R2 r' L 
 L2 R2 r' L2 
 L2 R2 r2 L' 
 L2 R2 r2 L 
 L2 R2 r2 L2 
 L2 r R L' 
 L2 r R L 
 L2 r R L2 
 L2 r R' L' 
 L2 r R' L 
 L2 r R' L2 
 L2 r R2 L' 
 L2 r R2 L 
 L2 r R2 L2 
 L2 r L' 
 L2 r L 
 L2 r L2 
 L2 r' R L' 
 L2 r' R L 
 L2 r' R L2 
 L2 r' R' L' 
 L2 r' R' L 
 L2 r' R' L2 
 L2 r' R2 L' 
 L2 r' R2 L 
 L2 r' R2 L2 
 L2 r' L' 
 L2 r' L 
 L2 r' L2 
 L2 r2 R L' 
 L2 r2 R L 
 L2 r2 R L2 
 L2 r2 R' L' 
 L2 r2 R' L 
 L2 r2 R' L2 
 L2 r2 R2 L' 
 L2 r2 R2 L 
 L2 r2 R2 L2 
 L2 r2 L' 
 L2 r2 L 
 L2 r2 L2 
 u D' u 
 u D' u' 
 u D' u2 
 u D' d' u 
 u D' d' u' 
 u D' d' u2 
 u D' d u 
 u D' d u' 
 u D' d u2 
 u D' d2 u 
 u D' d2 u' 
 u D' d2 u2 
 u D u 
 u D u' 
 u D u2 
 u D d' u 
 u D d' u' 
 u D d' u2 
 u D d u 
 u D d u' 
 u D d u2 
 u D d2 u 
 u D d2 u' 
 u D d2 u2 
 u D2 u 
 u D2 u' 
 u D2 u2 
 u D2 d' u 
 u D2 d' u' 
 u D2 d' u2 
 u D2 d u 
 u D2 d u' 
 u D2 d u2 
 u D2 d2 u 
 u D2 d2 u' 
 u D2 d2 u2 
 u d' D' u 
 u d' D' u' 
 u d' D' u2 
 u d' D u 
 u d' D u' 
 u d' D u2 
 u d' D2 u 
 u d' D2 u' 
 u d' D2 u2 
 u d' u 
 u d' u' 
 u d' u2 
 u d D' u 
 u d D' u' 
 u d D' u2 
 u d D u 
 u d D u' 
 u d D u2 
 u d D2 u 
 u d D2 u' 
 u d D2 u2 
 u d u 
 u d u' 
 u d u2 
 u d2 D' u 
 u d2 D' u' 
 u d2 D' u2 
 u d2 D u 
 u d2 D u' 
 u d2 D u2 
 u d2 D2 u 
 u d2 D2 u' 
 u d2 D2 u2 
 u d2 u 
 u d2 u' 
 u d2 u2 
 u' D' u 
 u' D' u' 
 u' D' u2 
 u' D' d' u 
 u' D' d' u' 
 u' D' d' u2 
 u' D' d u 
 u' D' d u' 
 u' D' d u2 
 u' D' d2 u 
 u' D' d2 u' 
 u' D' d2 u2 
 u' D u 
 u' D u' 
 u' D u2 
 u' D d' u 
 u' D d' u' 
 u' D d' u2 
 u' D d u 
 u' D d u' 
 u' D d u2 
 u' D d2 u 
 u' D d2 u' 
 u' D d2 u2 
 u' D2 u 
 u' D2 u' 
 u' D2 u2 
 u' D2 d' u 
 u' D2 d' u' 
 u' D2 d' u2 
 u' D2 d u 
 u' D2 d u' 
 u' D2 d u2 
 u' D2 d2 u 
 u' D2 d2 u' 
 u' D2 d2 u2 
 u' d' D' u 
 u' d' D' u' 
 u' d' D' u2 
 u' d' D u 
 u' d' D u' 
 u' d' D u2 
 u' d' D2 u 
 u' d' D2 u' 
 u' d' D2 u2 
 u' d' u 
 u' d' u' 
 u' d' u2 
 u' d D' u 
 u' d D' u' 
 u' d D' u2 
 u' d D u 
 u' d D u' 
 u' d D u2 
 u' d D2 u 
 u' d D2 u' 
 u' d D2 u2 
 u' d u 
 u' d u' 
 u' d u2 
 u' d2 D' u 
 u' d2 D' u' 
 u' d2 D' u2 
 u' d2 D u 
 u' d2 D u' 
 u' d2 D u2 
 u' d2 D2 u 
 u' d2 D2 u' 
 u' d2 D2 u2 
 u' d2 u 
 u' d2 u' 
 u' d2 u2 
 u2 D' u 
 u2 D' u' 
 u2 D' u2 
 u2 D' d' u 
 u2 D' d' u' 
 u2 D' d' u2 
 u2 D' d u 
 u2 D' d u' 
 u2 D' d u2 
 u2 D' d2 u 
 u2 D' d2 u' 
 u2 D' d2 u2 
 u2 D u 
 u2 D u' 
 u2 D u2 
 u2 D d' u 
 u2 D d' u' 
 u2 D d' u2 
 u2 D d u 
 u2 D d u' 
 u2 D d u2 
 u2 D d2 u 
 u2 D d2 u' 
 u2 D d2 u2 
 u2 D2 u 
 u2 D2 u' 
 u2 D2 u2 
 u2 D2 d' u 
 u2 D2 d' u' 
 u2 D2 d' u2 
 u2 D2 d u 
 u2 D2 d u' 
 u2 D2 d u2 
 u2 D2 d2 u 
 u2 D2 d2 u' 
 u2 D2 d2 u2 
 u2 d' D' u 
 u2 d' D' u' 
 u2 d' D' u2 
 u2 d' D u 
 u2 d' D u' 
 u2 d' D u2 
 u2 d' D2 u 
 u2 d' D2 u' 
 u2 d' D2 u2 
 u2 d' u 
 u2 d' u' 
 u2 d' u2 
 u2 d D' u 
 u2 d D' u' 
 u2 d D' u2 
 u2 d D u 
 u2 d D u' 
 u2 d D u2 
 u2 d D2 u 
 u2 d D2 u' 
 u2 d D2 u2 
 u2 d u 
 u2 d u' 
 u2 d u2 
 u2 d2 D' u 
 u2 d2 D' u' 
 u2 d2 D' u2 
 u2 d2 D u 
 u2 d2 D u' 
 u2 d2 D u2 
 u2 d2 D2 u 
 u2 d2 D2 u' 
 u2 d2 D2 u2 
 u2 d2 u 
 u2 d2 u' 
 u2 d2 u2 
 f B' f 
 f B' f' 
 f B' f2 
 f B' b' f 
 f B' b' f' 
 f B' b' f2 
 f B' b f 
 f B' b f' 
 f B' b f2 
 f B' b2 f 
 f B' b2 f' 
 f B' b2 f2 
 f B f 
 f B f' 
 f B f2 
 f B b' f 
 f B b' f' 
 f B b' f2 
 f B b f 
 f B b f' 
 f B b f2 
 f B b2 f 
 f B b2 f' 
 f B b2 f2 
 f B2 f 
 f B2 f' 
 f B2 f2 
 f B2 b' f 
 f B2 b' f' 
 f B2 b' f2 
 f B2 b f 
 f B2 b f' 
 f B2 b f2 
 f B2 b2 f 
 f B2 b2 f' 
 f B2 b2 f2 
 f b' B' f 
 f b' B' f' 
 f b' B' f2 
 f b' B f 
 f b' B f' 
 f b' B f2 
 f b' B2 f 
 f b' B2 f' 
 f b' B2 f2 
 f b' f 
 f b' f' 
 f b' f2 
 f b B' f 
 f b B' f' 
 f b B' f2 
 f b B f 
 f b B f' 
 f b B f2 
 f b B2 f 
 f b B2 f' 
 f b B2 f2 
 f b f 
 f b f' 
 f b f2 
 f b2 B' f 
 f b2 B' f' 
 f b2 B' f2 
 f b2 B f 
 f b2 B f' 
 f b2 B f2 
 f b2 B2 f 
 f b2 B2 f' 
 f b2 B2 f2 
 f b2 f 
 f b2 f' 
 f b2 f2 
 f' B' f 
 f' B' f' 
 f' B' f2 
 f' B' b' f 
 f' B' b' f' 
 f' B' b' f2 
 f' B' b f 
 f' B' b f' 
 f' B' b f2 
 f' B' b2 f 
 f' B' b2 f' 
 f' B' b2 f2 
 f' B f 
 f' B f' 
 f' B f2 
 f' B b' f 
 f' B b' f' 
 f' B b' f2 
 f' B b f 
 f' B b f' 
 f' B b f2 
 f' B b2 f 
 f' B b2 f' 
 f' B b2 f2 
 f' B2 f 
 f' B2 f' 
 f' B2 f2 
 f' B2 b' f 
 f' B2 b' f' 
 f' B2 b' f2 
 f' B2 b f 
 f' B2 b f' 
 f' B2 b f2 
 f' B2 b2 f 
 f' B2 b2 f' 
 f' B2 b2 f2 
 f' b' B' f 
 f' b' B' f' 
 f' b' B' f2 
 f' b' B f 
 f' b' B f' 
 f' b' B f2 
 f' b' B2 f 
 f' b' B2 f' 
 f' b' B2 f2 
 f' b' f 
 f' b' f' 
 f' b' f2 
 f' b B' f 
 f' b B' f' 
 f' b B' f2 
 f' b B f 
 f' b B f' 
 f' b B f2 
 f' b B2 f 
 f' b B2 f' 
 f' b B2 f2 
 f' b f 
 f' b f' 
 f' b f2 
 f' b2 B' f 
 f' b2 B' f' 
 f' b2 B' f2 
 f' b2 B f 
 f' b2 B f' 
 f' b2 B f2 
 f' b2 B2 f 
 f' b2 B2 f' 
 f' b2 B2 f2 
 f' b2 f 
 f' b2 f' 
 f' b2 f2 
 f2 B' f 
 f2 B' f' 
 f2 B' f2 
 f2 B' b' f 
 f2 B' b' f' 
 f2 B' b' f2 
 f2 B' b f 
 f2 B' b f' 
 f2 B' b f2 
 f2 B' b2 f 
 f2 B' b2 f' 
 f2 B' b2 f2 
 f2 B f 
 f2 B f' 
 f2 B f2 
 f2 B b' f 
 f2 B b' f' 
 f2 B b' f2 
 f2 B b f 
 f2 B b f' 
 f2 B b f2 
 f2 B b2 f 
 f2 B b2 f' 
 f2 B b2 f2 
 f2 B2 f 
 f2 B2 f' 
 f2 B2 f2 
 f2 B2 b' f 
 f2 B2 b' f' 
 f2 B2 b' f2 
 f2 B2 b f 
 f2 B2 b f' 
 f2 B2 b f2 
 f2 B2 b2 f 
 f2 B2 b2 f' 
 f2 B2 b2 f2 
 f2 b' B' f 
 f2 b' B' f' 
 f2 b' B' f2 
 f2 b' B f 
 f2 b' B f' 
 f2 b' B f2 
 f2 b' B2 f 
 f2 b' B2 f' 
 f2 b' B2 f2 
 f2 b' f 
 f2 b' f' 
 f2 b' f2 
 f2 b B' f 
 f2 b B' f' 
 f2 b B' f2 
 f2 b B f 
 f2 b B f' 
 f2 b B f2 
 f2 b B2 f 
 f2 b B2 f' 
 f2 b B2 f2 
 f2 b f 
 f2 b f' 
 f2 b f2 
 f2 b2 B' f 
 f2 b2 B' f' 
 f2 b2 B' f2 
 f2 b2 B f 
 f2 b2 B f' 
 f2 b2 B f2 
 f2 b2 B2 f 
 f2 b2 B2 f' 
 f2 b2 B2 f2 
 f2 b2 f 
 f2 b2 f' 
 f2 b2 f2 
 r L' r 
 r L' r' 
 r L' r2 
 r L' l' r 
 r L' l' r' 
 r L' l' r2 
 r L' l r 
 r L' l r' 
 r L' l r2 
 r L' l2 r 
 r L' l2 r' 
 r L' l2 r2 
 r L r 
 r L r' 
 r L r2 
 r L l' r 
 r L l' r' 
 r L l' r2 
 r L l r 
 r L l r' 
 r L l r2 
 r L l2 r 
 r L l2 r' 
 r L l2 r2 
 r L2 r 
 r L2 r' 
 r L2 r2 
 r L2 l' r 
 r L2 l' r' 
 r L2 l' r2 
 r L2 l r 
 r L2 l r' 
 r L2 l r2 
 r L2 l2 r 
 r L2 l2 r' 
 r L2 l2 r2 
 r l' L' r 
 r l' L' r' 
 r l' L' r2 
 r l' L r 
 r l' L r' 
 r l' L r2 
 r l' L2 r 
 r l' L2 r' 
 r l' L2 r2 
 r l' r 
 r l' r' 
 r l' r2 
 r l L' r 
 r l L' r' 
 r l L' r2 
 r l L r 
 r l L r' 
 r l L r2 
 r l L2 r 
 r l L2 r' 
 r l L2 r2 
 r l r 
 r l r' 
 r l r2 
 r l2 L' r 
 r l2 L' r' 
 r l2 L' r2 
 r l2 L r 
 r l2 L r' 
 r l2 L r2 
 r l2 L2 r 
 r l2 L2 r' 
 r l2 L2 r2 
 r l2 r 
 r l2 r' 
 r l2 r2 
 r' L' r 
 r' L' r' 
 r' L' r2 
 r' L' l' r 
 r' L' l' r' 
 r' L' l' r2 
 r' L' l r 
 r' L' l r' 
 r' L' l r2 
 r' L' l2 r 
 r' L' l2 r' 
 r' L' l2 r2 
 r' L r 
 r' L r' 
 r' L r2 
 r' L l' r 
 r' L l' r' 
 r' L l' r2 
 r' L l r 
 r' L l r' 
 r' L l r2 
 r' L l2 r 
 r' L l2 r' 
 r' L l2 r2 
 r' L2 r 
 r' L2 r' 
 r' L2 r2 
 r' L2 l' r 
 r' L2 l' r' 
 r' L2 l' r2 
 r' L2 l r 
 r' L2 l r' 
 r' L2 l r2 
 r' L2 l2 r 
 r' L2 l2 r' 
 r' L2 l2 r2 
 r' l' L' r 
 r' l' L' r' 
 r' l' L' r2 
 r' l' L r 
 r' l' L r' 
 r' l' L r2 
 r' l' L2 r 
 r' l' L2 r' 
 r' l' L2 r2 
 r' l' r 
 r' l' r' 
 r' l' r2 
 r' l L' r 
 r' l L' r' 
 r' l L' r2 
 r' l L r 
 r' l L r' 
 r' l L r2 
 r' l L2 r 
 r' l L2 r' 
 r' l L2 r2 
 r' l r 
 r' l r' 
 r' l r2 
 r' l2 L' r 
 r' l2 L' r' 
 r' l2 L' r2 
 r' l2 L r 
 r' l2 L r' 
 r' l2 L r2 
 r' l2 L2 r 
 r' l2 L2 r' 
 r' l2 L2 r2 
 r' l2 r 
 r' l2 r' 
 r' l2 r2 
 r2 L' r 
 r2 L' r' 
 r2 L' r2 
 r2 L' l' r 
 r2 L' l' r' 
 r2 L' l' r2 
 r2 L' l r 
 r2 L' l r' 
 r2 L' l r2 
 r2 L' l2 r 
 r2 L' l2 r' 
 r2 L' l2 r2 
 r2 L r 
 r2 L r' 
 r2 L r2 
 r2 L l' r 
 r2 L l' r' 
 r2 L l' r2 
 r2 L l r 
 r2 L l r' 
 r2 L l r2 
 r2 L l2 r 
 r2 L l2 r' 
 r2 L l2 r2 
 r2 L2 r 
 r2 L2 r' 
 r2 L2 r2 
 r2 L2 l' r 
 r2 L2 l' r' 
 r2 L2 l' r2 
 r2 L2 l r 
 r2 L2 l r' 
 r2 L2 l r2 
 r2 L2 l2 r 
 r2 L2 l2 r' 
 r2 L2 l2 r2 
 r2 l' L' r 
 r2 l' L' r' 
 r2 l' L' r2 
 r2 l' L r 
 r2 l' L r' 
 r2 l' L r2 
 r2 l' L2 r 
 r2 l' L2 r' 
 r2 l' L2 r2 
 r2 l' r 
 r2 l' r' 
 r2 l' r2 
 r2 l L' r 
 r2 l L' r' 
 r2 l L' r2 
 r2 l L r 
 r2 l L r' 
 r2 l L r2 
 r2 l L2 r 
 r2 l L2 r' 
 r2 l L2 r2 
 r2 l r 
 r2 l r' 
 r2 l r2 
 r2 l2 L' r 
 r2 l2 L' r' 
 r2 l2 L' r2 
 r2 l2 L r 
 r2 l2 L r' 
 r2 l2 L r2 
 r2 l2 L2 r 
 r2 l2 L2 r' 
 r2 l2 L2 r2 
 r2 l2 r 
 r2 l2 r' 
 r2 l2 r2 
 d' U u d' 
 d' U u d 
 d' U u d2 
 d' U u' d' 
 d' U u' d 
 d' U u' d2 
 d' U u2 d' 
 d' U u2 d 
 d' U u2 d2 
 d' U d' 
 d' U d 
 d' U d2 
 d' U- u d' 
 d' U- u d 
 d' U- u d2 
 d' U- u' d' 
 d' U- u' d 
 d' U- u' d2 
 d' U- u2 d' 
 d' U- u2 d 
 d' U- u2 d2 
 d' U- d' 
 d' U- d 
 d' U- d2 
 d' U2 u d' 
 d' U2 u d 
 d' U2 u d2 
 d' U2 u' d' 
 d' U2 u' d 
 d' U2 u' d2 
 d' U2 u2 d' 
 d' U2 u2 d 
 d' U2 u2 d2 
 d' U2 d' 
 d' U2 d 
 d' U2 d2 
 d' u U d' 
 d' u U d 
 d' u U d2 
 d' u U- d' 
 d' u U- d 
 d' u U- d2 
 d' u U2 d' 
 d' u U2 d 
 d' u U2 d2 
 d' u d' 
 d' u d 
 d' u d2 
 d' u' U d' 
 d' u' U d 
 d' u' U d2 
 d' u' U- d' 
 d' u' U- d 
 d' u' U- d2 
 d' u' U2 d' 
 d' u' U2 d 
 d' u' U2 d2 
 d' u' d' 
 d' u' d 
 d' u' d2 
 d' u2 U d' 
 d' u2 U d 
 d' u2 U d2 
 d' u2 U- d' 
 d' u2 U- d 
 d' u2 U- d2 
 d' u2 U2 d' 
 d' u2 U2 d 
 d' u2 U2 d2 
 d' u2 d' 
 d' u2 d 
 d' u2 d2 
 d U u d' 
 d U u d 
 d U u d2 
 d U u' d' 
 d U u' d 
 d U u' d2 
 d U u2 d' 
 d U u2 d 
 d U u2 d2 
 d U d' 
 d U d 
 d U d2 
 d U- u d' 
 d U- u d 
 d U- u d2 
 d U- u' d' 
 d U- u' d 
 d U- u' d2 
 d U- u2 d' 
 d U- u2 d 
 d U- u2 d2 
 d U- d' 
 d U- d 
 d U- d2 
 d U2 u d' 
 d U2 u d 
 d U2 u d2 
 d U2 u' d' 
 d U2 u' d 
 d U2 u' d2 
 d U2 u2 d' 
 d U2 u2 d 
 d U2 u2 d2 
 d U2 d' 
 d U2 d 
 d U2 d2 
 d u U d' 
 d u U d 
 d u U d2 
 d u U- d' 
 d u U- d 
 d u U- d2 
 d u U2 d' 
 d u U2 d 
 d u U2 d2 
 d u d' 
 d u d 
 d u d2 
 d u' U d' 
 d u' U d 
 d u' U d2 
 d u' U- d' 
 d u' U- d 
 d u' U- d2 
 d u' U2 d' 
 d u' U2 d 
 d u' U2 d2 
 d u' d' 
 d u' d 
 d u' d2 
 d u2 U d' 
 d u2 U d 
 d u2 U d2 
 d u2 U- d' 
 d u2 U- d 
 d u2 U- d2 
 d u2 U2 d' 
 d u2 U2 d 
 d u2 U2 d2 
 d u2 d' 
 d u2 d 
 d u2 d2 
 d2 U u d' 
 d2 U u d 
 d2 U u d2 
 d2 U u' d' 
 d2 U u' d 
 d2 U u' d2 
 d2 U u2 d' 
 d2 U u2 d 
 d2 U u2 d2 
 d2 U d' 
 d2 U d 
 d2 U d2 
 d2 U- u d' 
 d2 U- u d 
 d2 U- u d2 
 d2 U- u' d' 
 d2 U- u' d 
 d2 U- u' d2 
 d2 U- u2 d' 
 d2 U- u2 d 
 d2 U- u2 d2 
 d2 U- d' 
 d2 U- d 
 d2 U- d2 
 d2 U2 u d' 
 d2 U2 u d 
 d2 U2 u d2 
 d2 U2 u' d' 
 d2 U2 u' d 
 d2 U2 u' d2 
 d2 U2 u2 d' 
 d2 U2 u2 d 
 d2 U2 u2 d2 
 d2 U2 d' 
 d2 U2 d 
 d2 U2 d2 
 d2 u U d' 
 d2 u U d 
 d2 u U d2 
 d2 u U- d' 
 d2 u U- d 
 d2 u U- d2 
 d2 u U2 d' 
 d2 u U2 d 
 d2 u U2 d2 
 d2 u d' 
 d2 u d 
 d2 u d2 
 d2 u' U d' 
 d2 u' U d 
 d2 u' U d2 
 d2 u' U- d' 
 d2 u' U- d 
 d2 u' U- d2 
 d2 u' U2 d' 
 d2 u' U2 d 
 d2 u' U2 d2 
 d2 u' d' 
 d2 u' d 
 d2 u' d2 
 d2 u2 U d' 
 d2 u2 U d 
 d2 u2 U d2 
 d2 u2 U- d' 
 d2 u2 U- d 
 d2 u2 U- d2 
 d2 u2 U2 d' 
 d2 u2 U2 d 
 d2 u2 U2 d2 
 d2 u2 d' 
 d2 u2 d 
 d2 u2 d2 
 b' F f b' 
 b' F f b 
 b' F f b2 
 b' F f' b' 
 b' F f' b 
 b' F f' b2 
 b' F f2 b' 
 b' F f2 b 
 b' F f2 b2 
 b' F b' 
 b' F b 
 b' F b2 
 b' F' f b' 
 b' F' f b 
 b' F' f b2 
 b' F' f' b' 
 b' F' f' b 
 b' F' f' b2 
 b' F' f2 b' 
 b' F' f2 b 
 b' F' f2 b2 
 b' F' b' 
 b' F' b 
 b' F' b2 
 b' F2 f b' 
 b' F2 f b 
 b' F2 f b2 
 b' F2 f' b' 
 b' F2 f' b 
 b' F2 f' b2 
 b' F2 f2 b' 
 b' F2 f2 b 
 b' F2 f2 b2 
 b' F2 b' 
 b' F2 b 
 b' F2 b2 
 b' f F b' 
 b' f F b 
 b' f F b2 
 b' f F' b' 
 b' f F' b 
 b' f F' b2 
 b' f F2 b' 
 b' f F2 b 
 b' f F2 b2 
 b' f b' 
 b' f b 
 b' f b2 
 b' f' F b' 
 b' f' F b 
 b' f' F b2 
 b' f' F' b' 
 b' f' F' b 
 b' f' F' b2 
 b' f' F2 b' 
 b' f' F2 b 
 b' f' F2 b2 
 b' f' b' 
 b' f' b 
 b' f' b2 
 b' f2 F b' 
 b' f2 F b 
 b' f2 F b2 
 b' f2 F' b' 
 b' f2 F' b 
 b' f2 F' b2 
 b' f2 F2 b' 
 b' f2 F2 b 
 b' f2 F2 b2 
 b' f2 b' 
 b' f2 b 
 b' f2 b2 
 b F f b' 
 b F f b 
 b F f b2 
 b F f' b' 
 b F f' b 
 b F f' b2 
 b F f2 b' 
 b F f2 b 
 b F f2 b2 
 b F b' 
 b F b 
 b F b2 
 b F' f b' 
 b F' f b 
 b F' f b2 
 b F' f' b' 
 b F' f' b 
 b F' f' b2 
 b F' f2 b' 
 b F' f2 b 
 b F' f2 b2 
 b F' b' 
 b F' b 
 b F' b2 
 b F2 f b' 
 b F2 f b 
 b F2 f b2 
 b F2 f' b' 
 b F2 f' b 
 b F2 f' b2 
 b F2 f2 b' 
 b F2 f2 b 
 b F2 f2 b2 
 b F2 b' 
 b F2 b 
 b F2 b2 
 b f F b' 
 b f F b 
 b f F b2 
 b f F' b' 
 b f F' b 
 b f F' b2 
 b f F2 b' 
 b f F2 b 
 b f F2 b2 
 b f b' 
 b f b 
 b f b2 
 b f' F b' 
 b f' F b 
 b f' F b2 
 b f' F' b' 
 b f' F' b 
 b f' F' b2 
 b f' F2 b' 
 b f' F2 b 
 b f' F2 b2 
 b f' b' 
 b f' b 
 b f' b2 
 b f2 F b' 
 b f2 F b 
 b f2 F b2 
 b f2 F' b' 
 b f2 F' b 
 b f2 F' b2 
 b f2 F2 b' 
 b f2 F2 b 
 b f2 F2 b2 
 b f2 b' 
 b f2 b 
 b f2 b2 
 b2 F f b' 
 b2 F f b 
 b2 F f b2 
 b2 F f' b' 
 b2 F f' b 
 b2 F f' b2 
 b2 F f2 b' 
 b2 F f2 b 
 b2 F f2 b2 
 b2 F b' 
 b2 F b 
 b2 F b2 
 b2 F' f b' 
 b2 F' f b 
 b2 F' f b2 
 b2 F' f' b' 
 b2 F' f' b 
 b2 F' f' b2 
 b2 F' f2 b' 
 b2 F' f2 b 
 b2 F' f2 b2 
 b2 F' b' 
 b2 F' b 
 b2 F' b2 
 b2 F2 f b' 
 b2 F2 f b 
 b2 F2 f b2 
 b2 F2 f' b' 
 b2 F2 f' b 
 b2 F2 f' b2 
 b2 F2 f2 b' 
 b2 F2 f2 b 
 b2 F2 f2 b2 
 b2 F2 b' 
 b2 F2 b 
 b2 F2 b2 
 b2 f F b' 
 b2 f F b 
 b2 f F b2 
 b2 f F' b' 
 b2 f F' b 
 b2 f F' b2 
 b2 f F2 b' 
 b2 f F2 b 
 b2 f F2 b2 
 b2 f b' 
 b2 f b 
 b2 f b2 
 b2 f' F b' 
 b2 f' F b 
 b2 f' F b2 
 b2 f' F' b' 
 b2 f' F' b 
 b2 f' F' b2 
 b2 f' F2 b' 
 b2 f' F2 b 
 b2 f' F2 b2 
 b2 f' b' 
 b2 f' b 
 b2 f' b2 
 b2 f2 F b' 
 b2 f2 F b 
 b2 f2 F b2 
 b2 f2 F' b' 
 b2 f2 F' b 
 b2 f2 F' b2 
 b2 f2 F2 b' 
 b2 f2 F2 b 
 b2 f2 F2 b2 
 b2 f2 b' 
 b2 f2 b 
 b2 f2 b2 
 l' R r l' 
 l' R r l 
 l' R r l2 
 l' R r' l' 
 l' R r' l 
 l' R r' l2 
 l' R r2 l' 
 l' R r2 l 
 l' R r2 l2 
 l' R l' 
 l' R l 
 l' R l2 
 l' R' r l' 
 l' R' r l 
 l' R' r l2 
 l' R' r' l' 
 l' R' r' l 
 l' R' r' l2 
 l' R' r2 l' 
 l' R' r2 l 
 l' R' r2 l2 
 l' R' l' 
 l' R' l 
 l' R' l2 
 l' R2 r l' 
 l' R2 r l 
 l' R2 r l2 
 l' R2 r' l' 
 l' R2 r' l 
 l' R2 r' l2 
 l' R2 r2 l' 
 l' R2 r2 l 
 l' R2 r2 l2 
 l' R2 l' 
 l' R2 l 
 l' R2 l2 
 l' r R l' 
 l' r R l 
 l' r R l2 
 l' r R' l' 
 l' r R' l 
 l' r R' l2 
 l' r R2 l' 
 l' r R2 l 
 l' r R2 l2 
 l' r l' 
 l' r l 
 l' r l2 
 l' r' R l' 
 l' r' R l 
 l' r' R l2 
 l' r' R' l' 
 l' r' R' l 
 l' r' R' l2 
 l' r' R2 l' 
 l' r' R2 l 
 l' r' R2 l2 
 l' r' l' 
 l' r' l 
 l' r' l2 
 l' r2 R l' 
 l' r2 R l 
 l' r2 R l2 
 l' r2 R' l' 
 l' r2 R' l 
 l' r2 R' l2 
 l' r2 R2 l' 
 l' r2 R2 l 
 l' r2 R2 l2 
 l' r2 l' 
 l' r2 l 
 l' r2 l2 
 l R r l' 
 l R r l 
 l R r l2 
 l R r' l' 
 l R r' l 
 l R r' l2 
 l R r2 l' 
 l R r2 l 
 l R r2 l2 
 l R l' 
 l R l 
 l R l2 
 l R' r l' 
 l R' r l 
 l R' r l2 
 l R' r' l' 
 l R' r' l 
 l R' r' l2 
 l R' r2 l' 
 l R' r2 l 
 l R' r2 l2 
 l R' l' 
 l R' l 
 l R' l2 
 l R2 r l' 
 l R2 r l 
 l R2 r l2 
 l R2 r' l' 
 l R2 r' l 
 l R2 r' l2 
 l R2 r2 l' 
 l R2 r2 l 
 l R2 r2 l2 
 l R2 l' 
 l R2 l 
 l R2 l2 
 l r R l' 
 l r R l 
 l r R l2 
 l r R' l' 
 l r R' l 
 l r R' l2 
 l r R2 l' 
 l r R2 l 
 l r R2 l2 
 l r l' 
 l r l 
 l r l2 
 l r' R l' 
 l r' R l 
 l r' R l2 
 l r' R' l' 
 l r' R' l 
 l r' R' l2 
 l r' R2 l' 
 l r' R2 l 
 l r' R2 l2 
 l r' l' 
 l r' l 
 l r' l2 
 l r2 R l' 
 l r2 R l 
 l r2 R l2 
 l r2 R' l' 
 l r2 R' l 
 l r2 R' l2 
 l r2 R2 l' 
 l r2 R2 l 
 l r2 R2 l2 
 l r2 l' 
 l r2 l 
 l r2 l2 
 l2 R r l' 
 l2 R r l 
 l2 R r l2 
 l2 R r' l' 
 l2 R r' l 
 l2 R r' l2 
 l2 R r2 l' 
 l2 R r2 l 
 l2 R r2 l2 
 l2 R l' 
 l2 R l 
 l2 R l2 
 l2 R' r l' 
 l2 R' r l 
 l2 R' r l2 
 l2 R' r' l' 
 l2 R' r' l 
 l2 R' r' l2 
 l2 R' r2 l' 
 l2 R' r2 l 
 l2 R' r2 l2 
 l2 R' l' 
 l2 R' l 
 l2 R' l2 
 l2 R2 r l' 
 l2 R2 r l 
 l2 R2 r l2 
 l2 R2 r' l' 
 l2 R2 r' l 
 l2 R2 r' l2 
 l2 R2 r2 l' 
 l2 R2 r2 l 
 l2 R2 r2 l2 
 l2 R2 l' 
 l2 R2 l 
 l2 R2 l2 
 l2 r R l' 
 l2 r R l 
 l2 r R l2 
 l2 r R' l' 
 l2 r R' l 
 l2 r R' l2 
 l2 r R2 l' 
 l2 r R2 l 
 l2 r R2 l2 
 l2 r l' 
 l2 r l 
 l2 r l2 
 l2 r' R l' 
 l2 r' R l 
 l2 r' R l2 
 l2 r' R' l' 
 l2 r' R' l 
 l2 r' R' l2 
 l2 r' R2 l' 
 l2 r' R2 l 
 l2 r' R2 l2 
 l2 r' l' 
 l2 r' l 
 l2 r' l2 
 l2 r2 R l' 
 l2 r2 R l 
 l2 r2 R l2 
 l2 r2 R' l' 
 l2 r2 R' l 
 l2 r2 R' l2 
 l2 r2 R2 l' 
 l2 r2 R2 l 
 l2 r2 R2 l2 
 l2 r2 l' 
 l2 r2 l 
 l2 r2 l2

It looks like each person had a different agenda and the software compliments one another nicely. The solver of CW Tasai is very fast on my machine. I entered some random scrambles and 62-68 move solutions were appearing almost as soon as I hit the enter key. Not a move-length-optimized solution, but one that appeared with stunning speed!

It looks like I am not treading on anyone's toes as I don't believe the previous authors were crazy enough to implement a "brute force only" 4x4x4 solver. My interest is exhaustive search for the purpose of find any/all shortest algos for a given "endgame" if you want to call it that. And I have an ASCII board, unlike the others :)

revenge solve.jpg

Right now I added a feature to draw the starting problem cube to a text file, the solution, and the number of nodes explored to find the brute force results. As a test of the code, I am having it solve every possible arrangement where only 2 center pieces need to be exchanged on an otherwise solved cube. I want to know if every arrangement can be solved by a unique 8-ply solution. For example, the top-left center of the top and the bottom-right center on the front (I call this Centers T1:F4) seems to be the one requiring at least 2 turns to "orient" the centers before applying a center swapping algo. Can this "align and then apply the algo" approach be bypassed by a unique, shorter algo?

It is a simple test for starters, but one that will tell me if the pruning code I added today was done correctly. Once I know the result, I can move on to more complex tasks.
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Consider adding a small corners-only pruning table. This will give you pretty deep
pruning pretty quickly (should fit in cache; can be done with 78K entries or so); check
this before you check your bigger hash table. You can even take it a step further;
each entry can contain information on what twists take you closer to solved so you
don't even need to do many of the counterproductive moves. And you can factor
the coordinate into two subcoordinates, with tiny move tables, so the instruction
count is very minimal.

Average depth from solved on the 2x2x2 is somewhere around 10. This should
help keep you out of the weeds.

Edit:
After the corners-only table, you might consider adding a pruning table for two adjacent
corners, the two edges between them, and four same-color centers. I think this could
be done with a pruning table of perhaps 100MB, and you'll probably get a pretty good
distance on this. Further, this pruning table can be applied in 24 different ways to the
revenge; you can keep an pseudo-LRU table of which ones to check first.

If you have enough RAM you might choose to do one corner, four same-color centers,
and four of the edges near that corner around those centers. This will take a table
with 2.7B entries, which you can compact in a number of ways (using four, or two, or
1.6 bits per entry).

What you want to find is a pruning table that gives you the greatest average depth, and
I believe focusing on a small number of adjacent cubies will probably do this. Further,
you can exploit the adjacencies in various ways. Also, lookups are cheaper if you don't
need to examine as much cube state. Finally, you probably want to include cubies of
each "type" so you don't get lost in big non-solution areas that your pruning table has
a weak spot for.

For instance, my 3x3 optimal solver from about 2002/2003 focused on the top face cubies
only, and was able to get excellent performance.

-tom
 
Last edited by a moderator:

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Consider adding a small corners-only pruning table.
-tom

I'm afraid I don't know what you mean. I am not building a scramble-solver via algorithms. I am building, basically, a bruce force algorithm finder/verifier.

The sun would run out of Hydrogen by the time I got to a depth of 18 moves, for example, nowhere near enough to solve a sufficiently scrambled cube.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
The simplest way to visualize it is probably this.

Build a table storing the depth for each position of the revenge---but *only* consider the
corners. Ignore the edges and the centers *completely*. (You need to start with 24
entries at 0 because there are 24 different solution orientations, and you can populate it
by breadth-first search.)

Now, in your search recursion, at each step, look up your current position using *only* the
corners. If the table says you are too far away using only the corners, the position of
the other cubies don't matter---you're simply too far away.

That table, using a naive implementation, would have 8! * 3^7 or about 88M entries. You
can reduce this to about 78K entries by using the 1152-order symmetries of the 2x2x2.

The average depth of this table is, I think, about 9. Thus, you get very easy, fast,
and relatively deep pruning.

There are a lot of ways to make this faster once you have it working, but the basic idea
is simple: ignore everything but the corners. If corners "pass", then apply your other
search tree pruning techniques.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
The simplest way to visualize it is probably this.

Build a table storing the depth for each position of the revenge---but *only* consider the
corners.

I understand now. Speed cubers solve the corners last. In my lame way of solving, I do them much, much earlier. I solve the centers and dedges last.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
Ah, ok, sorry. Indeed, those cases are probably inner-slice heavy and corners are (almost) solved most of the time, so I don't see it being any good for that, either.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Corners will help prune the *search* a lot. You spend most of the time
in any standard IDA* search right at the outer limits of your pruning table.
Your search tree includes many move sequences that disturb the corners.
Let's say you are eight moves into a search, with a target depth of 15,
and the table says you are eight moves away from a corner solution. You
know then that you can prune your search immediately and backtrack.
No need to consider any further subnodes.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Corners will help prune the *search* a lot. You spend most of the time
in any standard IDA* search right at the outer limits of your pruning table.
Your search tree includes many move sequences that disturb the corners.
Let's say you are eight moves into a search, with a target depth of 15,
and the table says you are eight moves away from a corner solution. You
know then that you can prune your search immediately and backtrack.
No need to consider any further subnodes.

OK the concept of probing a database of presolved distances I understand, and I have that option.

I stored all 5-turn configurations of ALL 4x4x4 cube positions into a 6.5 GB buffer. I didn't bother probing it for the center solves because I was essentially benchmarking the solver speed.

There are countless 4x4x4 inner configurations possible for every set of corner-only data. I don't think this 3x3x3 shortcut can help with the 4x4x4, but I would love it if it did.
I just need to gain a better understanding of it.

I have a COMMUTATOR FILTER now, which speeds up things tremendously for solves where you know it is a commutator solution.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I stored all 5-turn configurations of ALL 4x4x4 cube positions into a 6.5 GB buffer. I didn't bother probing it for the center solves because I was essentially benchmarking the solver speed.

There are countless 4x4x4 inner configurations possible for every set of corner-only data. I don't think this 3x3x3 shortcut can help with the 4x4x4, but I would love it if it did.
I just need to gain a better understanding of it.

I am not sure exactly what your goals are with the solver you're writing. It seemed at first you were intending to generate optimal solutions for a specified position. But I'm not clear that some of what you are doing to increase its speed may be at the expense of guaranteeing optimal solutions for some metric.

An optimal solver is a type of solver that guarantees that a solution of the shortest possible length will be found (assuming the program runs for a long enough time) for some move metric. Such solvers typically use an iterative-deepening depth-first search. I suggest reading http://www.jaapsch.net/puzzles/compcube.htm to learn about some of the basic techniques that are used in quality solver programs. The documentation for Cube Explorer can also be good to read.

Your table of positions up to depth 5 uses a lot of memory, and can tell you if a given position is at least 6 moves from solved or not. The corner pruning table suggested by Tom needs a lot less memory and can often detect if a position is at least 9 moves from solved. In a depth-first search, being able to abort a search path 3 moves earlier can save a lot of "useless" searching. If your average branching factor is 28 moves, each time you prune 3 moves earlier would save about 28 + 28^2 + 28^3 = 22764 positions from being generated.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
I am not sure exactly what your goals are with the solver you're writing.

I want to find the optimal solution for any position within the horizon of the search.

It seemed at first you were intending to generate optimal solutions for a specified position.

When I was testing the move generator and benchmarking its speed, yes. When it got faster, I fed it a whole family of center positions to solve, and someone remarked that one of the solutions was a new commutator.

But I'm not clear that some of what you are doing to increase its speed may be at the expense of guaranteeing optimal solutions for some metric.

I do iterative deepening, one-ply at a time. At each leaf node, I test to see if the cube is solved. If not, I can probe a 1-turn-from-solved, 2-tfs, 3-tfs, 4-tfs, and 5-tfs database. I probe from smallest (1) to largest (5). If I get a hit, I know that I can solve it in at least that many turns.

At this point, I can take one of two paths:

1) Announce a win in however many moves and quit.
2) Continue searching

Option 2) is for determining if you can win more quickly than the tfs database. After all, I have not explored every leaf node at the current level. If I hit the 1-tfs database, there is no need to continue. I can't be less than 1 move away from solving the cube. But if I hit the 5-tfs database, that doesn't mean there isn't a 3-tfs position that is in there that I did not encounter yet from the current level of search.

I suggest reading http://www.jaapsch.net/puzzles/compcube.htm to learn about some of the basic techniques that are used in quality solver programs. The documentation for Cube Explorer can also be good to read.

I thank you for the references, I will take a look.

Your table of positions up to depth 5 uses a lot of memory, and can tell you if a given position is at least 6 moves from solved or not. The corner pruning table suggested by Tom needs a lot less memory and can often detect if a position is at least 9 moves from solved. In a depth-first search, being able to abort a search path 3 moves earlier can save a lot of "useless" searching. If your average branching factor is 28 moves, each time you prune 3 moves earlier would save about 28 + 28^2 + 28^3 = 22764 positions from being generated.

The branching factor varies based on two types of pruning:

1. Parallel face pruning
2. Non-Commutator pruning

If a solution is suspected to be of a commutator format, I can prune the heck out of the tree by setting a user-defined variable and hacking out any sequence where all the moves aren't zeroed in the end. I can even skip odd-plies in the search.

Parallel face pruning is less of a chainsaw, but still decent. I have not compiled explicit numbers for each as of yet.

I finally decided on a name for this program: Omnia Obtorquebantur 4x4x4

It means "All [sides/cubes] will be turned." I guess you can just call it OO 4x4x4. And, if it is successful, I will code a 5x5x5 version.

OO 4x4x4.jpg
 
Last edited:

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Yes, new to me. It is similar to a known corner commutator, but applied on the 4x4x4 in a way that I would not have thought to try.

Send me a move scramble to get a cube to that 3-cycle center you want me to test. The new code is running so much faster. I don't understand the other notation you posted yesterday.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA

OK, the search has started! I have the 1-turn-from-solve database re-coded as a rapid lookup function that uses 0-bytes of disk space :) Should be interesting to see how this performs. I want to see if the "auto-skip next ply" code is working. After 6 plies, if none of the 1-tfs database positions are hit, then there is no need to iterate over ply 7, and the search can proceed directly to ply 8. At ply 8 it will also find a 9-ply result if there is one.

search_started.jpg
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel

OK, the search has started! I have the 1-turn-from-solve database re-coded as a rapid lookup function that uses 0-bytes of disk space :) Should be interesting to see how this performs. I want to see if the "auto-skip next ply" code is working. After 6 plies, if none of the 1-tfs database positions are hit, then there is no need to iterate over ply 7, and the search can proceed directly to ply 8. At ply 8 it will also find a 9-ply result if there is one.

View attachment 3829

Yes that is the case I am curious about! Thank you both. I was inspired by the, as far as I know relatively recent, discovery of "pseudo-slice" commutators of the form [D b D', l'] and [(Uu) r (Uu)', l'] and wondered if the case you are currently searching could be done a different way than people have tried before. I'm particularly curious if it can be done in fewer than 10 turns in block turn metric.
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
Just one thing, if you plan to use this to generate algs, you might want to check for symmetries and ignore moves that only affects solved pieces at the start.

Doesn't cmowla's proposed (proven?) optimal length parity algorithm for wing edges turn only solved pieces on the first turn (or last turn you do the inverse alg)?
 
Status
Not open for further replies.
Top