114 lines
2.1 KiB
JavaScript
114 lines
2.1 KiB
JavaScript
let board = [];
|
|
let start = [];
|
|
let given = [];
|
|
|
|
function setup(input) {
|
|
/* This task is not about input validation, so
|
|
we're going to trust the input to be valid */
|
|
const puzzle = input.map(line => line.split(/\s+/));
|
|
const nCols = puzzle[0].length;
|
|
const nRows = puzzle.length;
|
|
let list = new Array(nRows * nCols);
|
|
|
|
board = Array(nRows + 2).fill().map(() =>
|
|
Array(nCols + 2).fill(-1)
|
|
);
|
|
|
|
for (let r = 0; r < nRows; r++) {
|
|
const row = puzzle[r];
|
|
for (let c = 0; c < nCols; c++) {
|
|
const cell = row[c];
|
|
switch (cell) {
|
|
case "_":
|
|
board[r + 1][c + 1] = 0;
|
|
break;
|
|
case ".":
|
|
break;
|
|
default:
|
|
const val = parseInt(cell, 10);
|
|
board[r + 1][c + 1] = val;
|
|
list.push(val);
|
|
if (val === 1) {
|
|
start = [r + 1, c + 1];
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
list.sort((a, b) => a - b);
|
|
given = [...list];
|
|
}
|
|
|
|
function solve(r, c, n, next) {
|
|
if (n > given[given.length - 1]) {
|
|
return true;
|
|
}
|
|
|
|
const back = board[r][c];
|
|
if (back !== 0 && back !== n) {
|
|
return false;
|
|
}
|
|
|
|
if (back === 0 && given[next] === n) {
|
|
return false;
|
|
}
|
|
|
|
if (back === n) {
|
|
next++;
|
|
}
|
|
|
|
board[r][c] = n;
|
|
for (let i = -1; i < 2; i++) {
|
|
for (let j = -1; j < 2; j++) {
|
|
if (solve(r + i, c + j, n + 1, next)) {
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
|
|
board[r][c] = back;
|
|
return false;
|
|
}
|
|
|
|
function printBoard() {
|
|
for (const row of board) {
|
|
let rowStr = '';
|
|
for (const c of row) {
|
|
switch (true) {
|
|
case c === -1:
|
|
rowStr += ' . ';
|
|
break;
|
|
case c > 0:
|
|
rowStr += c.toString().padStart(2) + ' ';
|
|
break;
|
|
default:
|
|
rowStr += '__ ';
|
|
break;
|
|
}
|
|
}
|
|
console.log(rowStr);
|
|
}
|
|
}
|
|
|
|
function main() {
|
|
const input = [
|
|
"_ 33 35 _ _ . . .",
|
|
"_ _ 24 22 _ . . .",
|
|
"_ _ _ 21 _ _ . .",
|
|
"_ 26 _ 13 40 11 . .",
|
|
"27 _ _ _ 9 _ 1 .",
|
|
". . _ _ 18 _ _ .",
|
|
". . . . _ 7 _ _",
|
|
". . . . . . 5 _"
|
|
];
|
|
|
|
setup(input);
|
|
printBoard();
|
|
console.log("\nFound:");
|
|
solve(start[0], start[1], 1, 0);
|
|
printBoard();
|
|
}
|
|
|
|
main();
|