15 puzzle solver: Difference between revisions

Content added Content deleted
Line 130:
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]{},N1N3[85]{},N3N4[85]{},N4[85];
unsigned long N2[85]{};
const bool fUfY(){
if (N2[n]==0x123456789abcdef0) return true;
if (N4[n]<=_n) return fN();
return false;
}
const bool fZ(const int w){
if ((w&i)>0){fI(); if (fUfY()) return true; --n;}
if ((w&g)>0){fG(); if (fUfY()) return true; --n;}
if ((w&e)>0){fE(); if (fUfY()) return true; --n;}
if ((w&l)>0){fL(); if (fUfY()) return true; --n;}
return false;
}
const 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: case 3: switch(N3[n]){case 'r': return fZ(i);
case 'u': return fZ(l);
default : return fZ(i+l);}
case 1: case default2: switch(N3[n]){case 'l': return fZ(i+l);
case 'r': return fZ(i+e);
case 'u': return fZ(e+l);
default : return fZ(il+e+li);}}
case 312: switch(N1[n]){case 0: switch(N3[n]){case 'l': return fZ(g);
case 'd': return fZ(e);
default : return fZ(e+g);}
case 15: case 3: switch(N3[n]){case 'r': return fZ(g);
case 'd': return fZ(l);
default : return fZ(g+l);}
case 13: case default14: 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);}}
defaultcase 4: switch(N1[n]){case 08: 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 311: 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: 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(){
const int g = (11-N1[n]-N0[n]*4)*4;
const unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]+1; N1[n+1]=N1[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(){
const int g = (19-N1[n]-N0[n]*4)*4;
const unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]-1; N1[n+1]=N1[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(){
const int g = (14-N1[n]-N0[n]*4)*4;
const 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]<=N1N0[n++]%4?0:1);
}
void fL(){
const int g = (16-N1[n]-N0[n]*4)*4;
const 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]>=N1N0[n++]%4?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;}
Line 210:
<lang cpp>
int main (){
fifteenSolver start(2,08,0xfe169b4c0a73d852);
start.Solve();
}