by Sandro Maffiodo
How small can be a Rubik's cube solver?
This is a Rubik's cube solver.
The program solves a 3x3 Rubik's cube using a modified version of the method "layer by layer" (explained here: http://solvethecube.com/).
This is not a bruteforce solver. One bruteforce solver takes too time to find a solution... This program will find its in the blink of an eye.
The program reads a scramble sequence from stdin and writes the solution to stdout. The program will not solve the cube by reversing the scramble sequence (this would be too simple!!). It uses the method "layer by layer", and is capable of solving any permutation of the cube (one of 43252003274489856000 permutations).
This program works with a cube with a standard color schema.
$(CC) prog.c -D_= -o prog
if you want to see a graphic rappresentation of the cube, before the scramble, after scramble, and when it is completed, build the program like this:
$(CC) prog.c -include "dump.c" -o prog
The program starts with a solved cube. You need to type a sequence of moves to scramble the cube.
You can get a scramble sequence from http://www.jaapsch.net/scramble_cube.htm or use one of these scramble:
L U B2 F' L' R B2 L' R2 F' R F2 D U' B D U' B U F'
B2 F' L U' F D' B D2 U2 R' U2 F' U F2 D' U2 B D2 U R'
L' R2 D2 U F2 D2 U2 L2 R2 B2 F D B2 U' L2 R2 D' B F' D
R U B2 L2 U2 F R'
The starts position of your cube MUST BE with the GREEN FACE on front and the WHITE FACE on top. The scramble sequence MUST NOT include the rotation moves: x, y, z.
You can type the scramble to the program using EOF (CTRL+D) to terminate the sequence, or use a pipe:
$ echo "R U B2 L2 U2 F R'" | ./prog
The build process will generate some warnings (30~ on clang):
The sourcecode of the program uses TAB, VERTICALTAB and FORMFEED without escaping them. This is my trick to fit the size limits imposed by the contest.
This is what the solver do:
The solution given by the program is not optimized and, sometimes, can generate boring sequences of moves:
x' (1 counterclockwise rotation on X axis)
the program can generate
x'x'x'x'x' (5 counterclockwise rotations on the X axis)
If you want, you can optimize the program output by using some sed transformations. Have fun!