KUBRIK

by Sandro Maffiodo

smaffer@gmail.com

www.assezeta.com/sandromaffiodo

OVERVIEW

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.

BUILD

$(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

RUN

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

REMARK

The build process will generate some warnings (30~ on clang):

• type specifier missing, defaults to 'int' : this is to save some tokens and fit the size limits of the contest
• format string is not a string literal : this is safe (trust me) The generated format string does not contain the '%' character
• using the result of an assignment as a condition without parentheses: becouse while(c=getchar()) is not evil

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.

HOW IT WORK

This is what the solver do:

1. starts by orienting the cube to my starting position
2. solves the red cross
3. solves the first layer (red face)
4. solves the second layer
5. solves the orange cross
6. solves the orange face (top face)
7. exchanges the top corners
8. complete the cube by rotating the top edges

NOTE

The solution given by the program is not optimized and, sometimes, can generate boring sequences of moves:

instead of 
    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!