Tuesday, May 5, 2015

Rubik's Cube Solver C++

Computer Puzzling or
My quest to solve Rubik's Cube using a personal computer.

I started my adventure with computer puzzling by writing a simple 3x3 8-piece sliding puzzle solver in C++ back in year 2002. I knew very little then about solving puzzles with a computer and solving puzzles in general. My first solver was a heuristic algorithm. It produced non-optimal results but solved the puzzle. My friend wrote a solver that beat mine by always finding a shorter solution. He advised me to use brute force tree search since the solution space is pretty small for the 3x3 8-piece sliding puzzle. Therefore there is no need to use any sort of heuristic evaluation. The breadth-first search will always find the shortest path.

The tree of all permutations is the structure of states with four descendants
each. Each descendant represents move in one direction in the puzzle. For many
states only two moves are valid, for some all four. Invalid moves may be
replaced by the NULL pointer in the branch. Also, when the move is about to
repeat the state that is already generated in one of the previous branches, it
should also be considered illegal:


                               GoalState R0
                          ------------------------
                          Left   Up   Down   Right
                           /     |     |       \
                          /     NULL   |       NULL
                         /             |
                 State1 LB0            |
           ------------------------    |
           Left   Up   Down   Right    |
            /    NULL  DB1    NULL     |
           /                       State2 DB2  
        State LB1           ------------------------
                            Left   Up   Down   Right
                             /     |     |       \
                            /     NULL   |       NULL
                           /             |
                   State3 LB3            |  
             ------------------------    |
             Left   Up   Down   Right    |
                                         |
                                    State4 DB3
                              ------------------------
                              Left   Up   Down   Right

The approach to solve the puzzle is to generate all possible descendants of
the goal state in the form of a tree. For 3x3 puzzle we have 9! permutations.
Each configuration has exactly 9!/2 solutions.

Data is represented in the linear tables couple:

Index:
0 1  2   3   4   5   6   7   ...
Tree:
X R0 LB0 DB2 LB1 DB1 LB3 DB3 ...  
Parent state index table:
X 0  1   1   2   2   3   3 ...

First row represents the index in the table. The second row represents the 
states of the puzzle. The index #0 is not used. The Parent state index table 
is used to create the sequence of the moves once the initial state is 
generated.

The tree array keeps the values of pointers to the PTree structure:

struct PuzzleTree
{
Box anBox; // represents the state
// descendants
PuzzleTree *pUp;
PuzzleTree *pDown;
PuzzleTree *pRight;
PuzzleTree *pLeft;
// internal use
long lID;
};

typedef struct PuzzleTree PTree;
typedef PTree *PTreePtr;

The InitialState R0 is the actual goal state - a solved puzzle.
Once the tree is generated, it is dumped in a file, so during the next program run the solutions are read from cache and a search is performed to find a state of the scrambled puzzle. Once the scrambled puzzle state is found in the cache, the solution is instantly known by going up the tree branches to the root state which is a solved puzzle. I included both methods - heuristic search  and brute force search in the program.

Example:
M:\src\devcppprj\Puzzle3x3>puzzle3x3 -tbegin 1 3 0 4 2 7 8 5 6 -tend

Slide puzzle 3x3. Public domain. Author: Marek K.'2002.

Starting state:
-------
1 3 0
4 2 7
8 5 6
-------
Goal state:
-------
1 2 3
4 5 6
7 8 0
-------
Algorithm type: linear tree search.
Please wait...
Reading tree from file...
File tree.bin opened successfully.
Tree read successfully.
Puzzle solved!
LIST:
-------
1 3 0
4 2 7
8 5 6
-------
NEXT...
-------
1 0 3
4 2 7
8 5 6
-------
NEXT...
-------
1 2 3
4 0 7
8 5 6
-------
NEXT...
-------
1 2 3
4 5 7
8 0 6
-------
NEXT...
-------
1 2 3
4 5 7
0 8 6
-------
NEXT...
-------
1 2 3
0 5 7
4 8 6
-------
NEXT...
-------
1 2 3
5 0 7
4 8 6
-------
NEXT...
-------
1 2 3
5 7 0
4 8 6
-------
NEXT...
-------
1 2 3
5 7 6
4 8 0
-------
NEXT...
-------
1 2 3
5 7 6
4 0 8
-------
NEXT...
-------
1 2 3
5 0 6
4 7 8
-------
NEXT...
-------
1 2 3
0 5 6
4 7 8
-------
NEXT...
-------
1 2 3
4 5 6
0 7 8
-------
NEXT...
-------
1 2 3
4 5 6
7 0 8
-------
NEXT...
-------
1 2 3
4 5 6
7 8 0
-------
NEXT...
END OF LIST.

In 14 moves.

The source code is available for download here: Marek's Public Share @SkyDrive
Look for ZIP archive: Puzzle3x3.zip

I loved the simplicity of brute force search. In my naivety I though it could be used as a magic formula to solve any puzzle, including Rubik's Cube.

I was wrong of course and when I posted on Google+ that the solver should be as easy as a simple tree search, I was immediately set straight by one participant in the discussion. Writing a computer program to solve the cube was in my bucket list for a long time now, so it was the time to prove him (or myself) wrong. The challenge was on.

I started by writing a simple cube engine to be able to represent the cube internally in the computer, display cube state on the computer screen and perform moves or transformations of the cubies as to change the cube state as one would do with the real Rubik's Cube. Computer graphics is not my thing, so I decided to use a flat unfolded presentation on the text console. I later implemented colors so the picture is more user friendly.

There are several ways of representing Rubik's Cube in the computer's memory. Some are better for presentation purposes and some are better for processing and searches. I started with facelet representation, which is far from optimal for  solving purposes, but it is good for presentation. Since I just started my experimenting with the cube, having a manipulation and presentation engine seemed to be a logical choice and intuitive approach. This later complicated things (a lot) for me. It would be better to start with minimalistic cube model and do conversions before displaying it on the screen or taking input from user instead of operating solely on the facelet model. 
The other way is to represent the cube in the form of one-dimensional arrays after establishing nomenclature of numbering edge and corner cubies. This method can be called cubie model, because it is not based on individual faces but rather cubies (edge and corner). For certain algorithm purposes it is also good to keep the orientation of the cubies in separate arrays. Both methods of 3x3x3 Rubik's Cube represenation I describe in detail below.

Rubik's cube unfolded - cube representation in the application:

Facelet model.

Internal cube faces coding and their mapping to my real cube colors:

U - upper face  -  (W) white
F - front face  -  (R) red
D - lower face  -  (Y) yellow
L - left face   -  (G) green
R - right face  -  (B) blue
B - back face   -  (P) purple (it is orange on original cube)

A single cubie's (face) is ID-ied with a letter and a number, where letter
is a face designation (F-front, U-upper, D-down/bottom, B-back, L-left and
R-right) and a number indicates exact position of the cubie's face on the 
face of the cube. 
All cubies with number 4 are stationary (middle of the cube).

Below is the state representing a solved cube:

                        +---+---+---+
                        |U0 |U1 |U2 |
                        +---+---+---+
                        |U3 |U4 |U5 |
                        +---+---+---+
                        |U6 |U7 |U8 |
            +---+---+---+---+---+---+---+---+---+---+---+---+
            |L0 |L1 |L2 |F0 |F1 |F2 |R0 |R1 |R2 |B0 |B1 |B2 |
            +---+---+---+---+---+---+---+---+---+---+---+---+
            |L3 |L4 |L5 |F3 |F4 |F5 |R3 |R4 |R5 |B3 |B4 |B5 |
            +---+---+---+---+---+---+---+---+---+---+---+---+
            |L6 |L7 |L8 |F6 |F7 |F8 |R6 |R7 |R8 |B6 |B7 |B8 |
            +---+---+---+---+---+---+---+---+---+---+---+---+
                        |D0 |D1 |D2 |
                        +---+---+---+
                        |D3 |D4 |D5 |
                        +---+---+---+
                        |D6 |D7 |D8 |
                        +---+---+---+

This is a solved cube coded with color letters instead of cubie ID-s and with
extra connection lines showing how the 3-d cube was unfolded:
                        
                               -----------------------
                              |                       |
                        +---+---+---+                 |
               ---------| W | W | W |---------        |
              |         +---+---+---+         |       |
              |    -----| W | W | W |-----    |       |
              |   |     +---+---+---+     |   |---    |
              |   |     | W | W | W |     |   |   |   |
            +---+---+---+---+---+---+---+---+---+---+---+---+
        *-->| G | G | G | R | R | R | B | B | B | P | P | P |-->*
            +---+---+---+---+---+---+---+---+---+---+---+---+
       **-->| G | G | G | R | R | R | B | B | B | P | P | P |-->**
            +---+---+---+---+---+---+---+---+---+---+---+---+
      ***-->| G | G | G | R | R | R | B | B | B | P | P | P |-->***
            +---+---+---+---+---+---+---+---+---+---+---+---+
              |   |     | Y | Y | Y |     |   |   |   |
              |   |     +---+---+---+     |   |---    |
              |    -----| Y | Y | Y |-----    |       |
              |         +---+---+---+         |       |
               ---------| Y | Y | Y |---------        |
                        +---+---+---+                 |
                              |                       |
                               -----------------------          

Regardles of the current state of the cube, the center (middle) cubies remain
stationary and these faces are still referenced to by their middle cubies even
though the edge and other cubies may at the moment come from different planes.

Example of a scrambled cube:

          R6 L1 R8
          F1 U4 B3
          U8 L7 L8

D2 U7 F2  R0 D3 D0  F6 R5 D8  B6 U3 F8
D5 L4 D1  F7 F4 D7  B7 R4 U5  R1 B4 R7
D6 F3 L2  U6 R3 U0  L0 B1 R2  U2 B5 L6

          F0 F5 B2
          L5 D4 U1
          B8 L3 B0

A input notation of above cube state (the notation accepted by program in
command line arguments) is presented below:

R6 L1 R8 F1 U4 B3 U8 L7 L8 D2 U7 F2 D5 L4 D1 D6 F3 L2 R0 D3 D0 F7 F4 D7 U6 R3 
U0 F6 R5 D8 B7 R4 U5 L0 B1 R2 B6 U3 F8 R1 B4 R7 U2 B5 L6 F0 F5 B2 L5 D4 U1 B8
L3 B0

Note that a sequence of scrambled cube faces separated with spaces are in the 
following order:

   U, L, F, R, B, D

So, the upper face is entered line by line, then left face, line by line,
then front face etc.

Solutions produced by program assume that the cube is being held with the
front face (F) toward user, upper (U) face being on the top, bottom (D) face
on the bottom and back (B) face being in the back (opposite to F).

The next level of abstraction is a plane, which contains all cubies from a
single face and adjacent neighboring faces, forming a plane or a layer of
cubies that move together when the plane is rotated.

E.g.:
   
Front plane consists of faces:
   F0..F8, U6..U8, R0, R3, R6, D0..D2, L2, L5, L8.
   Note that faces L2, F0 and U6 represent a single corner cubie, just as
   faces U8, F2 and R0 etc., while U7-F1, U3-L1, U5-R1 and U1-B1 pairs 
   represent edge cubies of the upper face and adjacent left, right, bottom
   and front faces.
Back plane (one on the opposite side) consists of faces:
   B0..B8, R2, R5, R8, L0, L3, L6, U0..U2, D6..D8.
Upper plane consists of faces:
   L0..L2, F0..F2, U0..U8, R0..R2, B0..B2.
Bottom plane consists of faces:
   L6..L8, F6..F8, D0..D8, R6..R8, B6..B8.
Left plane consists of faces:
   F0, F3, F6, U0, U3, U6, D0, D3, D6, L0..L8, B2, B5, B8.
Right plane consists of faces:
   F2,5,8, U2,5,8, D2,5,8, R0..R8, B0,3,6.

                        
Solved upper layer cross (## - not important):


                        +---+---+---+
                        |## |U1 |## |
                        +---+---+---+
                        |U3 |U4 |U5 |
                        +---+---+---+
                        |## |U7 |## |
            +---+---+---+---+---+---+---+---+---+---+---+---+
            |## |L1 |## |## |F1 |## |## |R1 |## |## |B1 |## |
            +---+---+---+---+---+---+---+---+---+---+---+---+
            |## |L4 |## |## |F4 |## |## |R4 |## |## |B4 |## |
            +---+---+---+---+---+---+---+---+---+---+---+---+
            |## |## |## |## |## |## |## |## |## |## |## |## |
            +---+---+---+---+---+---+---+---+---+---+---+---+
                        |## |## |## |
                        +---+---+---+
                        |## |D4 |## |
                        +---+---+---+
                        |## |## |## |
                        +---+---+---+ 

Cube move notation:

The solutions generated by program as well as command line input and
input to some internal methods follows the nomenclature described below.

Letters L, R, U, D, F, B represent corresponding planes being rotated
90 degrees clockwise.
If above letters are followed by 'i', the planes are rotated 90 degrees
counter-clockwise.
If above letters are followed by '2', the planes are rotaged 180 degrees (does not matter if clock-wise or counter clock-wise, since both moves are equivalent).

Example sequence of moves:

LLDFBiLLFiBDLL

or

L2DFBiL2FiBDL2

translates to following cube moves:

- Rotate left plane 180 degrees.
- Rotate bottom plane 90 degrees clockwise.
- Rotate front plane 90 degrees clockwise.
- Rotate back plane 90 degrees counter-clockwise.
- Rotate left plane 180 degrees.
- Rotate front plane 90 degrees counter-clockwise.
- Rotate back plane 90 degrees clockwise.
- Rotate bottom plane 90 degrees clockwise.
- Rotate left plane 180 degrees.

Examples of equivalent moves:

LL = L2 = LiLi
BB = B2 = BiBi
BBB = B2B = Bi

Examples of self-cancelling moves (leading to the same cube state as 
before they were performed):

DDDD or D2D2
LLi

Cubie model.

For cube solving, it is more officient to represent cube internally
as cubie model. This representation consists of total of 40 states.
20 states for corners and edges permutation and 20 states for corresponding
orientation of the cubies.

Edges are numbered 1-12 and corners 1-8.
When referring to the facelet presentation described earlier, the corners
to facelets conversions are:

Corner #  - Facelet symbol (3-corner faces)
1 - U0 (L0 U0 B2)
2 - F6 (L8 F6 D0)
3 - R8 (R8 B6 D8)
4 - U8 (U8 F2 R0)
5 - U6 (L2 U6 F0)
6 - L6 (L6 B8 D6)
7 - F8 (F8 R6 D2)
8 - U2 (U2 R2 B0)

and the edges to facelets conversions are:

Edge # - Facelet symbol (2-egde faces)
1 - U3 (U3 L1)
2 - L7 (L7 D3)
3 - U5 (U5 R1)
4 - R7 (R7 D5)
5 - L3 (L3 B5)
6 - L5 (L5 F3)
7 - F5 (F5 R3)
8 - R5 (R5 B3)
9 - F1 (F1 U7)
10 - F7 (F7 D1)
11 - B7 (B7 D7)
12 - U1 (U1 B1)

Which can be represented in memory as (solved cube):
ep = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; // edges permutation
eo = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; // edges orientation
cp = {1, 2, 3, 4, 5, 6, 7, 8}; // corners permutation
co = {0, 0, 0, 0, 0, 0, 0, 0}; // corners orientation

Edges can have good (1) or bad (0) orientation.
Corners can have good (0), clockwise twist (1) or counter clock wise twist (2) orientation.

My first attempt was a brute force search. However after waiting for solution for a very long time and not getting any, I started digging more information about the Rubik Cube  and was crushed by cruel reality!

According to Wikipedia, the total number of possible states is approximately 43 quantillion or:

8! x 3^7 x (12!/2) x 2^11 = 43,252,003,274,489,856,000

This would require about 30 computer years to map solutions for all states of the cube.
After experimenting with the cube and my own algorithms, including heuristics, I wasn't satisfied with the results. I decided I needed to study the topic to get better understanding of the puzzle. Two methods emerged as candidates: the layer-by-layer human approach based algorithm and the Thistlethwaite's 45 algorithm.

The layer-by-layer is relatively easy. It involves dividing the solution into following stages:

* Solve cross: 1-st layer edges.
* Solve 1-st layer corners.
* Solve middle layer: middle layer edges.
* Solve bottom layer cross.
* Position/solve permutation of the corners on the bottom layer.
* Fix orientation of the bottom layer corners.
* Fix permutation of the bottom layer edges.
* Cube solved.

With facelet cube model and the design limitations of the layer-by-layer approach, the result was a huge amount of ugly code producing highly non-optimal solutions (length-wise), but very fast and effective. I am yet to find the cube it can not solve, I ran very extensive test cases and so far all combinations generated randomly worked. I also tested the algorithm on a super-flip configuration and it was solved very fast in 200 quarter-turn moves:

M:\src\devcppprj\Rubik>rubik -a 3 -c -C -N -w URRFBRBBRUULBBRUiDiRRFRiLBBUUFF
Rubik Solver 3.0.0 (C) 2015 by Marek Karcz. All rights reserved.
Solving cube:

          U0 B1 U2
          L1 U4 R1
          U6 F1 U8

L0 U3 L2  F0 U7 F2  R0 U5 R2  B0 U1 B2
B5 L4 F3  L5 F4 R3  F5 R4 B3  R5 B4 L3
L6 D3 L8  F6 D1 F8  R6 D5 R8  B6 D7 B8

          D0 F7 D2
          L7 D4 R7
          D6 B7 D8

Input notation:U0 B1 U2 L1 U4 R1 U6 F1 U8 L0 U3 L2 B5 L4 F3 L6 D3 L8 F0 U7 F2 L5
 F4 R3 F6 D1 F8 R0 U5 R2 F5 R4 B3 R6 D5 R8 B0 U1 B2 R5 B4 L3 B6 D7 B8 D0 F7 D2 L
7 D4 R7 D6 B7 D8

Color notation:W P W G W B W R W G W G P G R G Y G R W R G R B R Y R B W B R B P
 B Y B P W P B P G P Y P Y R Y G Y B Y P Y

Finished in 0.015 seconds.

Cube solved!
Solution has 200 moves: FRBUiFRULUiDiRiDiRDURiDiRDRiDiRDURiDiRDURiDiRDURiDiRDUUR
iDiRDUiRiDiRDRiDiRDUDiBDiBiDiLiDLRiDRDFDiFiDRDiRiDiBiDBLDiLiDiFiDFLDiLiDiFiDFDFL
DLiDiFiDDFLDLiDiLDLiDiFiRDiLiDRiDiLRDiLiDRiDiLDiDiRDiLiDRiDiLDLDLiDLDiLiDLDDLiDL
iDiLDiLiDDLDLDLiDLDDLiDDLiDiLDiLiDDLLDLiDLDiLiDLDDLiDiLLDFBiLLFiBDLLD

1)      F  R  B  Ui F  R  U  L  Ui Di Ri Di R  D  U  Ri Di R  D  Ri
2)      Di R  D  U  Ri Di R  D  U  Ri Di R  D  U  Ri Di R  D  U  U
3)      Ri Di R  D  Ui Ri Di R  D  Ri Di R  D  U  Di B  Di Bi Di Li
4)      D  L  Ri D  R  D  F  Di Fi D  R  Di Ri Di Bi D  B  L  Di Li
5)      Di Fi D  F  L  Di Li Di Fi D  F  D  F  L  D  Li Di Fi D  D
6)      F  L  D  Li Di L  D  Li Di Fi R  Di Li D  Ri Di L  R  Di Li
7)      D  Ri Di L  Di Di R  Di Li D  Ri Di L  D  L  D  Li D  L  Di
8)      Li D  L  D  D  Li D  Li Di L  Di Li D  D  L  D  L  D  Li D
9)      L  D  D  Li D  D  Li Di L  Di Li D  D  L  L  D  Li D  L  Di
10)     Li D  L  D  D  Li Di L  L  D  F  Bi L  L  Fi B  D  L  L  D

The Thistlethwaite-45 (T45) algorithm proven a little bit more difficult to implement for me and I think I still did not get it quite right, but since it was designed by mathematician, it is much more elegant, produces shorter solutions (maximum 45 moves, 31 on average) and is also very fast. The cube is represented in computer's memory using cubie model (edges, corners, permutations, orientations).
This method divides the solution into 4 stages. In which stage cube is brought up to the next goal state without disturbing previously achieved result, just like in layer-by-layer method. It is achieved by IDA tree search with pruning. In each stage the number of permitted moves are more restricted to ensure that each previously solved stage stays solved.

In stage 1 all edge orientations are solved.
In stage 2 corner orientations are solved and the LR edges are put in their slice.
In stage 3 corners are put in their G3 orbit and all edges are put in their slice in an even permutation.
In stage 4 cube is solved.

For each stage, following moves are permitted:

G0: L, R, F, B, U, D - this group represents all cube states
G1: L, R, F, B, U2, D2
G2: L, R, F2, B2, U2, D2
G3: L2, R2, F2, B2, U2, D2
G4: I - cube solved

The essential part of the T45 algorithm is generating proper prune tables that aid in tree search for each stage of the solution. 
For stage 1, we use moves from G0 group and edges orientation state to generate prune table. For stage 2 we use moves from G1, corners orientation state and the location of edge cubies from LR slice. Stage 3 is more tricky - we need to generate the G3 corners permutations set using only moves from G3 and from this initial set we generate the prune table with moves in G2, using the G3 orbit corners permutations set and edge permutation for FB and UD slices. Prune tables for stage 4 are generated using moves from G3 and corners and edges permutations.
Once all the prune tables are generated, solution is found using IDA tree search.

I struggled with this implementation and finally got it working, but there are discrepancies in my results that differ from what sources provide regarding pruning tables initial values, the average solution length and the maximum number of moves required to solve the cube using this method. I acknowledge the problem lies on my side, I just did not find it yet.

The discrepancies are in the initialization values I get in prune tables for stages 1-3 (stage 4 agrees with the sources I used). I also find very small percentage of cube configurations that require 46 moves (single move is defined as a quarter (90 degrees) or double (180 degrees) turn) to solve. My average solution length is 37 moves while sources provide 31. I think this all comes down to the initialization of pruning tables for stages 1-3. It was also not mentioned that to move from stage 3 to 4, before using IDA tree search aided by prune table, the corners must be solved using double turn moves only. The maximum distance between G3 and solved corners is known to be no more than 4. Therefore a tree search with the depth=4 must be performed to find solved corners configuration before proceeding to stage 4.
The prune tables generation relies on functions that can convert certain cube configurations to a unique integer value (index in prune table) and from the integer value back to the cube configuration (which is not a full cube state, but just the part of the state being examined at given stage, e.g.: edges orientation or location of LR edges in the permutation array). My guess is that one of my conversion functions used in prune tables generation for stages 1-3 does not work correctly.

Here are some of the the results of 100,000 steps test cases I ran on my T45 implementation:

Test succeeded.
Average time      : 0.0947605 seconds.
Average length    : 37 steps.
Longest solution  : 46 steps.
Shortest solution : 11 steps.

Test succeeded.
Average time      : 0.0865535 seconds.
Average length    : 37 steps.
Longest solution  : 46 steps.
Shortest solution : 22 steps.
# of 45+ solutions: 7

The source code is available for download here: Marek's Public Share @SkyDrive
Look for ZIP archive: RubikSrc_3.0.zip

Example use:

rubik -a 4 -c -C -N -w URRFBRBBRUULBBRUiDiRRFRiLBBUUFF

Above command will solve super-flip cube configuration using T45 algorithm.

rubik -a 3 -c -s 20 -m

Above will run the program in interactive mode, initially scramble cube 20 times, set the algorithm to human layer-by-layer, do not use cache of known solutions (cache is used by brute force or heuristic search algorithms and is pretty much useless with layer-by-layer or T45 which uses its own cache of prune tables).

rubik -a 4 -c -N -C -s 33 -t 100000 > rubik_tc_a4_100000.txt

Above command will run 100,000 steps test case on T45 algorithm and redirect output to file.
The test case follows following algorithm:
- scramble the cube (in above example, 33 moves), save the scrambled cube state
- run solve algorithm, save the solution steps
- restore the cube state to the saved cube from the initial scramble step
- run the solution steps obtained from algorithm being tested through the cube engine
- if the cube is solved, the solution worked, algorithm works as expected

Please note that if the cache files do not exist, program will generate prune tables and save them in cache at current working directory at the 1st run. This process may take several minutes. Each next run uses saved cache and initialization is then much faster.






This is still work in progress. I need to clean up the code, remove non-working algorithms, correct T45 so it is a true T45 (and not T46 in some cases), make command line parser to accept double-turn moves (U2, F2 etc.) and so on.
However at this stage it is usable and presentable, therefore I share this project with community hoping it will be useful and enjoyable.
Thanks for reading.

Marek Karcz
5/5/2015

Credits/sources:
"Building and Solving Rubik's Cube in Mathworks R Matlab R." - by Joren Heit

3 comments:

  1. I found some problems in code and corrected them. I also made Linux and AIX portability refactoring. Remember to comment-out a DOS definition in Cube.h when compiling on non-windows platform.
    New version 3.0.1, archive file RubikSrc_301.zip is available for download under the same SkyDrive folder.

    ReplyDelete
  2. New version 3.0.9 is now available for download as a source code (RubikSrc_309.zip, look in the SkyDrive folder to which URL is provided in the article above).
    The new features and bug fixes:
    - Server mode (UNIX/AIX/Linux).
    - Memory leak corrected.
    - The solution path post-processing/optimization improved for layer-by-layer algorithm and introduced for T45 algorithm. Up to 10% improvement - shorter solution paths (number of moves needed to solve the cube).
    - Scripts and utilities for testing and statistics.

    ReplyDelete
  3. New version 3.1.7 is available:
    - bug fixes
    - generating random cubes definitions
    - prune tables initialization corrected, some optimizations added: the average solution length down from 35 to 31.6 on average

    ReplyDelete