15 puzzle solver: Difference between revisions
Content deleted Content added
Realize in Pascal |
Neater C++ solution |
||
Line 38: | Line 38: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
===Staying Functional (as possible in C++)=== |
|||
====The Solver==== |
|||
{{trans|FSharp}} |
|||
<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> |
|||
{{out}} |
|||
<pre> |
|||
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd |
|||
real 0m2.897s |
|||
user 0m2.887s |
|||
sys 0m0.008s |
|||
</pre> |
|||
===Time to get Imperative=== |
|||
[http://www.rosettacode.org/wiki/15_puzzle_solver/20_Random see] for an analysis of 20 randomly generated 15 puzzles solved with this solver. |
[http://www.rosettacode.org/wiki/15_puzzle_solver/20_Random see] for an analysis of 20 randomly generated 15 puzzles solved with this solver. |
||
====The Solver==== |
====The Solver==== |
||
Line 132: | Line 43: | ||
// Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017 |
// Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017 |
||
class fifteenSolver{ |
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 |
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}; |
||
int n{},_n{}, N0[ |
int n{},_n{}, N0[100]{},N3[100]{},N4[100]{}; |
||
unsigned long N2[ |
unsigned long N2[100]{}; |
||
const bool fY(){ |
const bool fY(){ |
||
if (N2[n]==0x123456789abcdef0) return true; |
if (N2[n]==0x123456789abcdef0) {std::cout<<"Solution found in "<<n<<" moves :"; for (int g{1};g<=n;++g) std::cout<<(char)N3[g]; std::cout<<std::endl; return true;}; |
||
if (N4[n]<=_n) return fN(); |
if (N4[n]<=_n) return fN(); |
||
return false; |
return false; |
||
} |
} |
||
const bool |
const bool fN(){ |
||
if ( |
if (N3[n]!='u' && N0[n]/4<3){fI(); ++n; if (fY()) return true; --n;} |
||
if ( |
if (N3[n]!='d' && N0[n]/4>0){fG(); ++n; if (fY()) return true; --n;} |
||
if ( |
if (N3[n]!='l' && N0[n]%4<3){fE(); ++n; if (fY()) return true; --n;} |
||
if ( |
if (N3[n]!='r' && N0[n]%4>0){fL(); ++n; if (fY()) return true; --n;} |
||
return false; |
return false; |
||
} |
|||
const bool fN(){ |
|||
switch(N0[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);} |
|||
case 1: case 2: switch(N3[n]){case 'l': return fZ(i+l); |
|||
case 'r': return fZ(i+e); |
|||
case 'u': return fZ(e+l); |
|||
default : return fZ(l+e+i);} |
|||
case 12: switch(N3[n]){case 'l': return fZ(g); |
|||
case 'd': return fZ(e); |
|||
default : return fZ(e+g);} |
|||
case 15: switch(N3[n]){case 'r': return fZ(g); |
|||
case 'd': return fZ(l); |
|||
default : return fZ(g+l);} |
|||
case 13: case 14: 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);} |
|||
case 4: case 8: 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 7: case 11: 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(){ |
void fI(){ |
||
const int g = (11-N0[n])*4; |
const int g = (11-N0[n])*4; |
||
const unsigned long a = N2[n]&((unsigned long)15<<g); |
const unsigned long a = N2[n]&((unsigned long)15<<g); |
||
N0[n+1]=N0[n]+4; N2[n+1]=N2[n]-a+(a<<16); N3[n+1]='d'; N4[n+1]=N4[n]+(Nr[a>>g]<=N0[n |
N0[n+1]=N0[n]+4; N2[n+1]=N2[n]-a+(a<<16); N3[n+1]='d'; N4[n+1]=N4[n]+(Nr[a>>g]<=N0[n]/4?0:1); |
||
} |
} |
||
void fG(){ |
void fG(){ |
||
const int g = (19-N0[n])*4; |
const int g = (19-N0[n])*4; |
||
const unsigned long a = N2[n]&((unsigned long)15<<g); |
const unsigned long a = N2[n]&((unsigned long)15<<g); |
||
N0[n+1]=N0[n]-4; N2[n+1]=N2[n]-a+(a>>16); N3[n+1]='u'; N4[n+1]=N4[n]+(Nr[a>>g]>=N0[n |
N0[n+1]=N0[n]-4; N2[n+1]=N2[n]-a+(a>>16); N3[n+1]='u'; N4[n+1]=N4[n]+(Nr[a>>g]>=N0[n]/4?0:1); |
||
} |
} |
||
void fE(){ |
void fE(){ |
||
const int g = (14-N0[n])*4; |
const int g = (14-N0[n])*4; |
||
const unsigned long a = N2[n]&((unsigned long)15<<g); |
const unsigned long a = N2[n]&((unsigned long)15<<g); |
||
N0[n+1]=N0[n]+1; N2[n+1]=N2[n]-a+(a<<4); N3[n+1]='r'; N4[n+1]=N4[n]+(Nc[a>>g]<=N0[n |
N0[n+1]=N0[n]+1; N2[n+1]=N2[n]-a+(a<<4); N3[n+1]='r'; N4[n+1]=N4[n]+(Nc[a>>g]<=N0[n]%4?0:1); |
||
} |
} |
||
void fL(){ |
void fL(){ |
||
const int g = (16-N0[n])*4; |
const int g = (16-N0[n])*4; |
||
const unsigned long a = N2[n]&((unsigned long)15<<g); |
const unsigned long a = N2[n]&((unsigned long)15<<g); |
||
N0[n+1]=N0[n]-1; N2[n+1]=N2[n]-a+(a>>4); N3[n+1]='l'; N4[n+1]=N4[n]+(Nc[a>>g]>=N0[n |
N0[n+1]=N0[n]-1; N2[n+1]=N2[n]-a+(a>>4); N3[n+1]='l'; N4[n+1]=N4[n]+(Nc[a>>g]>=N0[n]%4?0:1); |
||
} |
} |
||
public: |
public: |
||
fifteenSolver(int n, unsigned long g){N0[0]=n; N2[0]=g |
fifteenSolver(int n, unsigned long g){N0[0]=n; N2[0]=g;} |
||
void Solve(){ |
void Solve(){for(;not fY();++_n);} |
||
if (fN()) {std::cout<<"Solution found in "<<n<<" moves: "; for (int g{1};g<=n;++g) std::cout<<(char)N3[g]; std::cout<<std::endl;} |
|||
else {n=0; ++_n; Solve();} |
|||
} |
|||
}; |
}; |
||
</lang> |
</lang> |
||
Line 225: | Line 98: | ||
sys 0m0.000s |
sys 0m0.000s |
||
</pre> |
</pre> |
||
====Extra Credit==== |
|||
I have updated the 20 random examples, which showed n the number of moves to include _n. As seen when _n is less than 10 the puzzle is solved quickly. This suggests a multi-threading strategy. I have 8 cores available. Modifying solve so that it starts a thread for _n=0 to _n=9, 1 for _n=10, 1 for _n=11, 1 for _n=12, and 1 for _n=13 tests that the fan is still working and turns the computer into a hair-dryer. It also finds the following solution to the extra credit task: |
|||
<pre> |
|||
Solution found in 80 moves: dddrurdruuulllddrulddrrruuullddruulldddrrurulldrruulldlddrurullddrrruullulddrdrr |
|||
</pre> |
|||
in 29m19.973s.<br> |
|||
It also solves the 5th. example which requires 29.3s single threaded in 7s. |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===The Function=== |
===The Function=== |