Solve a Rubik's cube: Difference between revisions
added Phix
Thundergnat (talk | contribs) m (Change to draft status, minor typo fix) |
(added Phix) |
||
Line 4:
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.
| |||