Python 1166 bytes
A considerable amount of whitespace has been left for the sake of readability. Size is measured after removing this whitespace, and changing various indentation levels to Tab, Tab Space, Tab Tab, etc. I've also avoided any golfing which affected the performance too drastically.
T=[]
S=[0]*20,'QTRXadbhEIFJUVZYeijf',0
I='FBRLUD'
G=[(~i%8,i/8-4)for i in map(ord,'ouf|/[bPcU`Dkqbx-Y:(+=P4cyrh=I;-(:R6')]
R=range
def M(o,s,p):
z=~p/2%-3;k=1
for i,j in G[p::6]:i*=k;j*=k;o[i],o[j]=o[j]-z,o[i]+z;s[i],s[j]=s[j],s[i];k=-k
N=lambda p:sum([i<<i for i in R(4)for j in R(i)if p[j]<p[i]])
def H(i,t,s,n=0,d=()):
if i>4:n=N(s[2-i::2]+s[7+i::2])*84+N(s[i&1::2])*6+divmod(N(s[8:]),24)[i&1]
elif i>3:
for j in s:l='UZifVYje'.find(j);t[l]=i;d+=(l-4,)[l<4:];n-=~i<<i;i+=l<4
n+=N([t[j]^t[d[3]]for j in d])
elif i>1:
for j in s:n+=n+[j<'K',j in'QRab'][i&1]
for j in t[13*i:][:11]:n+=j%(2+i)-n*~i
return n
def P(i,m,t,s,l=''):
for j in~-i,i:
if T[j][H(j,t,s)]<m:return
if~m<0:print l;return t,s
for p in R(6):
u=t[:];v=s[:]
for n in 1,2,3:
M(u,v,p);r=p<n%2*i or P(i,m+1,u,v,l+I[p]+`n`)
if r>1:return r
s=raw_input().split()
o=[-(p[-1]in'UD')or p[0]in'RL'or p[1]in'UD'for p in s]
s=[chr(64+sum(1<<I.find(a)for a in x))for x in s]
for i in R(7):
m=0;C={};T+=C,;x=[S]
for j,k,d in x:
h=H(i,j,k)
for p in R(C.get(h,6)):
C[h]=d;u=j[:];v=list(k)
for n in i,0,i:M(u,v,p);x+=[(u[:],v[:],d-1)]*(p|1>n)
if~i&1:
while[]>d:d=P(i,m,o,s);m-=1
o,s=d
Sample usage:
$ more in.dat
RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU
$ pypy rubiks.py < in.dat
F3R1U3D3B1
F2R1F2R3F2U1R1L1
R2U3F2U3F2U1R2U3R2U1
F2L2B2R2U2L2D2L2F2
This is an implementation of Thistlethwaite's Algorithm, using an IDA* search to solve for each step. Because all of the heuristic tables need to be calculated on the fly, several compromises have been made, usually breaking a heuristic into two or more fairly equal size parts. This makes the computation of the heuristic tables many hundreds of times faster, while slowing down the search phase, usually only slightly, but it can be significant depending on the initial cube state.
Variable Index
T - the main heuristic table.S - a solved cube state. Each individual piece is stored as a bit mask, represented as a character. A solved orientation vector is defined as the zero vector.I - the various twists, in the order that they are eliminated from the search space.G - the groups for twist permutations, stored as pairs to be swapped. Each byte in the compressed string encodes for one pair. Each twist needs six swaps: three for the edge cycle, and three for the corner cycle. The compressed string contains only printable ascii (char 32 to 126).M - a function that performs a move, given by G.N - converts a permutation of four objects to a number, for encoding purposes.H - calculates the heuristic value for the given cube state, used to lookup move depth from T.P - perform a search at a single depth of a single phase of the algorithm.s - the input cube's permutation state.o - the input cube's orientation vector.
Performance
Using Tomas Rokicki's data set, this script averaged 16.02 twists per solve (maximum 35), with an average time of 472ms (i5-3330 CPU @ 3.0 Ghz, PyPy 1.9.0). Minimum solve time was 233ms with a maximum of 2.97s, standard deviation 0.488. Using the scoring guidelines from the contest (white space is not counted, keywords and identifiers count as one byte for a length of 870), the overall score would have been 13,549.
For the last 46 cases (the random states), it averaged 30.83 twists per solve, with an average time of 721ms.
Notes on Thistlethwaite's Algorithm
For the benefit of anyone who might want to attempt an implementation of Thistlethwaite's Algorithm, here is a brief explanation.
The algorithm works on a very simple solution space reduction principle. That is, reduce the cube to a state in which a subset of twists are not necessary to solve it, reduce it to a smaller solution space, and then solve the remainder using only the few twists remaining.
Thistlethwaite originally suggested <L,R,F,B,U,D> → <L,R,F,B,U2,D2> → <L,R,F2,B2,U2,D2> → <L2,R2,F2,B2,U2,D2>. However, given the input format, I think it is easier to first reduce to <L,R,F2,B2,U,D> (no quarter turn F or B), and then <L2,R2,F2,B2,U,D> before finally reaching the half turn state. Instead of explaining exactly why this is, I think it will be evident after defining the criteria for each state.
<L,R,F,B,U,D> ⇒ <L,R,F2,B2,U,D>
In order to eliminate F and B quarter turns, only the edges must be oriented correctly. Gilles Roux has a very good explanation on his site of what 'correct' and 'incorrect' orientation is, so I'll leave the explaining to him. But basically, (and this is why this input format is so condusive to F and B elimination), an edge cubie is correctly oriented if it matches the following regex: [^RL][^UD]. A correct orientation is typically signified with a 0 and incorrect with 1. Basically U and D stickers may not appear on the R or L faces, or on the edges of the any U or D edge cubies, or they cannot be moved into place without requiring an F or B quarter twist.
<L,R,F2,B2,U,D> ⇒ <L2,R2,F2,B2,U,D>
Two criteria here. First, all corners must be oriented correctly, and second, each of the for middle layer cubies (FR, FL, BR, BL) must be somewhere in the middle layer. A corner orientation is very simply defined given the input format: the position of the first U or D. For example, URB has orientation 0 (correctly oriented), LDF has orientation 1, and LFU has orientation 2.
<L2,R2,F2,B2,U,D> ⇒ <L2,R2,F2,B2,U2,D2>
The criteria here is as follows: each face may only contain stickers from its face, or from the face directly opposite it. For example, on the U face there may only be U and D stickers, on the R face there may only be R and L stickers, on the F face there may only be F and B stickers, etc. The easiest way to ensure this is to check if each edge piece is in its 'slice', and each corner piece in its 'orbit'. Additionally, one needs to pay attention to edge-corner parity. Although, if you check only for corner parity, edge parity is also guaranteed, and vice versa.
How twists affect orientation
U and D twists affect neither the edge orientation, nor the corner orientation. The pieces may be swapped directly without updating the orientation vector.
R and L twists do not affect the edge orientation, but they do affect the corner orientation. Depending on how you define your cycle, the change in corner orientation will either be +1, +2, +1, +2 or +2, +1, +2, +1, all modulo 3. Note that R2 and L2 twists do not affect the corner orientation, as +1+2 is zero modulo 3, as is +2+1.
F and B affect both the edge orientations and corner orientations. Edge orientations become +1, +1, +1, +1 (mod 2), and corner orientations are the same as for R and L. Note that F2 and B2 affect neither the edge orientations, nor corner orientations.
