Solve a Rubik's Cube

From Rosetta Code
Solve a Rubik's Cube is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Create a program that is capable of solving a Rubik's Cube as efficiently as possible.

You may use any sort of input you wish.

Phix[edit]

cfop[edit]

Uses brute-force (width/highscore-first) Fridrich-steps (ie cross,f2l,oll,pll).
Not the fastest (see THRESHOLD) or shortest results (see thistlethwaite) but the code is pretty easy to follow.
The final stage (pll) would probably benefit the most from being replaced with standard algorithms.

--
-- demo\rosetta\rubik_cfop.exw
--
-- Each stage uses a workspace of moves tried so far, ranked by score.
-- We repeatedly take the best scoring so far and try more moves, storing
-- those results in a second/new workspace. The THRESHOLD value below
-- determines the minimum number we should examine before discarding a
-- workspace and switching to the new (one move longer) one. We only ever
-- switch on change of score, and obviously the first workspace is empty,
-- and the next new workspace has a maximum of 12 entries (+/-90 by 6),
-- both of which will force earlier switches.
--
constant THRESHOLD = 100000 -- 100000 -- very slow (100s), best results
-- 10000 -- slow (10s), reasonable results
-- 1000 -- fast (1s), fairly poor results
-- 100 -- (counter-productive/slower)
 
string init ="""
_____________---YYY--------
---YYY--------
---YYY--------
BBBRRRGGGOOO--
BBBRRRGGGOOO--
BBBRRRGGGOOO--
------WWW-----
------WWW-----
------WWW-----
 
"""
-- numbering:
-- 1..15: ---456--------\n
-- 16..30: ---901--------\n -- U
-- 31..45: ---456--------\n
-- 46..60: 678901234567--\n
-- 61..75: 123456789012--\n -- LFRB
-- 76..90: 678901234567--\n
-- 91..105: ------789-----\n
-- 106..120:------234-----\n -- D
-- 121..136:------789-----\n\n
 
if length(init)!=136 then ?9/0 end if
 
--
-- TIP: Wrap a cube with blank paper, and write
-- the numbers on it, to derive these sets.
--
constant centres = {20,62,65,68,71,113}
 
constant edges = {{ 4, 5, 6,57,56,55}, -- ie YYY/OOO
{ 6, 21, 36,54,53,52}, -- YYY/GGG
{ 34, 35, 36,49,50,51}, -- YYY/RRR
{ 4, 19, 34,46,47,48}, -- YYY/BBB
{ 51, 66, 81,52,67,82}, -- RRR/GGG
{ 54, 69, 84,55,70,85}, -- GGG/OOO
{ 57, 72, 87,46,61,76}, -- OOO/BBB
{ 48, 63, 78,49,64,79}, -- BBB/RRR
{ 97, 98, 99,82,83,84}, -- WWW/GGG
{ 99,114,129,85,86,87}, -- WWW/OOO
{127,128,129,78,77,76}, -- WWW/BBB
{ 97,112,127,81,80,79}} -- WWW/RRR
 
constant corners = {{ 4, 57,46},{34,48, 49},{36,51,52},{ 6,54,55},
-- YOB/UBL YBR/UFL YRG/UFR YGO/UBL
{76,129,87},{78,79,127},{81,82,97},{84,85,99}}
-- BWO/DBL BRW/DFL RGW/DFR GOW/DFL
 
constant facing_corners = {-16,-14,16,14}, -- (nb not 14,16)
facing_edges = {-15, 1,15,-1},
fce = facing_corners&facing_edges,
rotations = {
-- up (clockwise):
{{57,54,51,48}, -- clockwise corners
{46,55,52,49}, -- anticlockwise corners
{47,56,53,50}}, -- middle edges
-- left
{{ 4,49,127, 87},
{57,34, 79,129},
{19,64,128, 72}},
-- front
{{34,52, 97, 78},
{48,36, 82,127},
{35,67,112, 63}},
-- right
{{36,55,99,81},
{51, 6,85,97},
{21,70,98,66}},
-- back
{{ 6,46,129,84},
{54, 4, 76,99},
{ 5,61,114,69}},
-- down
{{82,85,76,79},
{81,84,87,78},
{83,86,77,80}}}
 
--Up/Left/Front/Right/Back/Down
enum U=1,L=2,F=3,/*R=4,*/B=5,D=6,Dbl=#08,Shift=#10
constant U2 = U+Dbl, F2 = F+Dbl, /*R2 = R+Dbl, B2 = B+Dbl,*/ D2 = D+Dbl,
Us = U+Shift, Fs = F+Shift, Bs = B+Shift, Rs = R+Shift, Ds = D+Shift
 
enum CROSS,F2L,OLL,PLL
 
integer f2l = 0 -- (28==done)
integer edge_score = 0 -- (0..12 for f2l [as U cleared],
-- 0..24 for oll and pll stages)
 
function score(string cube, integer stage)
integer res = 0, c, cc, k
f2l = 0
for i=1 to length(centres) do
c = centres[i]
cc = cube[c]
for j=1 to length(fce) do -- (the 8 next to c)
k = c+fce[j]
if cube[k]=cc then
res += 1
f2l += (stage>CROSS and k>=61)
end if
end for
end for
-- give extra credit for edges paired with corners
edge_score = 0 -- += (0|1|2) for the 12 edges:
if stage>CROSS then
for i=1 to length(edges) do
sequence ei = edges[i] -- as 123
-- -- 456
-- then if {1,4}=={2,5} then edge_score += 1,
-- plus if {2,5}=={3,6} then edge_score += 1.
edge_score += (cube[ei[1]]=cube[ei[2]] and
cube[ei[4]]=cube[ei[5]]) +
(cube[ei[2]]=cube[ei[3]] and
cube[ei[5]]=cube[ei[6]])
end for
end if
return res
end function
 
function oll_score(string cube)
-- (should only be invoked if f2l==28)
integer res = 0 -- (true if res=8)
integer cu = centres[U]
if cube[cu]!='Y' then ?9/0 end if
for i=1 to length(fce) do
integer fcei = fce[i]
res += (cube[cu+fcei]='Y')
end for
return res
end function
 
function rotate_face(string cube, integer face)
--
-- face is 1..6 for clockwise (ULFRBD),
-- plus #08(Dbl) for a 180 (clockwise),
-- plus #10(Shift) for anti-clockwise.
--
integer dbl = 1+(and_bits(face,Dbl)=Dbl)
bool cw = 1-floor(face/Shift)
face = remainder(face,Dbl)
integer cf = centres[face]
sequence rf = {sq_add(facing_corners,cf),
sq_add(facing_edges,cf)}
&rotations[face]
for d=1 to dbl do
for i=1 to length(rf) do
sequence rfi = rf[i]
if cw then rfi = reverse(rfi) end if
integer rfi1 = cube[rfi[1]]
for j=1 to 3 do
cube[rfi[j]] = cube[rfi[j+1]]
end for
cube[rfi[4]] = rfi1
end for
end for
return cube
end function
 
function apply_moves(string cube, sequence moves)
for i=1 to length(moves) do
cube = rotate_face(cube,moves[i])
end for
return cube
end function
 
constant ULFRBD = "ULFRBD"
 
function moves_to_string(sequence moves)
-- convert eg {1,20,11} to "UR'F2"
string res = ""
integer l = length(moves)
for i=1 to l do
integer face = moves[i]
integer dbl = and_bits(face,Dbl)=Dbl
bool anticw = floor(face/Shift)
face = remainder(face,Dbl)
res &= ULFRBD[face]
if dbl then
res &= '2'
elsif anticw then
res &= '\''
end if
end for
res &=sprintf(" (%d move%s) ",{l,iff(l=1?"":"s")})
return res
end function
 
--
-- The seen dictionary.
-- Without this, since it uses a breadth/highscore-first
-- algorithm, after f2l (for instance) it would probably
-- just do U and U' as the new high scores, forever.
-- (The THRESHOLD constant mitigates that to some extent)
--
integer seen = new_dict()
 
function solve_stage(string cube, integer stage)
atom t1 = time()+1
string moves = "", moves2
sequence workspace, w2,
init
integer wslen, high = 1,
s, c2c = 0, o = 0
bool done
 
if stage=CROSS then
--
-- first, blank out all corners, and
-- all edges without a white on them.
--
for i=1 to length(rotations) do
for j=1 to 2 do -- (just corners)
for k=1 to 4 do
cube[rotations[i][j][k]]='-'
end for
end for
end for
for i=1 to length(edges) do
integer {?,m1,?,?,m2,?} = edges[i]
if cube[m1]!='W'
and cube[m2]!='W' then
cube[m1] = '-'
cube[m2] = '-'
end if
end for
wslen = 8
s = score(cube,CROSS)
done = (s=8)
elsif stage=F2L then
--
-- first, blank out all pieces with a yellow
--
for i=1 to length(corners) do
integer {c1,c2,c3} = corners[i]
if cube[c1]='Y'
or cube[c2]='Y'
or cube[c3]='Y' then
cube[c1] = '-'
cube[c2] = '-'
cube[c3] = '-'
end if
end for
for i=1 to length(edges) do
integer {?,m1,?,?,m2,?} = edges[i]
if cube[m1]='Y'
and cube[m2]='Y' then
cube[m1] = '-'
cube[m2] = '-'
end if
end for
wslen = 57+12
s = score(cube,F2L)
done = (f2l=28)
else
wslen = 77+24
s = score(cube,stage)
if f2l!=28 then ?9/0 end if
if stage=OLL then
done = (oll_score(cube)=8)
else -- (stage=PLL)
done = (s=48)
end if
end if
if not done then
workspace = repeat({},wslen)
w2 = workspace
init = cube
workspace[high] = {""}
destroy_dict(seen,justclear:=1)
integer move_count = 1
while 1 do
if workspace[high]={} then
while high and workspace[high]={} do high -= 1 end while
if high=0 or (stage!=CROSS and c2c>THRESHOLD) then
move_count += 1
workspace = w2
w2 = repeat({},wslen)
c2c = 0
high = wslen
while workspace[high]={} do high -= 1 end while
end if
end if
moves = workspace[high][1]
workspace[high] = workspace[high][2..$]
cube = apply_moves(init,moves)
for face=U to D do
-- (originally this loop did 180s as well, but that
-- gave them far too much dominance, esp during pll.
-- instead we now coalese those that survive a 90.)
for m=0 to Shift by Shift do
integer mi = face+m
sequence cube2 = rotate_face(cube,mi)
if getd_index(cube2,seen)=0 then
putd(cube2,0,seen)
s = score(cube2,stage)
if stage=CROSS then
done = (s=8)
elsif stage=F2L then
done = (f2l=28)
else
if f2l=28 then
o = oll_score(cube2)
else
o = 0
end if
if stage=OLL then
done = (o=8)
else
done = (s=48)
end if
end if
moves2 = moves
if length(moves2) and moves2[$]=mi then
moves2[$] = face+Dbl
else
moves2 &= mi
end if
if done then
destroy_dict(seen,justclear:=1)
return moves2
end if
s += 1+edge_score*2+o
w2[s] = append(w2[s],moves2)
c2c += 1
end if
end for
end for
if time()>t1 then
printf(1,"working... %d moves, %d positions\r",{move_count,dict_size(seen)})
t1 = time()+1
if get_key()=#1B then exit end if
end if
end while
end if
return "" -- (already solved case)
end function
 
constant stage_desc = { "make cross",
"solve first two layers",
"orientate last layer",
"permute last layer" }
 
procedure main()
string cube
sequence moves
integer total_moves = 0
atom t0 = time()
 
-- "hardest case" from http://www.cube20.org
moves = {F, Us, F2, Ds, B, U, Rs, Fs, L, Ds,
Rs, Us, L, U, Bs, D2, Rs, F, U2, D2}
cube = apply_moves(init,moves)
if length(moves)<=20 then
printf(1,"scramble: %s\n",{moves_to_string(moves)})
end if
 
puts(1,substitute(cube,"-"," "))
 
for stage=CROSS to PLL do
moves = solve_stage(cube, stage)
total_moves += length(moves)
cube = apply_moves(cube,moves)
printf(1,"%s: %s\n",{stage_desc[stage],moves_to_string(moves)})
if length(moves) then
puts(1,substitute(cube,"-"," "))
end if
end for
printf(1,"\nsolution of %d total moves found in %3.2fs\n",{total_moves,time()-t0})
end procedure
main()
Output:

The "hardest case" from http://www.cube20.org with a high threshold. You can try this manually. Disclaimer: the results are not always quite as good as this!

scramble: FU'F2D'BUR'F'LD'R'U'LUB'D2R'FU2D2  (20 moves)
   ROB
   BYG
   GRO
YYOYYBYYRYYG
RBOBRGOGRGOB
WWOWWBWWRWWG
      OGB
      RWO
      GBR

make cross: DLBRFL  (6 moves)
   BRB
   YYG
   YYY
ROBRBRGOYOGW
OBRBRYRGYGOB
RBYORGOGOBOW
      WWW
      WWW
      GWG

solve first two layers: FUL'R'FLRF'LRB'R'U'BU'B'U'B  (18 moves)
   RYG
   OYR
   YYY
BYRGGOBYOYBY
BBBRRRGGGOOO
BBBRRRGGGOOO
      WWW
      WWW
      WWW

orientate last layer: R'F'U'FUR  (6 moves)
   YYY
   YYY
   YYY
GGBRRGOOOBBR
BBBRRRGGGOOO
BBBRRRGGGOOO
      WWW
      WWW
      WWW

permute last layer: RU'L'UR'U2LU'L'U2LU'  (12 moves)
   YYY      
   YYY      
   YYY      
BBBRRRGGGOOO
BBBRRRGGGOOO
BBBRRRGGGOOO
      WWW
      WWW
      WWW


solution of 42 total moves found in 81.33s

thistlethwaite[edit]

Translation/de-golf(hrumph) of Tomas Sirgedas' winning entry from http://tomas.rokicki.com/cubecontest as held in 2004.
Faster and shorter solutions (in most cases) than cfop, however probably nigh on impossible to debug/enhance...

--
-- demo\rosetta\rubik_tomas.exw
--
function xor_string(string s)
return xor_bits(s[1],xor_bits(s[2],iff(length(s)=3?s[3]:'!')))
end function
 
function xor_all(sequence s)
for i=1 to length(s) do
s[i] = xor_string(s[i])
end for
return s
end function
 
constant d1 = xor_all(split("UF DF UB DB UR DR UL DL FR FL BR BL UFR DBR UBL DFL DLB ULF DRF URB"))
-- This is Mike Reid's notation, 12 sides then 8 corners, which may be rotated - hence we xor the
-- characters for fast lookup. The above string represents a cube in the solved state.
 
constant d2 = {18,12,17,15,0, 9,1,8,16,14,19,13,2,10,3,11,12,18,13,19,4,8,5,10,
14,16,15,17,6,11,7,9,17,12,19,14,6, 0,4, 2,18,15,16,13,1,7,3, 5}
--?sort(d2): (0..11 appear twice, 12..19 appear thrice - edges/corners is pretty much all I can say)
 
constant d3 = {13,16,15,1,3,
19,18,17,4,6}
-- these apppear to be swapped during initialisation, dunno why...
 
integer cur_phase, search_mode, history_idx
sequence history_mov = repeat(0,48),
history_rpt = repeat(0,48),
depth_to_go,
hash_table = repeat(repeat(6,6912),48)
-- (hash_table can/should be preserved for different problems)
 
sequence cubelet_pos = repeat(0,48),
cubelet_twi = repeat(0,48)
 
procedure rot(integer cur_phase)
if cur_phase<4 then
for i=0 to 3 do
integer di = cur_phase*8+i+1,
j = d2[di]+1,
k = d2[di+4]+1
cubelet_twi[j] = mod(cubelet_twi[j]+2-mod(i,2),3)
cubelet_twi[k] = xor_bits(cubelet_twi[k],cur_phase<2)
end for
end if
 
for i=0 to 6 do
integer di = cur_phase*8+i+1,
j = d2[di+(i!=3)]+1,
k = d2[di]+1
-- swap(cubelet[j]], cubelet[k]);
{cubelet_pos[j],cubelet_pos[k]} = {cubelet_pos[k],cubelet_pos[j]}
{cubelet_twi[j],cubelet_twi[k]} = {cubelet_twi[k],cubelet_twi[j]}
end for
end procedure
 
function hashf()
int ret = 0;
switch cur_phase do
case 0:
for i=0 to 10 do
ret += ret + cubelet_twi[i+1]
end for
return ret;
case 1:
for i=0 to 6 do
ret = ret*3 + cubelet_twi[i+12+1]
end for
for i=0 to 10 do
ret += ret + (cubelet_pos[i+1]>7)
end for
return ret-7;
case 2:
sequence inva = repeat(0,48),
b = repeat(0,48)
for i=0 to 7 do
integer ci12p = cubelet_pos[i+12+1],
ci12p3 = and_bits(ci12p,3)
if ci12p<16 then
inva[ci12p3+1] = ret
ret += 1
else
b[i-ret+1] = ci12p3
end if
end for
for i=0 to 6 do
ret += ret + (cubelet_pos[i+1]>3);
end for
for i=0 to 6 do
ret += ret + (cubelet_pos[i+12+1]>15);
end for
integer ib2 = xor_bits(inva[b[1]+1],inva[b[2]+1])*2,
ib3 = xor_bits(inva[b[1]+1],inva[b[3]+1]),
ib4 = xor_bits(inva[b[1]+1],inva[b[4]+1])
return ret*54 + ib2 + (ib3 > ib4) - 3587708
end switch
for i=0 to 4 do
ret *= 24;
for cp=0 to 3 do
for k=0 to cp-1 do
if cubelet_pos[i*4+cp+1] < cubelet_pos[i*4+k+1] then
ret += cp + iff(cp=3?cp:0)
end if
end for
end for
end for
return floor(ret/2)
end function
 
function do_search(integer dpt)
integer h = hashf(),
q = (floor(cur_phase/2)*19+8)*power(2,7),
hmq = mod(h,q)+1,
hfq = floor(h/q)+1,
d = (dpt < hash_table[cur_phase+1][hmq] or
dpt < hash_table[cur_phase+4+1][hfq])
 
if d xor search_mode then
if search_mode then
if dpt <= depth_to_go[h+1] then
return not h;
else
depth_to_go[h+1] = dpt;
end if
end if
 
hash_table[cur_phase+1][hmq] = min(hash_table[cur_phase+1][hmq],dpt);
hash_table[cur_phase+5][hfq] = min(hash_table[cur_phase+5][hfq],dpt);
 
for k=0 to 5 do
for i=0 to 3 do
rot(k)
if (k>=cur_phase*2 or i=1) and i<=2 then
history_idx += 1
history_mov[history_idx] = k
history_rpt[history_idx] = i
if do_search(dpt-search_mode*2+1) then return 1 end if
history_idx -= 1
end if
end for
end for
end if
return 0
end function
 
function pack_moves()
string moves = ""
integer n = 0, this, last, last_rpt
if history_idx!=0 then
-- add a dummy move to trigger the last move print:
last = xor_bits(history_mov[history_idx],1) -- F<->B, etc
history_idx += 1
history_mov[history_idx] = last
history_rpt[history_idx] = 0
last = history_mov[1]
last_rpt = 0
for i=1 to history_idx do
this = history_mov[i]
if this!=last then
-- coalesce eg F1F2 to F' (unless you wanna fix do_search()!)
if last_rpt then
moves &= "FBRLUD"[last+1] & {"","2","'"}[last_rpt]
n += 1
end if
last = this
last_rpt = history_rpt[i]+1
else
last_rpt = mod(last_rpt+history_rpt[i]+1,4)
end if
end for
end if
return {moves,n,iff(n=1?"":"s")}
end function
 
function tomas(sequence args)
search_mode = 0
history_idx = 0
depth_to_go = repeat(0,5*power(2,20))
 
for i=0 to 19 do
cubelet_pos[i+1] = i
end for
for i=0 to 3 do
cur_phase = i
{} = do_search(0)
end for
args = split(args)
for i=0 to 19 do
string s = args[i+1] -- (may be rotated, eg RU or UR)
integer p = find(xor_string(s),d1)
if p=0 then ?9/0 end if -- sensible message(bad args)?
cubelet_pos[i+1] = p-1
int x = max(find('U',s), find('D',s));
cubelet_twi[i+1] = iff(x!=0 ? x-1 : s[1]>'F')
end for
for i=0 to 4 do
integer j = d3[i+1]+1,
k = d3[i+6]+1
-- swap(cubelet[j], cubelet[k]);
{cubelet_pos[j],cubelet_pos[k]} = {cubelet_pos[k],cubelet_pos[j]}
{cubelet_twi[j],cubelet_twi[k]} = {cubelet_twi[k],cubelet_twi[j]}
end for
search_mode = 1;
for cp=0 to 3 do
cur_phase = cp
for i=0 to 19 do
if do_search(i) then exit end if
end for
end for
return pack_moves()
end function
 
printf(1,"%s (%d move%s)\n",tomas("UL DL RF UB FD BR DB UF DR UR BL FL FDR BLU DLB URB RUF FLD BRD FUL"))
Output:
UF'R'FB2R2B2LD2L2DLR2U'F2UF2U2F2L2UF2DF2U2R2U2R2B2D2R2F2L2B2D2 (35 moves)

The distributed copy of demo\rosetta\rubik_cfop.exw also contains routines to convert between my 136-character cube and reid notation, and demo\rosetta\rubik_tomas.exw also contains the full 100-long test set from the original competition.