147 lines
3.3 KiB
JavaScript
147 lines
3.3 KiB
JavaScript
class Node {
|
|
constructor() {
|
|
this.val = 0;
|
|
this.neighbors = 0;
|
|
}
|
|
}
|
|
|
|
class NSolver {
|
|
constructor() {
|
|
this.dx = new Array(8);
|
|
this.dy = new Array(8);
|
|
this.wid = 0;
|
|
this.hei = 0;
|
|
this.max = 0;
|
|
this.arr = null;
|
|
|
|
this.dx[0] = -2; this.dy[0] = -2; this.dx[1] = -2; this.dy[1] = 2;
|
|
this.dx[2] = 2; this.dy[2] = -2; this.dx[3] = 2; this.dy[3] = 2;
|
|
this.dx[4] = -3; this.dy[4] = 0; this.dx[5] = 3; this.dy[5] = 0;
|
|
this.dx[6] = 0; this.dy[6] = -3; this.dx[7] = 0; this.dy[7] = 3;
|
|
}
|
|
|
|
solve(puzz, maxWid) {
|
|
if (puzz.length < 1) return;
|
|
|
|
this.wid = maxWid;
|
|
this.hei = Math.floor(puzz.length / this.wid);
|
|
const len = this.wid * this.hei;
|
|
let c = 0;
|
|
this.max = len;
|
|
|
|
this.arr = new Array(len);
|
|
for (let i = 0; i < len; i++) {
|
|
this.arr[i] = new Node();
|
|
}
|
|
|
|
for (let i = 0; i < puzz.length; i++) {
|
|
if (puzz[i] === "*") {
|
|
this.max--;
|
|
this.arr[c++].val = -1;
|
|
continue;
|
|
}
|
|
// Handle both "." and number cases properly
|
|
this.arr[c].val = puzz[i] === "." ? 0 : parseInt(puzz[i]);
|
|
c++;
|
|
}
|
|
|
|
this.solveIt();
|
|
|
|
c = 0;
|
|
for (let i = 0; i < puzz.length; i++) {
|
|
if (puzz[i] === ".") {
|
|
puzz[i] = this.arr[c].val.toString();
|
|
}
|
|
c++;
|
|
}
|
|
|
|
return puzz;
|
|
}
|
|
|
|
search(x, y, w) {
|
|
if (w > this.max) return true;
|
|
|
|
const n = this.arr[x + y * this.wid];
|
|
n.neighbors = this.getNeighbors(x, y);
|
|
|
|
for (let d = 0; d < 8; d++) {
|
|
if (n.neighbors & (1 << d)) {
|
|
const a = x + this.dx[d];
|
|
const b = y + this.dy[d];
|
|
if (this.arr[a + b * this.wid].val === 0) {
|
|
this.arr[a + b * this.wid].val = w;
|
|
if (this.search(a, b, w + 1)) return true;
|
|
this.arr[a + b * this.wid].val = 0;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
getNeighbors(x, y) {
|
|
let c = 0;
|
|
for (let xx = 0; xx < 8; xx++) {
|
|
const a = x + this.dx[xx];
|
|
const b = y + this.dy[xx];
|
|
if (a < 0 || b < 0 || a >= this.wid || b >= this.hei) continue;
|
|
if (this.arr[a + b * this.wid].val > -1) c |= (1 << xx);
|
|
}
|
|
return c;
|
|
}
|
|
|
|
solveIt() {
|
|
const result = this.findStart();
|
|
if (result.z === 99999) {
|
|
console.log("\nCan't find start point!\n");
|
|
return;
|
|
}
|
|
this.search(result.x, result.y, result.z + 1);
|
|
}
|
|
|
|
findStart() {
|
|
for (let b = 0; b < this.hei; b++) {
|
|
for (let a = 0; a < this.wid; a++) {
|
|
if (this.arr[a + this.wid * b].val === 0) {
|
|
const x = a;
|
|
const y = b;
|
|
const z = 1;
|
|
this.arr[a + this.wid * b].val = z;
|
|
return { x, y, z };
|
|
}
|
|
}
|
|
}
|
|
return { x: 0, y: 0, z: 99999 };
|
|
}
|
|
}
|
|
|
|
function main() {
|
|
const wid = 7;
|
|
const p = "* . . * . . * . . . . . . . . . . . . . . * . . . . . * * * . . . * * * * * . * * *";
|
|
const puzz = p.split(" ");
|
|
|
|
const solver = new NSolver();
|
|
const result = solver.solve(puzz, wid);
|
|
|
|
let c = 0;
|
|
let output = "";
|
|
|
|
for (let i = 0; i < result.length; i++) {
|
|
if (result[i] !== "*" && result[i] !== ".") {
|
|
const num = parseInt(result[i]);
|
|
if (!isNaN(num) && num < 10) output += "0";
|
|
output += result[i] + " ";
|
|
} else {
|
|
output += " ";
|
|
}
|
|
|
|
if (++c >= wid) {
|
|
output += "\n";
|
|
c = 0;
|
|
}
|
|
}
|
|
|
|
console.log(output);
|
|
}
|
|
|
|
main();
|