While experimenting with coordinates and 3D graphs, I wondered whether Stata/Mata could do more than draw a cube. Could it find a solution to a small 2x2 cube problem and then show the moves?
This version starts with 24 sticker colors. It knows the legal turns and the target arrangement, but receives neither the scramble history nor a solution sequence.
Mata explores states up to three moves from each end, removes duplicates, and finds the meeting with the shortest combined path. Stata then draws that verified path, using two fixed views so that all six faces can be seen. The panels show the chosen solution, not every branch explored by the search.
For the supplied state, Stata/MP 16.1 reports:
R, U and F mean the right, upper and front faces. A prime means counterclockwise when viewed from outside that face; 2 means a half turn. Each counts as one move. 
The scope is deliberately small: only these three faces are turned, the target orientation is fixed, and the search covers solutions of at most six moves. Within those rules the returned path is shortest. Failure to find one would mean "not found within the limit", not "this cube is impossible". The final arrangement is checked against all 24 target stickers.
I found the distinction between turning a face and changing the camera particularly useful: one changes the puzzle state, while the other changes how I see it.
The complete code follows, including the graphics. Paste the whole block into one do-file. No downloads, packages or data files are needed. It preserves the current dataset, uses sb2_/SB2_ names, and writes cube_search_2x2.png in the current folder (replacing that file if it exists). The graphics are static snapshots after each turn.
I would be interested in a simpler way to show the search itself, or a clearer visual cue for the next turn. This seems a useful small playground for coordinates, search and graphics together.
One question this leaves me with: does a cube with more stickers in their target positions necessarily need fewer moves to solve? I would like to compare “looking closer” with the shortest-path distance.
This version starts with 24 sticker colors. It knows the legal turns and the target arrangement, but receives neither the scramble history nor a solution sequence.
Mata explores states up to three moves from each end, removes duplicates, and finds the meeting with the shortest combined path. Stata then draws that verified path, using two fixed views so that all six faces can be seen. The panels show the chosen solution, not every branch explored by the search.
For the supplied state, Stata/MP 16.1 reports:
Code:
FOUND BY SEARCH: F2 U R2 F' U' R' Length: 6 face turns; states: 385 start + 385 goal
The scope is deliberately small: only these three faces are turned, the target orientation is fixed, and the search covers solutions of at most six moves. Within those rules the returned path is shortest. Failure to find one would mean "not found within the limit", not "this cube is impossible". The final arrangement is checked against all 24 target stickers.
I found the distinction between turning a face and changing the camera particularly useful: one changes the puzzle state, while the other changes how I see it.
The complete code follows, including the graphics. Paste the whole block into one do-file. No downloads, packages or data files are needed. It preserves the current dataset, uses sb2_/SB2_ names, and writes cube_search_2x2.png in the current folder (replacing that file if it exists). The graphics are static snapshots after each turn.
Code:
version 16.1
set more off
preserve
capture quietly mata: sb2_goal()
if _rc {
mata:
struct sb2_tree {
real matrix states
real colvector depth, parent, move
transmorphic scalar seen
}
struct sb2_result {
real scalar found, length, startnodes, goalnodes, checks
real rowvector path
real matrix layers
}
real matrix sb2_geometry()
{
real matrix N,G
real rowvector n,a,b,c
real scalar f,i,j
N=(1,0,0\-1,0,0\0,0,1\0,0,-1\0,-1,0\0,1,0)
G=J(0,7,.)
for(f=1;f<=6;f++) {
n=N[f,]
if(abs(n[1])) { a=(0,1,0); b=(0,0,1); }
else if(abs(n[2])) { a=(1,0,0); b=(0,0,1); }
else { a=(1,0,0); b=(0,1,0); }
for(i=-1;i<=1;i=i+2) for(j=-1;j<=1;j=j+2) {
c=n+.5*i*a+.5*j*b
G=G\(c,n,f)
}
}
return(G)
}
real matrix sb2_moves(real matrix G)
{
real matrix P,Q,H
real rowvector axis,ix,base
real scalar f,i,k
P=J(9,24,.)
// Row vectors multiply Q. Clockwise seen from outside R, U, F.
for(f=1;f<=3;f++) {
if(f==1) { Q=(1,0,0\0,0,-1\0,1,0); axis=(1,0,0); }
if(f==2) { Q=(0,-1,0\1,0,0\0,0,1); axis=(0,0,1); }
if(f==3) { Q=(0,0,-1\0,1,0\1,0,0); axis=(0,-1,0); }
H=G
for(i=1;i<=24;i++) if(G[i,1..3]*axis'>0) {
H[i,1..3]=G[i,1..3]*Q
H[i,4..6]=G[i,4..6]*Q
}
k=3*f-2
for(i=1;i<=24;i++) {
ix=selectindex(rowsum(abs(G[,1..6]:-H[i,1..6])):==0)'
assert(cols(ix)==1)
P[k,ix[1]]=i
}
base=P[k,]
P[k+1,]=base[base]
P[k+2,]=base[base[base]]
assert(all(sort(base',1):==(1::24)))
assert(all(base[base[base[base]]]:==(1..24)))
}
return(P)
}
real rowvector sb2_goal()
{
return((1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6))
}
string scalar sb2_key(real rowvector s)
{
return(invtokens(strofreal(s,"%1.0f"),""))
}
real scalar sb2_inverse(real scalar m)
{
return(3*floor((m-1)/3)+4-mod(m-1,3)-1)
}
string scalar sb2_names(real rowvector path)
{
string rowvector names
names=("R","R2","R'","U","U2","U'","F","F2","F'")
if(cols(path)==0) return("(none)")
return(invtokens(names[path]))
}
real rowvector sb2_parse(string scalar text)
{
string rowvector words,names
real rowvector path,ix
real scalar i
words=tokens(text)
names=("R","R2","R'","U","U2","U'","F","F2","F'")
path=J(1,0,.)
for(i=1;i<=cols(words);i++) {
ix=selectindex(names:==words[i])
assert(cols(ix)==1)
path=path,ix[1]
}
return(path)
}
real rowvector sb2_apply(real rowvector s,real rowvector path,real matrix P)
{
real scalar i
real rowvector out
out=s
for(i=1;i<=cols(path);i++) out=out[P[path[i],]]
return(out)
}
struct sb2_tree scalar sb2_bfs(real rowvector root,real matrix P,real scalar radius)
{
struct sb2_tree scalar T
real scalar cap,head,n,d,m
real rowvector s
string scalar key
// Upper bound on all 9-branch paths. This demo limits radius to 4.
cap=(9^(radius+1)-1)/8
T.states=J(cap,24,.)
T.depth=J(cap,1,.)
T.parent=J(cap,1,0)
T.move=J(cap,1,0)
T.seen=asarray_create("string",1)
T.states[1,]=root; T.depth[1]=0
asarray(T.seen,sb2_key(root),1)
head=1; n=1
while(head<=n) {
d=T.depth[head]
if(d<radius) for(m=1;m<=9;m++) {
s=T.states[head,P[m,]]
key=sb2_key(s)
if(!asarray_contains(T.seen,key)) {
n++
T.states[n,]=s; T.depth[n]=d+1
T.parent[n]=head; T.move[n]=m
asarray(T.seen,key,n)
}
}
head++
}
T.states=T.states[1..n,]
T.depth=T.depth[1..n]; T.parent=T.parent[1..n]; T.move=T.move[1..n]
return(T)
}
real rowvector sb2_trace(struct sb2_tree scalar T, real scalar i)
{
real rowvector path
path=J(1,0,.)
while(T.parent[i]>0) {
path=T.move[i],path
i=T.parent[i]
}
return(path)
}
struct sb2_result scalar sb2_solve(real rowvector start,real matrix P,real scalar radius)
{
struct sb2_tree scalar A,B
struct sb2_result scalar R
real scalar i,j,d,best,ai,bi,c
real rowvector back
string scalar key
assert(cols(start)==24 & rows(start)==1)
assert(all(start:==floor(start)) & min(start)>=1 & max(start)<=6)
for(c=1;c<=6;c++) assert(sum(start:==c)==4)
assert(radius>=0 & radius<=4 & radius==floor(radius))
// Only start, legal moves and depth limit enter. No scramble history.
A=sb2_bfs(start,P,radius)
B=sb2_bfs(sb2_goal(),P,radius)
R.startnodes=rows(A.states); R.goalnodes=rows(B.states)
R.checks=rows(A.states); R.found=0; R.length=.
R.path=J(1,0,.); R.layers=J(radius+1,3,0)
for(d=0;d<=radius;d++) R.layers[d+1,]=(d,sum(A.depth:==d),sum(B.depth:==d))
best=.; ai=0; bi=0
// Check ALL meetings: first meeting need not give the shortest combined path.
for(i=1;i<=rows(A.states);i++) {
key=sb2_key(A.states[i,])
if(asarray_contains(B.seen,key)) {
j=asarray(B.seen,key)
d=A.depth[i]+B.depth[j]
if(d<best) { best=d; ai=i; bi=j; }
}
}
if(ai==0) return(R)
R.path=sb2_trace(A,ai)
back=sb2_trace(B,bi)
for(i=cols(back);i>=1;i--) R.path=R.path,sb2_inverse(back[i])
R.found=1; R.length=cols(R.path)
assert(R.length==best)
assert(all(sb2_apply(start,R.path,P):==sb2_goal()))
return(R)
}
// Static orthographic rendering. At quarter-turn endpoints the cube is convex;
// outward-facing stickers are sufficient, without a general z-buffer renderer.
void sb2_render(real rowvector state,real matrix G)
{
real matrix out,pts
real rowvector right,up,cam,n,a,b,c
real scalar view,i,poly,shift
out=J(0,5,.); poly=0
for(view=1;view<=2;view++) {
right=(.8,.6,0); up=(-.36,.48,.8); cam=(.48,-.64,.6)
if(view==2) { right=-right; cam=-cam; }
shift=(view==1 ? 0 : 3.8)
for(i=1;i<=24;i++) {
n=G[i,4..6]
if(n*cam'<=0) continue
if(abs(n[1])) { a=(0,1,0); b=(0,0,1); }
else if(abs(n[2])) { a=(1,0,0); b=(0,0,1); }
else { a=(1,0,0); b=(0,1,0); }
// First sticker of each face also draws its dark backing square.
if(mod(i-1,4)==0) {
pts=(n-a-b\n+a-b\n+a+b\n-a+b\n-a-b)
poly++
out=out\(J(5,1,poly),pts*right':+shift,pts*up',J(5,1,0),J(5,1,view))
}
c=G[i,1..3]
pts=(c-.46*a-.46*b\c+.46*a-.46*b\c+.46*a+.46*b\c-.46*a+.46*b\c-.46*a-.46*b)
poly++
out=out\(J(5,1,poly),pts*right':+shift,pts*up',J(5,1,state[i]),J(5,1,view))
}
}
st_addobs(rows(out))
st_addvar("double",("polygon","px","py","color","view"))
st_store(.,.,out)
}
end
}
clear
mata:
sb2_G=sb2_geometry()
sb2_P=sb2_moves(sb2_G)
// Current colors only: no scramble history or solution is supplied.
// Slots: R(1-4), L(5-8), U(9-12), D(13-16), F(17-20), B(21-24).
// Colors: 1 red, 2 orange, 3 white, 4 yellow, 5 green, 6 blue.
sb2_start=(2,6,5,3,5,6,2,1,3,3,1,6,2,4,3,4,4,2,5,4,6,5,1,1)
sb2_answer=sb2_solve(sb2_start,sb2_P,3)
if(!sb2_answer.found) {
printf("No solution within 6 face turns; this does not prove impossibility.\n")
_error(3498)
}
printf("INPUT STATE: %s\n",sb2_key(sb2_start))
printf("FOUND BY SEARCH: %s\n",sb2_names(sb2_answer.path))
printf("Length: %g face turns; states: %g start + %g goal\n",sb2_answer.length,sb2_answer.startnodes,sb2_answer.goalnodes)
st_numscalar("SB2_length",sb2_answer.length)
st_numscalar("SB2_startnodes",sb2_answer.startnodes)
st_numscalar("SB2_goalnodes",sb2_answer.goalnodes)
st_matrix("SB2_layers",sb2_answer.layers)
sb2_states=sb2_start
for(sb2_i=1;sb2_i<=sb2_answer.length;sb2_i++) sb2_states=sb2_states\sb2_apply(sb2_states[rows(sb2_states),],sb2_answer.path[sb2_i],sb2_P)
assert(all(sb2_states[rows(sb2_states),]:==sb2_goal()))
end
local panels
forvalues step=0/`=scalar(SB2_length)' {
clear
mata: sb2_render(sb2_states[`step'+1,],sb2_G)
local applied "Start"
if `step'>0 {
mata: st_local("applied",sb2_names(sb2_answer.path[`step']))
}
local next "SOLVED: all 24 facelets checked"
if `step'<scalar(SB2_length) {
mata: st_local("next","Next: "+sb2_names(sb2_answer.path[`step'+1]))
}
local colors `""40 45 53" "204 57 57" "239 145 50" "244 244 235" "246 211 64" "49 151 113" "66 111 185""'
quietly levelsof polygon, local(polys)
local plots
foreach p of local polys {
quietly summarize color if polygon==`p', meanonly
local ci=r(min)+1
local rgb : word `ci' of `colors'
local plots `"`plots' (area py px if polygon==`p', color("`rgb'") lcolor("40 45 53") lwidth(vthin))"'
}
twoway `plots', aspectratio(.5070422535) xscale(range(-1.65 5.45) noextend off) yscale(range(-1.6 2.0) noextend off) xlabel(none) ylabel(none) legend(off) text(1.75 0 "Front / right / up", size(small) color(gs6)) text(1.75 3.8 "Back / left / down", size(small) color(gs6)) title("Step `step': `applied'", size(medium)) subtitle("`next'", size(small)) graphregion(color(white)) plotregion(color(white)) xsize(9) ysize(5.8) name(sb2_step`step', replace)
local panels `panels' sb2_step`step'
}
twoway scatteri 0 0, msymbol(none) xscale(range(0 10) off) yscale(range(0 10) off) xlabel(none) ylabel(none) legend(off) text(8.7 5 "Input: 24 colors, no move history", size(medium)) text(6.9 5 "Start side: `=scalar(SB2_startnodes)' distinct states", size(medium) color("40 104 150")) text(5.8 5 "Goal side: `=scalar(SB2_goalnodes)' distinct states", size(medium) color("40 104 150")) text(4.0 5 "Depth: 0 1 2 3", size(medium)) text(3.0 5 "Start: `=SB2_layers[1,2]' / `=SB2_layers[2,2]' / `=SB2_layers[3,2]' / `=SB2_layers[4,2]'", size(medium)) text(1.1 5 "Shortest path found: `=scalar(SB2_length)' face turns", size(medium)) title("The search behind the pictures", size(medium)) graphregion(color(white)) plotregion(color(white)) xsize(9) ysize(5.8) name(sb2_summary, replace)
graph combine `panels' sb2_summary, cols(2) imargin(tiny) graphregion(color(white)) title("A 2x2 cube solved by search in Mata", size(medium)) note("Mata finds the moves; Stata draws the verified states. Both fixed views together show all six faces." "R/right, U/up, F/front. Prime: counterclockwise viewed from outside. 2: a half turn.", size(vsmall)) xsize(12) ysize(16) name(sb2_overview, replace)
graph export "cube_search_2x2.png", width(1800) replace
restore
display "CUBE_SANDBOX_PASS"
One question this leaves me with: does a cube with more stickers in their target positions necessarily need fewer moves to solve? I would like to compare “looking closer” with the shortest-path distance.
Comment