by Sandro Maffiodo

smaffer@gmail.com

www.assezeta.com/sandromaffiodo

**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):

**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.

This is what the solver do:

- starts by orienting the cube to my starting position
- solves the red cross
- solves the first layer (red face)
- solves the second layer
- solves the orange cross
- solves the orange face (top face)
- exchanges the top corners
- complete the cube by rotating the top edges

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!**