# My trial to make a mapping of (2x2x2 rubik's cube, poket cube, mini cube)'s states with solutions.Recursive function wanted.

#1

Hello everyone,

I’m trying to make a pocket cube solver in Julia.

I would like some advises, remarks and ultimately some help to write a optimized recursive function to replace my “for loop”.

First some explanations of my method:

1. I fix one of the 8 corners and move the others around it.

2. I represent the cube with an a 1x21 Array{Int8,2} (3 faces for each 7 corners left).

``````Int8[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21]
``````
1. I use the permute!(v,p) function from the combinatorics.jl packages to rotate the cube.I define 6 permutations, one for every quarter turn possible (top,right,front+anticlockwise).
``````T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]
``````
1. I stock the cube states in a `Int32[]` array and one cube state is define by:
``````state=Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+(cube[16]-1)
``````

So I look at one face of 6 corners and I made a integer in a 21 radix/base.

1. I use string to remember the moves. “TFRtfr” mean rotate the cube (top clockwise then front clockwise then right clockwise then top anticlockwise then front anticlockwise then right anticlockwise).

Here is my code:

``````using Combinatorics

global const T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
global const Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
global const F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
global const Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
global const R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
global const Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]

global cube = Int8[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21]

global stateslist=Int32[]
global rotlist=String[]
global rot=""
global numb=Int32(1)
global inversrot=String["t","f","r","T","F","R"]

function rotcube(r)
global cube,rot,T,F,R,Ti,Fi,Ri
if r==0 && !endswith(rot,"t") && !endswith(rot,"TT")
permute!(cube,T)
rot*="T"
return 0
elseif r==1 && !endswith(rot,"f") && !endswith(rot,"FF")
permute!(cube,F)
rot*="F"
return 0
elseif r==2 && !endswith(rot,"r") && !endswith(rot,"RR")
permute!(cube,R)
rot*="R"
return 0
elseif r==3 && !endswith(rot,"T") && !endswith(rot,"t")
permute!(cube,Ti)
rot*="t"
return 0
elseif r==4 && !endswith(rot,"F") && !endswith(rot,"f")
permute!(cube,Fi)
rot*="f"
return 0
elseif r==5 && !endswith(rot,"R") && !endswith(rot,"r")
permute!(cube,Ri)
rot*="r"
return 0
else
return 1
end
end

function jumpcube(way)
global cube,T,F,R,Ti,Fi,Ri
for i in way
if i=='T'
permute!(cube,T)
elseif i=='F'
permute!(cube,F)
elseif i=='R'
permute!(cube,R)
elseif i=='t'
permute!(cube,Ti)
elseif i=='f'
permute!(cube,Fi)
elseif i=='r'
permute!(cube,Ri)
end
end
end

function upstates()
global cube,rot,stateslist,rotlist
state=Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+cube[16]-1)
index=findin(stateslist,state)
if index==[]
push!(stateslist,state)
push!(rotlist,rot)
elseif length(rotlist[index[1]])>=length(rot) && findin([rot],split(rotlist[index[1]],'/'))==[]
rotlist[index[1]]*="/"*rot
end
end

while sizeof(rot)<5 #the number of quarter turn, 14 is the maximum to solve any position of the cube.
for i in 0:5
flag=rotcube(i)
upstates()
if flag == 0
jumpcube(inversrot[i+1])
rot=chop(rot)
end
end
cube = Int8[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21]
jumpcube(split(rotlist[numb],'/')[1])
rot=split(rotlist[numb],'/')[1]
numb+=1
end

for o in rotlist
print(o*"-|-")
end
println("---------------------------")
``````

I wanna replace the for loop with a recursive function but I need some advises.

Thanks you very much

rapasite

#2

You might be able to partially solve for the corner rotations individually, and then a greedy pathfinder with a distance metric could possibly work

#3

I am starting with the solved cube and exploring all the possibilities.
For every possibilities (state of the cube) I stock the configuration of the cube in “stateslist” and the corresponding moves to get there from the solve cube in “rotlist”.

So at rotlist[i] is a string who contain the moves to go to the stateslist[i] cube configuration from the solved cube (if you make the inverse of the moves in rotlist[i] you go back to the solved cube). Witch mean the cube is completely solve already.

Of course it is not convenient at the moment to take a scramble cube and get the best solution from my program to solve it. Once the code is optimized I plan to make a user friendly interface.

As for a corner rotation individually this is a impossible move to make on a rubik’s cube.

thx you

#4

That’s okay, my answer isn’t certain to work, and it seems you have a working solver
It’s pretty nice really, I’d probably have written much more code to get something similar

In one move, yes, and just on it’s own, probably also yes-ish, but this may be half of what makes rubiks cubes tricky… You can do a sequence of down-left-up-up to rotate a corner 120 degrees and be back at the same corner position.
I had meant partially solving for both the position and corner-face-rotation as `rotation’ though, and you’d have to find a way of combining the individual solutions back into grouped turns of the cube

this may help visualize the corners

#5

Since nobody answer yet for the recursive version I did some test on my own, Here is my new code:

It’s pretty AMAZING to solve all the (pocketcube,minicube,2x2x2 rubik’s cube) in LESS THAN 40 LINES OF JULIA CODE!!!

thanks julia

``````using Combinatorics

global const T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
global const Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
global const F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
global const Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
global const R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
global const Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]

global stateslist=Int32[]
global rotlist=String[]

cube=Int8[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,11,12,13,14,15,16,17,18,19,20,21]
rot=""

function browsecube(cube,rot)
if length(rot)>6
return
end
state=Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+cube[16]-1)
index=findin(stateslist,state)
if index!=[]
if length(rot) < length(split(rotlist[index[1]],'/')[1])
rotlist[index[1]]=rot
elseif length(rot) == length(split(rotlist[index[1]],'/')[1])
rotlist[index[1]]*="/"*rot
else
return
end
else
push!(rotlist,rot)
push!(stateslist,state)
end
browsecube(cube[T],rot*"T")
browsecube(cube[F],rot*"F")
browsecube(cube[R],rot*"R")
browsecube(cube[Ti],rot*"t")
browsecube(cube[Fi],rot*"f")
browsecube(cube[Ri],rot*"r")
end

@time browsecube(cube,rot)

for o in rotlist
print(o*"-|-")
end
``````

Since I have a lot to learn about Julia I will be glad if someone point out the part slowing it down because it is very long to evaluate.
I know I am making some strange stuff so please ask me some questions if needed.

Tips needed to speed it up.

thx!

#6

You can save a bit of time by only keeping the shortest rotlist string, about +50% speed-up on the local machine

``````## version 2
## much faster
global const T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
global const Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
global const F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
global const Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
global const R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
global const Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]

global const Tii=T[T];
global const Fii=F[F];
global const Rii=R[R];

println("T[Tii] == Ti ", T[Tii] == Ti );
println("F[Fii] == Fi ", F[Fii] == Fi );
println("R[Rii] == Ri ", R[Rii] == Ri );

mutable struct xcube
id::Int32;
cube::Array{Int8,1};
parent::Int32;
last::Int8;
end;

function initcube()
cube=Int8[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,11,12,13,14,15,16,17,18,19,20,21];
rot="";
local stateslist=Dict{Int32, xcube}();
local rotlist=Int32[]

println("begin");
@time (sl, rl) = browsecubeW(cube,rot, stateslist, rotlist);

return(sl, rl);
end;

function stateid(cube)
return Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+cube[16]-1)
end;

function addstate(cube, sl, rl, p, r)
cubeid = stateid(cube);
x = get!(sl, cubeid, xcube(cubeid, cube, p, r));
if((x.parent == p) & (x.last == r))
push!(rl, cubeid);
end;
return(sl, rl);
end;

function browsecubeW(cube,rot, sl, rl, b=0)
xbreak = 0;
sl, rl = addstate(cube, sl, rl, 0, 0);

local iter = 1;
local a1 = time();

while(xbreak==0)

local ccubeid = rl[iter];
local ccube = sl[ccubeid];

if(iter%10000 == 0)
print(time() - a1, " ", length(sl), " ", iter, " ");
end;
if(ccube.last != 1)
sl, rl = addstate(ccube.cube[T], sl, rl, iter, 1);
sl, rl = addstate(ccube.cube[Ti], sl, rl, iter, 1);
sl, rl = addstate(ccube.cube[Tii], sl, rl, iter, 1);
end;
if(ccube.last != 2)
sl, rl = addstate(ccube.cube[F], sl, rl, iter, 2);
sl, rl = addstate(ccube.cube[Fi], sl, rl, iter, 2);
sl, rl = addstate(ccube.cube[Fii], sl, rl, iter, 2);
end;
if(ccube.last != 3)
sl, rl = addstate(ccube.cube[R], sl, rl, iter, 3);
sl, rl = addstate(ccube.cube[Ri], sl, rl, iter, 3);
sl, rl = addstate(ccube.cube[Rii], sl, rl, iter, 3);
end;
xbreak = 0 + (iter == size(rl, 1)) + (iter > 10000000);
iter = iter+1;
end;
return(sl, rl);
end

##for o in rotlist
##print(o*"-|-")
##end
``````

@rapasite try this one
Should be even faster with a `sizehint`, i’m pretty sure it’s pausing to do `rehash!`

#7

Yeah, but I want all the best solutions to solve any cube’s scramble because I am thinking about making a tool for the speedcubers.

I figure we don’t need to use the deepcopy (I was using it a some point for some reasons) in the browsecube arguments (a speed up occur!).
I edit the code in my previous post and I am not sure the one you start with was working perfect.

Thanks you so much to dig inside my code It make me happy.

I will get more time in 3 hours to look a your code.

I am sure there is still space for a good optimization but I am not good enough as I am a noob^^.
I will try anyway hehe!

So to any experts on optimization around here thanks in advance.

Is there another good place to post my Julia code looking for optimized code?

#8

For those interested here is my last version:

``````using DataStructures

global const T=Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
global const t=Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
global const F=Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
global const f=Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
global const R=Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
global const r=Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]

global slvcube=Int8[0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,11,12,13,14,15,16,17,18,19,20]

function upstates(state,rot)
get!(statesdict,Int32(T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1]),"t"*rot)
get!(statesdict,Int32(t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1]),"T"*rot)
get!(statesdict,Int32(F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1]),"f"*rot)
get!(statesdict,Int32(f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1]),"F"*rot)
get!(statesdict,Int32(R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1]),"r"*rot)
get!(statesdict,Int32(r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1]),"R"*rot)
end

function cube(state)
p=digits(state,21,6)
c=setdiff(0:6,div.(p,3))[1]*3+(2*sum(p)%3)
return Int8[p[6],p[6]-p[6]%3+(p[6]+1)%3,p[6]-p[6]%3+(p[6]+2)%3,p[5],p[5]-p[5]%3+(p[5]+1)%3,p[5]-p[5]%3+(p[5]+2)%3,p[4],p[4]-p[4]%3+(p[4]+1)%3,p[4]-p[4]%3+(p[4]+2)%3,p[3],p[3]-p[3]%3+(p[3]+1)%3,p[3]-p[3]%3+(p[3]+2)%3,p[2],p[2]-p[2]%3+(p[2]+1)%3,p[2]-p[2]%3+(p[2]+2)%3,p[1],p[1]-p[1]%3+(p[1]+1)%3,p[1]-p[1]%3+(p[1]+2)%3,c,3*(c÷3)+(c+1)%3,3*(c÷3)+(c+2)%3]
end

function state(cube)
return Int32(cube[1]*21^5+cube[4]*21^4+cube[7]*21^3+cube[10]*21^2+cube[13]*21+cube[16])
end

function move(cube,movement)
for rot in movement
if rot=='T'
cube=T[cube+1]
end
if rot=='t'
cube=t[cube+1]
end
if rot=='F'
cube=F[cube+1]
end
if rot=='f'
cube=f[cube+1]
end
if rot=='R'
cube=R[cube+1]
end
if rot=='r'
cube=r[cube+1]
end
end
return cube
end

global statesdict = OrderedDict{Int32,String}(643245=>"")
@time for i in keys(statesdict)
upstates(i,statesdict[i])
end

statesdict
``````

create a dictionary that contain all permutations of the (2x2x2 rubik’s cube, poket cube, mini cube) associated with one of the shortest solution!

It take about 9 seconds on my laptop

special thanks to @y4lu

#9

Code doesn’t run, `i` is not defined.

#10

should i be 643245 in your example?

#11

I do not really understand your model (or the states), but on my computer things become about twice as fast
when I refrain from using global variables (is that needed for your use case?), also either inbounds or SVector might help.

On my computer my version uses half as much memory as yours (that is, if I interpreted the starting value for `i`correctly)

``````using StaticArrays
using BenchmarkTools
using DataStructures

#=
global const T=@SVector Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
global const t=@SVector Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
global const F=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
global const f=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
global const R=@SVector Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
global const r=@SVector Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]
=#

function upstates(statesdict,state,rot,T,F,R,t,f,r)
@inbounds get!(statesdict,Int32(T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1]),"T"*rot)
@inbounds get!(statesdict,Int32(t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1]),"t"*rot)
@inbounds get!(statesdict,Int32(F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1]),"F"*rot)
@inbounds get!(statesdict,Int32(f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1]),"f"*rot)
@inbounds get!(statesdict,Int32(R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1]),"R"*rot)
@inbounds get!(statesdict,Int32(r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1]),"r"*rot)
end

function me()
statesdict = OrderedDict{Int32,String}(643245=>"")
const T=@SVector Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
const t=@SVector Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
const F=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
const f=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
const R=@SVector Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
const r=@SVector Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]
for state in keys(statesdict)
upstates(statesdict,state,statesdict[643245],T,F,R,t,f,r)
end
statesdict
end

@benchmark result=me() #7.2 seconds about 780mb allocations

``````

#12

I edited the code changing i by state

@bernhard i should be the iteration on the keys of statesdict, sorry about forgetting to change the value

#13

Instead of a string, we can represent a rotation as a `UInt8` value

``````struct Rotation
r::UInt8
end
const rotations = ["T", "t", "F", "f", "R", "r"]
Base.show(io::IO, r::Rotation) = print(io, rotations[r.r])
``````

and then create the different rotations

``````for (i, r) in enumerate(rotations)
@eval const \$(Symbol(r)) = Rotation(\$i % UInt8)
end
``````
``````julia> T
T

julia> F
F

julia> typeof(F)
Rotation
``````

A set of rotation can be represented as a `UInt128` containing the bits of the rotations.
This can represent a total of 128/8 = 16 rotations which should be enough for 2x2x2

``````struct RotationSet
r::UInt128 # Can store 16 rotations, good enough for 2x2x2
n::UInt8 # Number of rotations in the set
end
RotationSet() = RotationSet(UInt128(0), UInt8(0))
const EMPTY_ROT = RotationSet()

function Base.show(io::IO, set::RotationSet)
print(io, '[')
for i in 1:set.n
shift = 8 * (16 - i)
print(io, Rotation(UInt8((set.r << shift) >> 8*15)))
i != set.n && print(io, ", ")
end
print(io, ']')
end
``````
``````julia> EMPTY_ROT
[]
``````

Adding a rotation to the rotation set is done by shifting the `UInt8` the correct amount

``````function Base.:*(set::RotationSet, rot::Rotation)
return RotationSet(set.r | (UInt128(rot.r) << UInt(8) * set.n), set.n + UInt8(1))
end
``````
``````julia> EMPTY_ROT * R * t * T * f
[R, t, T, f]

julia> typeof(ans)
RotationSet
``````

Running the code again (with some tweaks) we get

``````const Tv = Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const tv = Int8.((3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20))
const Fv = Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const fv = Int8.((0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20))
const Rv = Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))
const rv = Int8.((0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15))

function upstates(statesdict,state, set)
I = ntuple(i -> state ÷ 21^(6-i) % 21 + 1, Val{6}())
for (v, rot) in zip((Tv, tv, Fv, fv, Rv, rv), (T, t, F, f, R, r))
s = Int32(0)
@inbounds for i in 1:6
s += Int32(v[I[i]] * 21^(5-i+1))
end
get!(statesdict, s, set * rot)
end
end

function me()
statesdict = OrderedDict{Int32,RotationSet}(643245 => RotationSet())

for state in keys(statesdict)
upstates(statesdict, state, statesdict[643245])
end
statesdict
end

using DataStructures
using BenchmarkTools
using StaticArrays
@time result = me()
``````
``````julia> @time result = me()
4.742019 seconds (8.67 k allocations: 178.256 MiB, 2.24% gc time)
``````

The dictionary is probably the bottle neck now.

#14

I just edited my code because I made a mistake with the rotations (needed to save the reverse order of the inverse rotations to have the good solutions in the dictionary)

I added 3 functions for the ones who want to play around
a function to get the cube from the states:
it is very ugly lol

``````function cube(state)
p=digits(state,21,6)
c=setdiff(0:6,div.(p,3))[1]*3+(2*sum(p)%3)
return Int8[p[6],p[6]-p[6]%3+(p[6]+1)%3,p[6]-p[6]%3+(p[6]+2)%3,p[5],p[5]-p[5]%3+(p[5]+1)%3,p[5]-p[5]%3+(p[5]+2)%3,p[4],p[4]-p[4]%3+(p[4]+1)%3,p[4]-p[4]%3+(p[4]+2)%3,p[3],p[3]-p[3]%3+(p[3]+1)%3,p[3]-p[3]%3+(p[3]+2)%3,p[2],p[2]-p[2]%3+(p[2]+1)%3,p[2]-p[2]%3+(p[2]+2)%3,p[1],p[1]-p[1]%3+(p[1]+1)%3,p[1]-p[1]%3+(p[1]+2)%3,c,3*(c÷3)+(c+1)%3,3*(c÷3)+(c+2)%3]
end
``````

a function to get the state from any cube:

``````function state(cube)
return Int32(cube[1]*21^5+cube[4]*21^4+cube[7]*21^3+cube[10]*21^2+cube[13]*21+cube[16])
end

``````

a function to applies rotations on the cube:

``````function move(cube,movement)
for rot in movement
if rot=='T'
cube=T[cube+1]
else if rot=='t'
cube=t[cube+1]
else if rot=='F'
cube=F[cube+1]
else if rot=='f'
cube=f[cube+1]
else if rot=='R'
cube=R[cube+1]
else if rot=='r'
cube=r[cube+1]
end
end
return cube
end
``````

@kristoffer.carlsson waaa you made a fine improvements in such a short time + your tweaks are neat!
can you update the rotations issues? (at the end of the get! it should be “t” for the T rotation)
I am still trying to understand some parts.
what about @inbounds in front of get! and the constants issues that point out @bernhard was it something real?

Thanks you very mutch all!

#15

Inbounds in front of `get!` should make no difference because the `get` calls has to do quite some work. I think the biggest difference there was to not have the `statesdict` as a global.

#16

This make my pc CRASH, any Ideas why?

``````using DataStructures

const T=Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const t=Int8.((3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20))
const F=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const f=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20))
const R=Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))
const r=Int8.((0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15))

function upstates(state,statesdict)
push!(statesdict,T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1])
push!(statesdict,t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1])
push!(statesdict,F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1])
push!(statesdict,f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1])
push!(statesdict,R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1])
push!(statesdict,r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1])
end

function me()
statesdict = OrderedSet{Int32}(643245)
for i in statesdict
upstates(i,statesdict)
end
statesdict
end

@time result=me()
``````

#17

push! vs get! ?

@kristoffer.carlsson
I have a bit of code for a dict replacement, as it possibly doesn’t really need to do retrieval here

``````struct xbloom2
m1::Int32
m2::Int32
v3::BitArray{2}
xbloom2(x) = new(x,x+1, BitArray(x, x+1))
end;

function checkval!(xb::xbloom2, checkval::Int, setval=0)
i1 = (checkval % xb.m1) + 1;
i2 = (checkval % xb.m2) + 1;
if(setval==1)
if(!xb.v3[i1, i2])
xb.v3[i1, i2] = true;
return(true);
end;
return(false);
end;
return(xb.v3[i1, i2]);
end;

##initializing
local bloomlist = xbloom2(round(Int, 10 + sqrt(stateid(collect(Int8, 21:-1:1)))));
bloomlist.v3[:] = false;``````

#18

OKAY I think we did something amazing, here is my last version:

``````using DataStructures

const T=Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const F=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const R=Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))

function upstates(state,rot,statesdict)
get!(statesdict,T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1],rot%100==22 ? rot÷10-1 : rot*10+2)
get!(statesdict,F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1],rot%100==44 ? rot÷10-1 : rot*10+4)
get!(statesdict,R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1],rot%100==66 ? rot÷10-1 : rot*10+6)
end

function m()
statesdict = OrderedDict{Int32,Int64}(643245=>0)
for i in keys(statesdict)
upstates(i,statesdict[i],statesdict)
end
return statesdict
end

@time result=m()
``````

After computing result
You can get the string version of the solutions by using this simple function (you have to caus the order is inversed in the int64 value)

``````function strsolution(state)
const rotval=['T','t','F','f','R','r']
return String(rotval[digits(result[state])])
end
``````

you can replace whitout any others changes this:

``````const T=Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const F=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const R=Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))
``````

by this:(it is slightly slower, I don’t get why exactly???)

``````const T=Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
const F=Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
const R=Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
``````

so you can use the move function describe on my post above.

I am currently amaze that it is this easy and fast to optimaly solve all the (2x2x2 rubik’s cube, poket cube, mini cube)'s states!

Any further remark is welcome!

@kristoffer.carlsson I think in your ntuple you should put Val{6} instead of Val{6}()

thank you everyone again.

I would like to make a package with some 3D visualization of the cube and some other options to set the cube ,etc,…
Can anyone put me on track because I have no ideas how to do that.

#19

just as with statesdict, you could also have the T,F and R as local variables.
This reduces the time by approximately 33% on my computer

``````using BenchmarkTools
using DataStructures

function upstates(state,rot,statesdict,F,T,R)
get!(statesdict,T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1],rot%100==22 ? rot÷10-1 : rot*10+2)
get!(statesdict,F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1],rot%100==44 ? rot÷10-1 : rot*10+4)
get!(statesdict,R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1],rot%100==66 ? rot÷10-1 : rot*10+6)
end

function m()
statesdict = OrderedDict{Int32,Int64}(643245=>0)
const T= Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
const F= Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
const R= Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
for i in keys(statesdict)
upstates(i,statesdict[i],statesdict,F,T,R)
end
return statesdict
end

#@btime result=m()
@benchmark m() #3.5 seconds
``````

#20

I figured the previous version with only three rotations(F,T,R) where not correct because some solutions are not the smallest possible!

here is a version witch find all the optimal solutions for every position of the cube, it is quite slow.(350s on my laptop)

``````using DataStructures

function upstates(state,rot,statesdict,T,t,F,f,R,r)
Tstate=T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1]
Tset=setrot(rot,2)
Tval=get!(statesdict,Tstate,Tset)
if Tval!=Tset && ndigits(asetvalue(Tval))==ndigits(asetvalue(Tset))
statesdict[Tstate]=statesdict[Tstate] ∪ Tset
end
tstate=t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1]
tset=setrot(rot,1)
tval=get!(statesdict,tstate,tset)
if tval!=tset && ndigits(asetvalue(tval))==ndigits(asetvalue(tset))
statesdict[tstate]=statesdict[tstate] ∪ tset
end
Fstate=F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1]
Fset=setrot(rot,4)
Fval=get!(statesdict,Fstate,Fset)
if Fval!=Fset && ndigits(asetvalue(Fval))==ndigits(asetvalue(Fset))
statesdict[Fstate]=statesdict[Fstate] ∪ Fset
end
fstate=f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1]
fset=setrot(rot,3)
fval=get!(statesdict,fstate,fset)
if fval!=fset && ndigits(asetvalue(fval))==ndigits(asetvalue(fset))
statesdict[fstate]=statesdict[fstate] ∪ fset
end
Rstate=R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1]
Rset=setrot(rot,6)
Rval=get!(statesdict,Rstate,Rset)
if Rval!=Rset && ndigits(asetvalue(Rval))==ndigits(asetvalue(Rset))
statesdict[Rstate]=statesdict[Rstate] ∪ Rset
end
rstate=r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1]
rset=setrot(rot,5)
rval=get!(statesdict,rstate,rset)
if rval!=rset && ndigits(asetvalue(rval))==ndigits(asetvalue(rset))
statesdict[rstate]=statesdict[rstate] ∪ rset
end
end

function asetvalue(set)
@inbounds for i in eachindex(set.dict.slots)
if set.dict.slots[i]==0x01
return set.dict.keys[i]
end
end
end

function setrot(S,r)
C=Set{Int64}()
for s in S
v=s*10+r
v=in(v%100,(11,33,55))?v+11:v
push!(C,v)
end
return C
end

function rotway(rot)
const rotval=['t','T','f','F','r','R']
str=""
while rot != 0
str = str*rotval[rot.%10]
rot ÷= 10
end
str
end

function rotstring(rot)
const rotval=['T','t','F','f','R','r']
str=""
while rot != 0
str = rotval[rot.%10]*str
rot ÷= 10
end
str
end

function cube(state)
cube=Int8[]
d=digits(state,21,6)
for i in 2*sum(d)%3+setdiff(0:6,d.÷3)[1]*3 ∪ d
unshift!(cube,i,3*(i÷3)+(i+1)%3,3*(i÷3)+(i+2)%3)
end
return cube
end

function state(cube)
return Int32(cube[1]*21^5+cube[4]*21^4+cube[7]*21^3+cube[10]*21^2+cube[13]*21+cube[16])
end

function move(cube,movement)
for rot in movement
if rot=='T'
cube=cube[T+1]
elseif rot=='t'
cube=cube[t+1]
elseif rot=='F'
cube=cube[F+1]
elseif rot=='f'
cube=cube[f+1]
elseif rot=='R'
cube=cube[R+1]
elseif rot=='r'
cube=cube[r+1]
end
end
return cube
end

function m()
statesdict = OrderedDict{Int32,Set{Int64}}(643245=>Set{Int64}(0))
const T=Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
const t=Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
const F=Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
const f=Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
const R=Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
const r=Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]
for i in keys(statesdict)
upstates(i,statesdict[i],statesdict,T,t,F,f,R,r)
end
return statesdict
end

@time statesdict=m()

gg=collect(values(statesdict))
``````

Thx you again