cs0x7f / fivestage444 Goto Github PK

============
Introduction
============

The five stage solver for 4x4x4 is C++ program originally written by Bruce Norskog. Some information can be found on this page: http://cubezzz.dyndns.org/drupal/?q=node/view/62 and on other posts by Bruce on the same forum.
This is an attempt to use it as a WCA scrambler program.

Some conditions are required for this:
- it must print sufficiently short scrambles. Actual WCA scrambles are 40 twist turns long, so it should be close to this.
- it must generate solutions in a reasonable amount of time, less than a few seconds.
- it should not use big stored tables, as the program should be able to be distributed. Well, the program could generate and store those table locally during the first execution, but it's not very nice.
- it must be written in java, to be incorporated in Jeremy's awesome noodle program.

About first point, Bruce's program outputs solutions in 53 block turns on average and 66 twist turns (see old_doc.txt for metric definition), so the program should be improved to get shorter solutions. Current program only take the first best solution of every stage. An idea would be to try every solution for every stage...

=========================
Description of the stages
=========================

Stage 1
Orient the corner cubies, and put the u- and d-layer edges into those two layers. (A d-layer edge may be in u layer, and a u-layer edge may be in the d layer.)
All slice turns allowed:
        U,U',U2,u,u',u2,D,D',D2,d,d',d2,
        L,L',L2,l,l',l2,R,R',R2,r,r',r2,
        F,F',F2,f,f',f2,B,B',B2,b,b',b2
One-time whole cube rotations allowed:
120-degree turns (either direction) about the UFL-DBR axis.

Stage 2
Put front and back centers onto the front and back faces into one of the twelve configurations that can be solved using only half-turn moves. Arrange u- and d-layer edges within the u- and d-layers so that they will be in one of the 96 configurations that can be solved using only half-turn moves.
Slice turns allowed:
        U,U',U2,u,u',u2,D,D',D2,d,d',d2,
        L2,l,l',l2,R2,r,r',r2,
        F2,f,f',f2,B2,b,b',b2
One-time whole cube rotations allowed:
90-degree turn about U-D axis.

Stage 3
Put centers for left and right faces into the left and right faces so that they are in one of the 12 configurations that can be solved using only half-turn moves. This leaves the centers for the U and D faces arbitrarily arranged in the U and D faces. Put top and bottom layer edges into positions such that the U or D facelet is facing either up or down. Also, put these edges into an even permutation.
Slice turns allowed:
        U,U',U2,u2,D,D',D2,d2,
        L2,l2,R2,r2,
        F2,f,f',f2,B2,b,b',b2

Stage 4
Put corners into one of the 96 configurations that can be solved using only half-turn moves. Put U and D centers into one of the 12 configurations that can be solved using only half-turn moves. Put all U- and D-layer edges into a configuration that can be solved using only half-turn moves. This consists of 96 possible configurations for the l- and r-layer edges, and 96 for the f- and b-layer edges.
Slice turns to use:
        U,U',U2,u2,D,D',D2,d2,
        L2,l2,R2,r2,
        F2,f2,B2,b2

Stage 5
Put all cubies into their solved position.
Slice turns allowed:
        U2,u2,D2,d2,
        L2,l2,R2,r2,
        F2,f2,B2,b2
One-time whole cube rotations allowed:
180-degree turns about U-D, F-B, L-R axes.

========
Analysis
========

Stage       Positions          Unique     Symmetries
------------------------------------------------------
  1     1,608,475,077      33,516,864             48
  2    21,622,847,400   2,703,114,810             16
  3    23,189,166,000   2,898,889,420              8
  4     2,593,080,000     162,371,132             16
  5   146,767,085,568   3,080,465,032             48

======
Memory
======

Move tables          Positions        Moves        Size        Memory (byte)
----------------------------------------------------------------------------
stage 1 symedges        15,582           36           4            2,243,808
stage 1 corners          2,187           18           2               78,732
stage 2 symcenters         716           28           2               40,096
stage 2 edges              420           28           2               23,520
stage 3 symcenters     113,330           20           4            9,066,400
stage 3 edges           12,870           20           2              514,800
stage 4 symedges         5,968           16           4              381,952
stage 4 corners            420           16           2               13,440
stage 4 centers             70           16           1                1,120
stage 5 symedges        21,908           12           4            1,051,584
stage 5 corners             96           12           1                1,152
stage 5 centers          1,728           12           2               41,472

Pruning tables              Positions        Memory (byte)
----------------------------------------------------------
stage 1                    34,077,834            6,815,567
stage 2 centers/edges         300,720               60,145
stage 3 symcenters            113,330               22,667
stage 3 edges                  25,740                5,149
stage 3                 2,917,114,200          583,422,841
stage 4                   175,459,200           35,091,841
stage 5 symedges/centers   37,857,024            7,571,405
stage 5 symedges/corners    2,103,168              420,634
stage 5                 3,634,274,304          726,854,861

Full pruning tables for stage 3 and 5 can be enabled at the begining of Constants.java.