Solve a Rubik's cube: Difference between revisions
Thundergnat (talk | contribs) m (Change to draft status, minor typo fix) |
(added Phix) |
||
Line 4: | Line 4: | ||
You may use any sort of input you wish. |
You may use any sort of input you wish. |
||
=={{header|Phix}}== |
|||
===cfop=== |
|||
Uses brute-force (width/highscore-first) Fridrich-steps (ie cross,f2l,oll,pll).<br> |
|||
Not the fastest (see THRESHOLD) or shortest results (see thistlethwaite) but the code is pretty easy to follow.<br> |
|||
The final stage (pll) would probably benefit the most from being replaced with standard algorithms. |
|||
<lang Phix>-- |
|||
-- 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()</lang> |
|||
{{Out}} |
|||
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! |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
===thistlethwaite=== |
|||
Translation/de-golf(hrumph) of Tomas Sirgedas' winning entry from http://tomas.rokicki.com/cubecontest as held in 2004.<br> |
|||
Faster and shorter solutions (in most cases) than cfop, however probably nigh on impossible to debug/enhance... |
|||
<lang Phix>-- |
|||
-- 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"))</lang> |
|||
{{out}} |
|||
<pre> |
|||
UF'R'FB2R2B2LD2L2DLR2U'F2UF2U2F2L2UF2DF2U2R2U2R2B2D2R2F2L2B2D2 (35 moves) |
|||
</pre> |
|||
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. |
Revision as of 19:55, 13 September 2017
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
cfop
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.
<lang Phix>--
-- 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()</lang>
- 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
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...
<lang Phix>--
-- 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"))</lang>
- 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.