98 lines
3.2 KiB
JavaScript
98 lines
3.2 KiB
JavaScript
class FifteenSolver {
|
|
constructor(n, g) {
|
|
this.Nr = [3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3];
|
|
this.Nc = [3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2];
|
|
this.n = 0;
|
|
this._n = 0;
|
|
this.N0 = new Array(100).fill(0);
|
|
this.N3 = new Array(100).fill('');
|
|
this.N4 = new Array(100).fill(0);
|
|
this.N2 = new Array(100).fill(0n);
|
|
this.N0[0] = n;
|
|
this.N2[0] = BigInt(g);
|
|
}
|
|
|
|
fY() {
|
|
if (this.N4[this.n] < this._n) return this.fN();
|
|
if (this.N2[this.n] === 0x123456789abcdef0n) {
|
|
let moves = '';
|
|
for (let g = 1; g <= this.n; g++) moves += this.N3[g];
|
|
console.log(`Solution found in ${this.n} moves: ${moves}`);
|
|
return true;
|
|
}
|
|
if (this.N4[this.n] === this._n) return this.fN();
|
|
return false;
|
|
}
|
|
|
|
fN() {
|
|
if (this.N3[this.n] !== 'u' && Math.floor(this.N0[this.n]/4) < 3) {
|
|
this.fI();
|
|
this.n++;
|
|
if (this.fY()) return true;
|
|
this.n--;
|
|
}
|
|
if (this.N3[this.n] !== 'd' && Math.floor(this.N0[this.n]/4) > 0) {
|
|
this.fG();
|
|
this.n++;
|
|
if (this.fY()) return true;
|
|
this.n--;
|
|
}
|
|
if (this.N3[this.n] !== 'l' && this.N0[this.n]%4 < 3) {
|
|
this.fE();
|
|
this.n++;
|
|
if (this.fY()) return true;
|
|
this.n--;
|
|
}
|
|
if (this.N3[this.n] !== 'r' && this.N0[this.n]%4 > 0) {
|
|
this.fL();
|
|
this.n++;
|
|
if (this.fY()) return true;
|
|
this.n--;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
fI() {
|
|
const g = (11 - this.N0[this.n]) * 4;
|
|
const a = this.N2[this.n] & (15n << BigInt(g));
|
|
this.N0[this.n + 1] = this.N0[this.n] + 4;
|
|
this.N2[this.n + 1] = this.N2[this.n] - a + (a << 16n);
|
|
this.N3[this.n + 1] = 'd';
|
|
this.N4[this.n + 1] = this.N4[this.n] + (this.Nr[Number(a >> BigInt(g))] <= Math.floor(this.N0[this.n]/4) ? 0 : 1);
|
|
}
|
|
|
|
fG() {
|
|
const g = (19 - this.N0[this.n]) * 4;
|
|
const a = this.N2[this.n] & (15n << BigInt(g));
|
|
this.N0[this.n + 1] = this.N0[this.n] - 4;
|
|
this.N2[this.n + 1] = this.N2[this.n] - a + (a >> 16n);
|
|
this.N3[this.n + 1] = 'u';
|
|
this.N4[this.n + 1] = this.N4[this.n] + (this.Nr[Number(a >> BigInt(g))] >= Math.floor(this.N0[this.n]/4) ? 0 : 1);
|
|
}
|
|
|
|
fE() {
|
|
const g = (14 - this.N0[this.n]) * 4;
|
|
const a = this.N2[this.n] & (15n << BigInt(g));
|
|
this.N0[this.n + 1] = this.N0[this.n] + 1;
|
|
this.N2[this.n + 1] = this.N2[this.n] - a + (a << 4n);
|
|
this.N3[this.n + 1] = 'r';
|
|
this.N4[this.n + 1] = this.N4[this.n] + (this.Nc[Number(a >> BigInt(g))] <= this.N0[this.n]%4 ? 0 : 1);
|
|
}
|
|
|
|
fL() {
|
|
const g = (16 - this.N0[this.n]) * 4;
|
|
const a = this.N2[this.n] & (15n << BigInt(g));
|
|
this.N0[this.n + 1] = this.N0[this.n] - 1;
|
|
this.N2[this.n + 1] = this.N2[this.n] - a + (a >> 4n);
|
|
this.N3[this.n + 1] = 'l';
|
|
this.N4[this.n + 1] = this.N4[this.n] + (this.Nc[Number(a >> BigInt(g))] >= this.N0[this.n]%4 ? 0 : 1);
|
|
}
|
|
|
|
solve() {
|
|
while (!this.fY()) this._n++;
|
|
}
|
|
}
|
|
|
|
const start = new FifteenSolver(8, '0xfe169b4c0a73d852');
|
|
start.solve();
|