题解 | #Sudoku#

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;
}