题解 | #Sudoku#
Sudoku
https://www.nowcoder.com/practice/78a1a4ebe8a34c93aac006c44f6bf8a1
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let data = [];
rl.on("line", function (line) {
data.push(line.trim().split(" "));
});
rl.on("close", function () {
resolveSudo();
data.forEach((row) => {
console.log(row.join(" "));
});
});
function resolveSudo() {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (data[i][j] !== "0") continue;
// 检测到了0 填充
for (let k = 1; k <= 9; k++) {
// 两个判断，数独是否有效，剩下的 0 是否能被填充
if (isValidSodu(i, j, `${k}`)) {
// 有效则填
data[i][j] = `${k}`;
// 并且满足剩下的数独是合理的
if (resolveSudo()) {
return true;
}
// 如果剩下的不满足，返回充填
data[i][j] = "0";
}
}
// 1-9 都试过了，都不行，那就返回false
return false;
}
}
// 遍历完了没有0了, 说明位置是合适的了
return true;
}
function isValidSodu(i, j, k) {
// 每一列不能重复
for (let m = 0; m < 9; m++) {
if (data[m][j] == k) return false;
}
// 每一行不能重复
for (let n = 0; n < 9; n++) {
if (data[i][n] == k) return false;
}
// 每一个 3 * 3 的九宫格也不能为0
let rowStart = Math.floor(i / 3) * 3;
let colStart = Math.floor(j / 3) * 3;
for (let m = 0; m < 3; m++) {
for (let n = 0; n < 3; n++) {
if (data[rowStart + m][colStart + n] == k) return false;
}
}
return true;
}
