Conway's Game Of Life - C#

I love Conway's Game Of Life, a fact that I can't deny. I implemented several rather unsophisticated simulators in various programming languages: MOS 6502 assembly, C64 BASIC, Apple Soft BASIC, C, C#. Today I'd like to write about my C# port.

Back in 2004 I started to learn C# and .NET. This process spawned several programming projects. The first was Game Of Life simulator. I recently brought that project back from hibernation. I originally developed the program under SharpDevelop IDE. That IDE is still being developed and supported. I downloaded the newest version 5 and Microsoft's .NET developer's pack for version 4.5 of .NET. I fixed few bugs and made some improvements and I built a new version. It performs nicely. It is so good to watch those colonies evolve again. There is something hypnotic about watching a running GOL colony simulation, any nerd can confirm that.

Anyway, few words about the game:

It was invented by mathematician John Horton Conway in 1970. It is a game that plays itself, since this is a cellular automaton, the evolution of the game is determined by initial state and the rules that govern the creation of subsequent generations of the colony created in each time tick.
The universe of a game is a 2-dimensional grid of cells which can be in 2 possible states: dead or alive. Each cell interacts with 8 adjacent neighbors and depending on the number of alive neighbors, the state of the cell may or may not change in the next generation.

The following rules govern the next state of the cell:

• Each alive cell that has one or no alive neighbors will die from loneliness.
• Each alive cell that has two or three alive neighbors will remain alive.
• In each empty (dead) cell with exactly 3 neighbors will change the state to alive (reproduction).
• Each alive cell with 4 or more neighbors will die from overcrowding.

My program allows to save the colony in disk file and load one from file. I developed my own colony file plain text format so for now unfortunately you can not download and use directly any popular on the internet colonies in common formats like 'plaintext' or RLE. This is something that you esteemed reader can perhaps do on your own if you are not afraid of doing some programming (write your own converter or alter my program) or you may need to wait until I add this feature in the future version.
Program lets the user to edit the colony by clicking on the colony view area directly. Click on the cell to flip its state. Clicking on the colony view area automatically stops the simulation which can be restarted after modifications are complete. Saving the colony before running simulation is recommended.

Other features include:

• Individual colony properties/setup file.
• Zoom range 1-20.
• Optional painting of the grid lines (slow).
• Optional painting the dying cells (slow).
• Possibility of changing the colony size.
• Random colony generator.
• Initial population number limit.
• Single step mode.

In future versions I plan to improve GUI. I will also add support for one or more of the popular GOL colony file formats. Performance also may need some optimization, if I ever want to increase the maximum size of the colony or perhaps implement a dynamically extendable colony size, which may require some more advanced programming techniques to maintain proper rendering speed for huge colonies.

Download here (GameOfLife.zip) and enjoy.
(The most current version as of 10/14/2015 is 5.0.1.18 - GameOfLife_501_18.zip).

Sources:

• Wikipedia
• Google + article
• Plaintext file format.
• RLE file format.
• Cellular Automata File Formats.

Cheers!

8/20/2015
Marek K

Game of Tic-Tac-Toe.

It would probably be difficult to find anybody that has never played a classic 3x3 Tic-Tac-Toe game. I remember that at school it was one of the time killing methods during boring activities we were made to attend. We played many different variants of the game, mostly going beyond the 3x3 boundaries (we played often 5x5 variant or until the space was available on the piece of paper). Anyway, while experimenting on my C-128 with CP/M system and Aztec C compiler, I thought that Tic-Tac-Toe would be a good project for a game running in such environment as it requires no graphics, text mode being sufficient for presentation and player input. Well, I started the development on that platform, however the cycles of code changing/compiling/testing took awfully long time (due to CP/M and compiler slowness on C-128), therefore I decided to move the development to a modern computer. This proved a fun casual programming project, the goal was to create an unbeatable computer AI playing classic 3x3 Tic-Tac-Toe game.

The game rules:

Players play on a 3x3 square board:

 In the empty spaces of the board, using pencils on a paper (or a computer generated board) players put their symbols taking turns. One player plays with 'O' (circle) and another with 'X' - cross. In my version if human player selects 'O' symbol, he/she begins the game. Otherwise, computer AI performs the first move. It does not matter which symbol really starts the game, but we must establish some laws. A different approach could be to select the 1-st player randomly and this would also be fine.
The goal of the game is to win by putting the player's 3 symbols in a row in any horizontal, vertical or diagonal line. This game, if both players make no mistakes and play with proper tactic, can not be lost or won and shall always end-up in a tie.
For the benefit of this article and explanation of the algorithm, I will name the board columns A, B C and rows 1, 2 and 3. The corner spots are A1, A3, C1, C3. The edge spots are B1, A2, C2 and B3. The center spot is B2.

Because the development started on a limited in resources platform (CP/M OS, 8-bit hardware), I established some development directives to prevent the system running out of resources playing such a simple game, which would make the programmer look rather lame.

The rules are:

• Do not use recursion (stack limitations).
• Use as few local function variables as possible (stack limitations).
• Game works in text mode (CP/M limitation) in a scroll-down fashion (not using potentially incompatible terminal control characters, aimed for portability here).

When approaching such problem from programming perspective I always use top-down programming method. I write main() function first and invoke whatever functions I might need, implemented or not, inventing them along the way. Later I proceed to implement the rest of the needed functions using exactly the same method. I repeat the process until all the required functions are implemented. Then it is time to make the code to compile/link properly. At this point the process of debugging starts which consists of the cycles of testing/debugging/correcting code until the program is up to my expectations and bugs free.

As with any game, we should start with the main program loop, which basically consists of initialization function, presentation function, user input function, game logic function and game-end test.

In pseudo-code, we might end-up with something like this:

initialize_game
repeat until game_not_ended
begin
   present_game
   get_player_move
   if game_ended
   then
      show_score
      if play_again
      then
         initialize_game
      else
         end_loop
      end-if
   end-if
   computer_move
   if game_ended
   then
      show_score
      if play_again
      then
         initialize_game
      else
         end_loop
      end-if
   end-if
end 
say_good_bye
end_app

The C implementation may look similar to this:

main()
{
    int n;

    banner();
    init_game();

    do {
       show_board();
       next_move();
       n = end_game();
       if (0 == n) {
          comp_move();
          n = end_game();
       }
       if (1 == n) {
          banner();
          init_game();
       }
    } while(0 == n || 1 == n);
    bye();
}

This part of course is not too difficult, even for a beginner. The devil is in details, as they say. The first two of the development directives that I made before imply that the game logic should be based on a simple heuristic evaluation. Computer should perform analysis of all possible moves in the next turn, assign the score to each possibility and then pick the best move based on this evaluation. That function is comp_move(), 

Before implementation, I needed to design a clear strategy based on the experience of playing the game and on game rules. The strategy I assumed is as follows (remember that computer will be only looking one move ahead and base its decision on existing game state):

• The top most important directive is to prevent other player from winning.
• Next priority is to favor the center spot, if not yet taken, make the move there.
• If none of the above conditions occurred, then if the human player already occupies two opposite corners but remaining corners are free, make move to any edge spot.

       This hypothetical situation occurs when player has symbols in spots 
       A1, C3  and spots A3, C1 are free OR the opposite/symmetrical (player:
       A3, C1, free: A1, C3). 

       See graphical representation below:

      

• If the player symbol occupies an edge and one of the corners on the opposite side of the board, the preferred position is a corner spot next to the player occupied edge spot and opposite to the player occupied corner spot.

       The above pattern occurs if player has one of A1, A3 combined with 
       C2 OR one of C1, C3 combined with A2 OR one of A1, C1 combined with 
       B3 OR one of A3, C3 combined with B1.

       See graphical representation below:

      

• If player played a corner, also play a corner.
• If player symbol occupies 2 adjacent edge spots, take a corner between them.

 

• if player played an edge, also play an edge.

Above tactics are applied in the order as listed, from top to bottom.
Below is the code if my implementation:

/*
 * A computer move routine (AI).
 * Looks unbeatable :-) (needs more testing).
 */
comp_move()
{
   int i, j, k, l, m, n;

   k = l = -1; /* indexes of computer move */
   m = n = 0;  /* game evaluation results/scores for computer and player */

   /* evaluate heuristically each possible next move for player and computer */
   /* i - column index, j - row index */
   for (i=0; i<3; i++) {
      for (j=0; j<3; j++) {
         if (' ' == board[i][j]) {
            board[i][j] = plr_sym; /* simulate player's move */
            /* if player's move would result in winning, give this position */
            /* highest score to prevent human player from winning */
            if (cmc > 0 && n < 100 && 1 == game_done()) {
                n = 100; k = i;    l = j;
            } /* next - favor the center spot */
            else if (n < 50 && i == 1 && j == 1) {
                n = 50;    k = l = 1;
            } /* next - if human player occupies two opposite corners */
                          /* and remaining corners are free, prefer edge spot */
            else if (cmc > 0 && n < 25 && abs(j-i) == 1 &&
                       ((board[0][0] == plr_sym && board[2][2] == plr_sym
                               && board[0][2] == ' ' && board[2][0] == ' ')
                       || (board[2][0] == plr_sym && board[0][2] == plr_sym
                              && board[0][0] == ' ' && board[2][2] == ' '))) {
                n = 25;    k = i; l = j;
            } /* next - if player has a corner and edge on opposite sides */
              /* take the corner spot next to the player's edge piece */
            else if (cmc > 0 && n < 20 && abs(j-i) == 2
                               && board[i][1] == plr_sym
                              && ((i == 2 && (board[0][0] == plr_sym
                                 || board[0][2] == plr_sym))
                                 || (i == 0 && (board[2][0] == plr_sym)
                                 || board[2][2] == plr_sym))) {
                n = 20; k = i; l = j;
            } /* next - similar but simmetrical situation */
            else if (cmc > 0 && n < 20 && abs(j-i) == 2
                                   && board[1][j] == plr_sym
                                   && ((j == 2 && (board[0][0] == plr_sym
                                   || board[2][0] == plr_sym))
                                   || (j == 0 && (board[0][2] == plr_sym)
                                   || board[2][2] == plr_sym))) {
                n = 20; k = i; l = j;
            }
            /* next - prefer corner spots if this is not the 1-st move */
            /* and player also played corner */
            else if (cmc != 0 && n < 12 && i != 1 && j != 1 && plr_nm_col != 1
                                         && plr_nm_row !=1) {
                n = 12; k = i; l = j;
            } /* next - if player occupies 2 adjacent edge spots and */
              /* the remaining edge spots are free, take corner between them */
            else if (cmc > 0 && n < 6 && i != 1 && j != 1
                         && board[i][1] == plr_sym && board[1][j] == plr_sym) {
                n = 6; k = i; l = j;
            } /* next - prefer edge spots if this is not 1-st move and */
              /* player also played edge */
            else if (cmc != 0 && n < 3 && abs(j-i) == 1
                               && abs(plr_nm_col-plr_nm_row) == 1) {
                n = 3; k = i; l = j;
            }
            board[i][j] = comp_sym; /* simulate computer move */
            m = eval_game(comp_sym); /* evaluate the current game */
            /* if computer move gets higher score than player move and other */
            /* preferred strategies then take precedence and assign new */
            /* computer move to current location [i,j] */
            if (m > n) {
                n = m; k = i; l = j;
            }
            board[i][j] = ' '; /* restore board to previous state */
         }
      }
   }
   /* if move indexes were assigned, perform this move */
   if (0 <= k) {
        cmc++; mvc++;
       board[k][l] = comp_sym;
       printf("Computer move: %c%d\n", (char)('A'+k), l+1);
   }
}

There is not much more to say about this simple game.
Download from here and enjoy not winning it ever :-)
Game runs in text mode (DOS) and should work under any modern version of windows system.
The program is written in C and is highly portable and will compile on Windows, Linux, AIX and even under CP/M 3.0 (Aztec C).

Cheers!

8/20/2015
Marek K

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:

Jaap's Puzzle Page

Thistlethwaite 45 implementation (C)

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