15 puzzle solver
You are encouraged to solve this task according to the task description, using any language you may know.
Your task is to write a program that finds a solution in the fewest single moves (no multimoves) possible to a random Fifteen Puzzle Game.
For this task you will be using the following puzzle:
15 14 1 6 9 11 4 12 0 10 7 3 13 8 5 2
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
The output must show the moves' directions, like so: left, left, left, down, right... and so on.
There are 2 solutions with 52 moves:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
finding either one, or both is an acceptable result.
see: Pretty Print of Optimal Solution
- Extra credit.
Solve the following problems:
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 0
and
0 12 9 13 15 11 10 14 3 7 2 5 4 8 6 1
- Related Tasks
C++
Staying Functional (as possible in C++)
The Solver
<lang cpp> // Solve Random 15 Puzzles : Nigel Galloway - October 11th., 2017 const int Nr[]{3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}, Nc[]{3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}; using N = std::tuple<int,int,unsigned long,std::string,int>; void fN(const N,const int); const N fI(const N n){
int g = (11-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n)+1,std::get<1>(n),std::get<2>(n)-a+(a<<16),std::get<3>(n)+"d",(Nr[a>>g]<=std::get<0>(n))?std::get<4>(n):std::get<4>(n)+1);
} const N fG(const N n){
int g = (19-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n)-1,std::get<1>(n),std::get<2>(n)-a+(a>>16),std::get<3>(n)+"u",(Nr[a>>g]>=std::get<0>(n))?std::get<4>(n):std::get<4>(n)+1);
} const N fE(const N n){
int g = (14-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n),std::get<1>(n)+1,std::get<2>(n)-a+(a<<4),std::get<3>(n)+"r",(Nc[a>>g]<=std::get<1>(n))?std::get<4>(n):std::get<4>(n)+1);
} const N fL(const N n){
int g = (16-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n),std::get<1>(n)-1,std::get<2>(n)-a+(a>>4),std::get<3>(n)+"l",(Nc[a>>g]>=std::get<1>(n))?std::get<4>(n):std::get<4>(n)+1);
} void fZ(const N n, const int g){
if (std::get<2>(n)==0x123456789abcdef0){
int g{};for (char a: std::get<3>(n)) ++g;
std::cout<<"Solution found with "<<g<<" moves: "<<std::get<3>(n)<<std::endl; exit(0);}
if (std::get<4>(n) <= g) fN(n,g);
} void fN(const N n, const int g){
const int i{std::get<0>(n)}, e{std::get<1>(n)}, l{std::get<3>(n).back()};
switch(i){case 0: switch(e){case 0: switch(l){case 'l': fZ(fI(n),g); return;
case 'u': fZ(fE(n),g); return;
default : fZ(fE(n),g); fZ(fI(n),g); return;}
case 3: switch(l){case 'r': fZ(fI(n),g); return;
case 'u': fZ(fL(n),g); return;
default : fZ(fL(n),g); fZ(fI(n),g); return;}
default: switch(l){case 'l': fZ(fI(n),g); fZ(fL(n),g); return;
case 'r': fZ(fI(n),g); fZ(fE(n),g); return;
case 'u': fZ(fE(n),g); fZ(fL(n),g); return;
default : fZ(fL(n),g); fZ(fI(n),g); fZ(fE(n),g); return;}}
case 3: switch(e){case 0: switch(l){case 'l': fZ(fG(n),g); return;
case 'd': fZ(fE(n),g); return;
default : fZ(fE(n),g); fZ(fG(n),g); return;}
case 3: switch(l){case 'r': fZ(fG(n),g); return;
case 'd': fZ(fL(n),g); return;
default : fZ(fL(n),g); fZ(fG(n),g); return;}
default: switch(l){case 'l': fZ(fG(n),g); fZ(fL(n),g); return;
case 'r': fZ(fG(n),g); fZ(fE(n),g); return;
case 'd': fZ(fE(n),g); fZ(fL(n),g); return;
default : fZ(fL(n),g); fZ(fG(n),g); fZ(fE(n),g); return;}}
default: switch(e){case 0: switch(l){case 'l': fZ(fI(n),g); fZ(fG(n),g); return;
case 'u': fZ(fE(n),g); fZ(fG(n),g); return;
case 'd': fZ(fE(n),g); fZ(fI(n),g); return;
default : fZ(fE(n),g); fZ(fI(n),g); fZ(fG(n),g); return;}
case 3: switch(l){case 'd': fZ(fI(n),g); fZ(fL(n),g); return;
case 'u': fZ(fL(n),g); fZ(fG(n),g); return;
case 'r': fZ(fI(n),g); fZ(fG(n),g); return;
default : fZ(fL(n),g); fZ(fI(n),g); fZ(fG(n),g); return;}
default: switch(l){case 'd': fZ(fI(n),g); fZ(fL(n),g); fZ(fE(n),g); return;
case 'l': fZ(fI(n),g); fZ(fL(n),g); fZ(fG(n),g); return;
case 'r': fZ(fI(n),g); fZ(fE(n),g); fZ(fG(n),g); return;
case 'u': fZ(fE(n),g); fZ(fL(n),g); fZ(fG(n),g); return;
default : fZ(fL(n),g); fZ(fI(n),g); fZ(fE(n),g); fZ(fG(n),g); return;}}}
} void Solve(N n){for(int g{};;++g) fN(n,g);} </lang>
The Task
<lang cpp> int main (){
N start(2,0,0xfe169b4c0a73d852,"",0); Solve(start);
} </lang>
- Output:
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd real 0m2.897s user 0m2.887s sys 0m0.008s
Time to get Imperative
see for an analysis of 20 randomly generated 15 puzzles solved with this solver.
The Solver
<lang cpp> // Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017 class fifteenSolver{
const int Nr[16]{3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}, Nc[16]{3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}, i{1}, g{8}, e{2}, l{4};
int n{},_n{}, N0[85]{},N1[85]{},N3[85]{},N4[85];
unsigned long N2[85]{};
bool fU(){
if (N2[n]==0x123456789abcdef0) return true;
if (N4[n]<=_n) return fN();
return false;
}
bool fZ(const int w){
int a = n;
if ((w&i)>0){fI(); if (fU()) return true; n=a;}
if ((w&g)>0){fG(); if (fU()) return true; n=a;}
if ((w&e)>0){fE(); if (fU()) return true; n=a;}
if ((w&l)>0){fL(); return fU();}
return false;
}
bool fN(){
switch(N0[n]){case 0: switch(N1[n]){case 0: switch(N3[n]){case 'l': return fZ(i);
case 'u': return fZ(e);
default : return fZ(i+e);}
case 3: switch(N3[n]){case 'r': return fZ(i);
case 'u': return fZ(l);
default : return fZ(i+l);}
default: switch(N3[n]){case 'l': return fZ(i+l);
case 'r': return fZ(i+e);
case 'u': return fZ(e+l);
default : return fZ(i+e+l);}}
case 3: switch(N1[n]){case 0: switch(N3[n]){case 'l': return fZ(g);
case 'd': return fZ(e);
default : return fZ(e+g);}
case 3: switch(N3[n]){case 'r': return fZ(g);
case 'd': return fZ(l);
default : return fZ(g+l);}
default: switch(N3[n]){case 'l': return fZ(g+l);
case 'r': return fZ(e+g);
case 'd': return fZ(e+l);
default : return fZ(g+e+l);}}
default: switch(N1[n]){case 0: switch(N3[n]){case 'l': return fZ(i+g);
case 'u': return fZ(g+e);
case 'd': return fZ(i+e);
default : return fZ(i+g+e);}
case 3: switch(N3[n]){case 'd': return fZ(i+l);
case 'u': return fZ(g+l);
case 'r': return fZ(i+g);
default : return fZ(i+g+l);}
default: switch(N3[n]){case 'd': return fZ(i+e+l);
case 'l': return fZ(i+g+l);
case 'r': return fZ(i+g+e);
case 'u': return fZ(g+e+l);
default : return fZ(i+g+e+l);}}}
}
void fI(){
int g = (11-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]+1; N1[n+1]=N1[n]; N2[n+1]=N2[n]-a+(a<<16); N3[n+1]='d'; N4[n+1]=N4[n]+(Nr[a>>g]<=N0[n++]?0:1);
}
void fG(){
int g = (19-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]-1; N1[n+1]=N1[n]; N2[n+1]=N2[n]-a+(a>>16); N3[n+1]='u'; N4[n+1]=N4[n]+(Nr[a>>g]>=N0[n++]?0:1);
}
void fE(){
int g = (14-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]; N1[n+1]=N1[n]+1; N2[n+1]=N2[n]-a+(a<<4); N3[n+1]='r'; N4[n+1]=N4[n]+(Nc[a>>g]<=N1[n++]?0:1);
}
void fL(){
int g = (16-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]; N1[n+1]=N1[n]-1; N2[n+1]=N2[n]-a+(a>>4); N3[n+1]='l'; N4[n+1]=N4[n]+(Nc[a>>g]>=N1[n++]?0:1);
}
public:
fifteenSolver(int n, int i, unsigned long g){N0[0]=n; N1[0]=i; N2[0]=g; N4[0]=0;}
void Solve(){
while (not fN()){n=0;++_n;}
std::cout<<"Solution found in "<<n<<" moves: "; for (int g{1};g<=n;++g) std::cout<<(char)N3[g]; std::cout<<std::endl;
}
}; </lang>
The Task
<lang cpp> int main (){
fifteenSolver start(2,0,0xfe169b4c0a73d852); start.Solve();
} </lang>
- Output:
Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd real 0m0.795s user 0m0.794s sys 0m0.000s
F#
<lang fsharp> // A Naive 15 puzzle solver using no memory. Nigel Galloway: October 6th., 2017 let Nr = [|3;0;0;0;0;1;1;1;1;2;2;2;2;3;3;3|] let Nc = [|3;0;1;2;3;0;1;2;3;0;1;2;3;0;1;2|] let rec Solve n =
let rec fN (i,g,e,l,_) = seq {
let fI = let n = (11-g-i*4)*4
let a = (e&&&(15UL<<<n))
(i+1,g,e-a+(a<<<16),'d'::l,Nr.[(int (a>>>n))] <= i)
let fG = let n = (19-g-i*4)*4
let a = (e&&&(15UL<<<n))
(i-1,g,e-a+(a>>>16),'u'::l,Nr.[(int (a>>>n))] >= i)
let fE = let n = (14-g-i*4)*4
let a = (e&&&(15UL<<<n))
(i,g+1,e-a+(a<<<4), 'r'::l,Nc.[(int (a>>>n))] <= g)
let fL = let n = (16-g-i*4)*4
let a = (e&&&(15UL<<<n))
(i,g-1,e-a+(a>>>4), 'l'::l,Nc.[(int (a>>>n))] >= g)
let fZ (n,i,g,e,l) = seq{yield (n,i,g,e,l); if l then yield! fN (n,i,g,e,l)}
match (i,g,l) with
|(0,0,'l'::_) -> yield! fZ fI
|(0,0,'u'::_) -> yield! fZ fE
|(0,0,_) -> yield! fZ fI; yield! fZ fE
|(0,3,'r'::_) -> yield! fZ fI
|(0,3,'u'::_) -> yield! fZ fL
|(0,3,_) -> yield! fZ fI; yield! fZ fL
|(3,0,'l'::_) -> yield! fZ fG
|(3,0,'d'::_) -> yield! fZ fE
|(3,0,_) -> yield! fZ fE; yield! fZ fG
|(3,3,'r'::_) -> yield! fZ fG
|(3,3,'d'::_) -> yield! fZ fL
|(3,3,_) -> yield! fZ fG; yield! fZ fL
|(0,_,'l'::_) -> yield! fZ fI; yield! fZ fL
|(0,_,'r'::_) -> yield! fZ fI; yield! fZ fE
|(0,_,'u'::_) -> yield! fZ fE; yield! fZ fL
|(0,_,_) -> yield! fZ fI; yield! fZ fE; yield! fZ fL
|(_,0,'l'::_) -> yield! fZ fI; yield! fZ fG
|(_,0,'u'::_) -> yield! fZ fE; yield! fZ fG
|(_,0,'d'::_) -> yield! fZ fI; yield! fZ fE
|(_,0,_) -> yield! fZ fI; yield! fZ fE; yield! fZ fG
|(3,_,'l'::_) -> yield! fZ fG; yield! fZ fL
|(3,_,'r'::_) -> yield! fZ fE; yield! fZ fG
|(3,_,'d'::_) -> yield! fZ fE; yield! fZ fL
|(3,_,_) -> yield! fZ fE; yield! fZ fG; yield! fZ fL
|(_,3,'d'::_) -> yield! fZ fI; yield! fZ fL
|(_,3,'u'::_) -> yield! fZ fL; yield! fZ fG
|(_,3,'r'::_) -> yield! fZ fI; yield! fZ fG
|(_,3,_) -> yield! fZ fI; yield! fZ fL; yield! fZ fG
|(_,_,'d'::_) -> yield! fZ fI; yield! fZ fE; yield! fZ fL
|(_,_,'l'::_) -> yield! fZ fI; yield! fZ fG; yield! fZ fL
|(_,_,'r'::_) -> yield! fZ fI; yield! fZ fE; yield! fZ fG
|(_,_,'u'::_) -> yield! fZ fE; yield! fZ fG; yield! fZ fL
|_ -> yield! fZ fI; yield! fZ fE; yield! fZ fG; yield! fZ fL
}
let n = Seq.collect fN n
match (Seq.tryFind(fun(_,_,n,_,_)->n=0x123456789abcdef0UL)) n with
|Some(_,_,_,n,_) -> printf "Solution found with %d moves: " (List.length n); List.iter (string >> printf "%s") (List.rev n); printfn ""
|_ -> Solve (Seq.filter(fun (_,_,_,_,n)->not n) n)
Solve [(2,0,0xfe169b4c0a73d852UL,[],false)] </lang>
- Output:
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd