Solve the (Rubiks) Pocket Cube

Question

Your task

.. is to do what Brian Fantana apparently couldn't do, and solve the 2x2x2 Rubik's Cube.

The Layout

- -   A B   - -   - -
- -   C D   - -   - -

E F   G H   I J   K L
M N   O P   Q R   S T

- -   U V   - -   - -
- -   W X   - -   - -

And will be given to you via stdin or the command line (your choice - please specify in your answer) in the format:

ABCDEFGHIJKLMNOPQRSTUVWX

Note that A-D make up the U-face(up), EFMN make up the L-face(left), GHOP make up the F-face(front), IJQR make up the R-face(right), KLST make up the B-face(back), and U-X make up the D-face(down).

There will be six unique characters representing each color, but they may vary, so prepare for any combination of 6 ascii characters to be used for each color.

Specifications

• Your code should output a solution using only the Right (R), Upper (U), and Front(F) faces, and should use the standard notation: R , R' , R2 , U , U' , U2 , F , F' , F2. You can find more info here. The restriction to the RUF subset is standard for the 2x2 cube (Hint: treat the bottom-back-left corner as a fixed base to work from).
• Your code must be capable of solving all possible permutations of the pocket cube.
• Each solution should take less than 30 seconds to complete.
• Each solution should be less than 30 moves.
• A bonus of -20% will be given for solutions always providing answers less than 20 moves (please advertise it in your answer so I can do a thorough check for it)
• A bonus of -50% will be given for code which always provides an optimal solution. - Again, please advertise in your answer
• Solutions must not contain two consecutive moves on the same face, because they can be easily combined into one move.
• Solutions can optionally contain a single space - and only a single space - between each move.
• The whole solution sequence, if necessary, may be contained in a pair of parentheses, quotation marks, braces, brackets, or carets, but no other extraneous output is allowed.
• Please provide either a briefly commented version of your code or a thorough explanation of your code.
• No use of external files. This includes internet, data tables, and libraries/packages made for this sort of problem.
• Shortest code by byte count wins.
• Winner chosen Wednesday (July 30, 2014).

Answer 1

Python 2.7: 544 bytes -50% = 272 bytes**

import sys;o=''.join;r=range;a=sys.argv[1];a=o([(' ',x)[x in a[12]+a[19]+a[22]] for x in a]);v={a:''};w={' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:''}
m=lambda a,k:o([a[([0x55a5498531bb9ac58d10a98a4788e0,0xbdab49ca307b9ac2916a4a0e608c02,0xbd9109ca233beac5a92233a842b420][k]>>5*i)%32] for i in r(24)])
def z(d,h):
 t={}
 for s in d[0]:
  if s in d[1]:print d[h][s]+d[1-h][s];exit()
  n=[d[0][s],'']
  for k in r(3):
   for j in r(3):s=m(s,k);t[s]=n[h]+'RUF'[k]+" 2'"[(j,2-j)[h]]+n[1-h]
   s=m(s,k)
 d[0]=t;return d
while 1:v,w=z([v,w],0);w,v=z([w,v],1)

Stackexchange replaces tabs with multiple whitespaces. So technical this version has 549 bytes. Just replace the first two spaces in the lines 6-10 with a tabulator.

Idea behind my program: My first idea was a breath first search. But this took too long. Around 2 minutes for a hard (11 move optimal) scramble. So I decided to approach the problem from both sides. I use two sets. I generate sequentially all states with distance 1,2,3,... to the scramble and save them in set1, and at the same time all states with distance 1,2,3,... to the solved state and save them in set2. The first time a state is in both sets, we found the solution.

For this I need the colors of the solved cube, which are not known. The characters 13, 20 and 23 define the left, back and down color. But these 3 colors are sufficient to represent the cube. I simply replace the other 3 colors with whitespaces and I can represent my solved state as '____ll____bbll____dddd'.

Oh, and for shortening the permutations I used an idea from https://codegolf.stackexchange.com/a/34651/29577

Ungolfed version:

import sys

#define permutations for R,U,F
permutation = [[0,7,2,15,4,5,6,21,16,8,3,11,12,13,14,23,17,9,1,19,20,18,22,10],
            [2,0,3,1,6,7,8,9,10,11,4,5,12,13,14,15,16,17,18,19,20,21,22,23],
            [0,1,13,5,4,20,14,6,2,9,10,11,12,21,15,7,3,17,18,19,16,8,22,23]]

def applyMove(state, move):
    return ''.join([state[i] for i in permutation[move]])

scramble = sys.argv[1]
#remove up,front,rigth colors
scramble = ''.join([(' ', x)[x in scramble[12]+scramble[19]+scramble[22]] for x in scramble])
solved = ' '*4+scramble[12]*2+' '*4+scramble[19]*2+scramble[12]*2+' '*4+scramble[19]*2+scramble[22]*4

dict1 = {scramble: ''} #stores states with dist 0,1,2,... from the scramble
dict2 = {solved: ''} #stores states with dist 0,1,2,... from the solved state

moveName = 'RUF'
turnName = " 2'"

for i in range(6):
    tmp = {}
    for state in dict1:
        if state in dict2:
            #solution found
            print dict1[state] + dict2[state]
            exit()
        moveString = dict1[state]
        #do all 9 moves
        for move in range(3):
            for turn in range(3):
                state = applyMove(state, move)
                tmp[state] = moveString + moveName[move] + turnName[turn]
            state = applyMove(state, move)
    dict1 = tmp
    tmp = {}
    for state in dict2:
        if state in dict1:
            #solution found
            print dict1[state] + dict2[state]
            exit()
        moveString = dict2[state]
        #do all 9 moves
        for move in range(3):
            for turn in range(3):
                state = applyMove(state, move)
                tmp[state] = moveName[move] + turnName[2 - turn] + moveString
            state = applyMove(state, move)
    dict2 = tmp

I'm pretty happy with the result, because I'm quite new to Python. This is one of my first python programs.

edit: half a year later: 427 - 50% = 213.5

Got a little bit more experience in Python and in golfing. So I revised my original code and could save more than 100 character.

import sys;o=''.join;a=sys.argv[1];d=[{o((' ',x)[x in a[12]+a[19]+a[22]]for x in a):[]},{' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:[]}]
for h in[0,1]*6:
 for s,x in d[h].items():
  for y in range(12):
   d[h][s]=x+[y-[1,-1,1,3][h*y%4]];
   if s in d[1-h]:print o('RUF'[x/4]+" 2'"[x%4]for x in d[0][s]+d[1][s][::-1]);exit()
   s=o(s[ord(c)-97]for c in'acahabcdnpbfegefhugiovjgqkciljdeklflmmmnnvoopxphrqdjrrbsstttuuqsviwwwkxx'[y/4::3])

I basically use the exact same approach. The biggest change is, that I don't define a function anymore. Instead of

def z(d,h):
 for s in d[0]:
  if s in d[1]:...
while 1:v,w=z([v,w],0);w,v=z([w,v],1)

I can do

for h in[0,1]*6:
 for s in d[h]:
  if s in d[1-h]:...

Also I changed the move lamda a little bit. First shortend, and then integrated the code directly, since the function call only appears once.

I keep for each state a list of numbers between 0 and 11, to represent the moves, instead of a string containing the moves. The numbers are converted at the very end.

Also I combined the two for-loops 'for k in r(3):for j in r(3): into one for y in r(12). Therefore I also have to do the moves U4, R4, F4. Of course such a move doesn't appear in the shortest solution, so " 2'"[x%4] works. (If x % 4 == 3, there would be a index out of range exception)

It's also a little bit faster, since I look for the entry in the second set earlier. About 0.5 second for a 11 move solution.

Answer 2

C, 366 - 50% optimal bonus = 183

char c[99],t[3][26]={"ZGONFZCPTEZBHUMZ","ZIQPHZRUGAZJWOCZ","ZACB@ZJHFDZKIGEZ"};r=20;f(int m,int n){int e,i,j;for(i=4;i--;){for(j=15;j--;)c[t[n][j+1]]=c[t[n][j]];c[m]="FRU"[n],c[m+1]="4'2 "[i],c[m+2]=0;for(e=0,j=68;j<76;j++) e+= (c[j]!=c[j+8]) + (c[j]!=c[j^1]);i&&e&&e<45-m*2&m<r?f(m+2,(n+1)%3),f(m+2,(n+2)%3):e||(puts(c),r=m);}}main(){scanf("%s",c+64);f(0,2),f(0,1),f(0,0);}

Using recursion, the program searches through a tree of up to 11 moves deep (the max length of an optimal soluton according to http://en.wikipedia.org/wiki/Pocket_Cube and the page mentioned below) and when it finds a solution it prints it (up to 22 characters long, tracked by function argument m.) The order used is a kind of dictionary order, where all routes begining U,U2,U' are searched before any routes beginning R or F are searched. Thus it does not necessarily find the optimal solution first.

When a solution is printed, r is made equal to m which ensures that only equal or shorter solutions will be printed afterwards. Putting r=m-2 costs an extra 2 characters but ensures only one solution of each length found (down to optimal) is printed. If you want it to ONLY show the optimal solution, the best solution found so far must be stored to a variable, and the optimal solution printed at the end of the program (this would cost about an extra 15 characters.)

the input is read into the array c[] from index 64 onwards. This is necessary in order to use alphabet characters in the movetable. The symbols @ through W are used instead of A through X per the question, because it is necessary to start on an even number to make the test for solutions work. c['Z'] is also used for temporary storage, because in order to perform 4-fold rotation a total of 5 assignments are needed. Because the first part of c[] is unused, it is available to store the solution (which is terminated with a zero byte, like all C strings.)

for(i..) goes through a sequence of 4 quarterturns of the face specified by n.

The first for(j..) performs the actual swapping according to table t[].

To test if the cube is solved, it is only necessary to check the four side faces. The pieces URF and DFR can be distinguised even with the U and D stickers removed, because one piece reads XRF in the clockwise direction and the other XFR. If the two pieces are interchanged so that U shows on the down face and vice versa, the F colour will show on the right face and vice versa.

The second for(j..) counts the number of mismatches on the four side faces. For example for the front face it compares G & O, H & P, and G & H (twice.) If e==0, the cube is solved. If e<9 or e<13, it might be possible to solve the cube in the next one move or 2 moves respectively. Otherwise it definitely not possible to solve the cube in this number of moves. In order to save time, this heuristic is used to prune the search tree and avoid wasting time on many of those branches of depth 10 or 11 which will be unsuccesful. Expressed as a formula, this becomes e<45-m*2.

Ungolfed Code

char c[99],t[3][26]={"ZGONFZCPTEZBHUMZ","ZIQPHZRUGAZJWOCZ","ZACB@ZJHFDZKIGEZ"};
r=20;                                                       //All moves are output as 2 characters. The index of the last move of the longest solution (11 moves) shall be 20.

f(int m,int n){                                             //perform a cycle through four 1/4 turns of the face specified in n. The index of the move reported in the solution is m.
  int e,i,j;                                                //e is for counting mismatches. i loops through the four 1/4 turns. j performs other functions.
  for(i=4;i--;){

    for(j=15;j--;)c[t[n][j+1]]=c[t[n][j]];                  //A 1/4 turn is performed as three 4-sticker rotations of the type z=a;a=b;b=c;c=d;d=z using the data in the movetable t[][]

    c[m]="FRU"[n],c[m+1]="4'2 "[i],c[m+2]=0;                //Write to the output in c[] the face to be turned and the number of 1/4 turns. Terminate with a zero byte to overwrite any longer solution that may have been found before. 

    for(e=0,j=68;j<76;j++)e+=(c[j]!=c[j+8])+(c[j]!=c[j^1]); //Compare each sticker of the top row of the side faces (64+4 through 64+11) with the stickers below and beside it. Count the number of mismatches.

    i && e && e<45-m*2 & m<r?                               //if the number of 1/4turns is not 4 AND the cube is not solved AND the heuristic (as described in the text) is good AND a shorter solution has not already been found,
      f(m+2,(n+1)%3), f(m+2,(n+2)%3):                       //deepen the search to another faceturn of the other two faces. 
      e||(puts(c),r=m);                                     //otherwise, if a solution has been found, print the solution and reduce the value of r to the new max solution length.
  } 
}

main(){
  scanf("%s",c+64);                                         //scan in the current cube state to c[] at index 64.
  f(0,2),f(0,1),f(0,0);                                     //call f() three times to search for solutions beginning with U R and F.
}

Performance

The program was tested with patterns 1 to 13 at http://www.jaapsch.net/puzzles/cube2.htm

Results as follows give the timing on my machine to find ALL optimal solutions (for the curious-minded.) Also for the more complex positions, the timing is given for the 2-byte modification mentioned above which finds just one optimal solution. For this timings are given both to find the first solution and for the program to terminate. The solutions given (which are generally different to the solutions obtained by reversing the generators on the linked page) have been verified with an online cube simulator.

U 4 (1 move) horizontal flags (not mirror symmetric)
1 solution 1 sec

U2 (1 move) 4 horizontal flags (mirror symmetric)
1 solution 1 sec

F2 R2 F2 (3 moves) 4 vertical flags  
UUUULRBFRLFBLRBFRLFBDDDD 2 solutions 1 sec

U2 F2 R2 U2 (4 moves) Supertwist; 6 flags
DDUURRBFRRFBLLBFLLFBUUDD 3 solutions 1 sec

U F2 U2 R2 U (5 moves) 4 vertical flags, 2 checkerboards
UDDULBRFRFLBLBRFRFLBUDDU 2 solutions 1 sec

R2 F2 R2 U2 (4 moves) 4 checkerboards
UUUURLFBLRBFLRBFRLFBDDDD 4 solutions 1 sec

R U2 R' F2 R U' R2 U F2 U' (10 moves) Cube in cube
FFFUDDRFRULLLDRRUULBBBDB 18 solutions 26 sec; 1 solution U F2U'R2U R'F2R U2R' 1,13 sec 

R F U' R2 U F' R U F2 R2 (10 moves) Cube in cube 2
DDDUFFLFRBRRLFLLBBRBUUDU 8 solutions 28 sec; 1 solution R F U'R2U F'R U F2R2 12,21 sec 

U R F2 U R F2 R U F' R (10 moves)3-Cycle
UFFULDRFRULBLLFRURBBDBDD 45 solutions 26 sec; 1 solution U R'F U'F'R'F2U R F2 8,14 sec 

U R U' R2 U' R' F' U F2 R F' (11 moves) Column turn
UUUDLLFRFRBBLLFRFRBBDUDD many solutions 29 sec; 1 solution U R U'F U2R F'R'F'U2F' 3,27 sec 

F' U R' F2 U' R F U R2 U R' (11 moves)Corner swap
UUUURLFBLRBFLLFFRRBBDDDD 29 sec 24 solutions; 1 solution R U'F R U'R2U'F'R'U F2 12,28 sec

U F2 U' (3 moves) Zig-zag 
UDUDLLFRFFLBLBRRFRBBUUDD 1 solution 1 sec 

U' F2 U2 R2 U' F2 U2 R2 U' (9 moves) 2 Checkerboards, 4 L
DUUDLLFBRRBFLRFFRLBBUDDU 8 solutions 13 sec; 1 solution U F2U2R2U R2U2F2U' 1,5 sec