题解 | #Sudoku#

// 用set去保存1-9个数字，再去每一列和每一行每个格子进行比对
// 相当于用空间去换时间
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
const arr = [];
void (async function () {
  // Write your code here
  while ((line = await readline())) {
    // 格式化数字
    arr.push(line.split(" ").map(Number));
  }
  const rows = new Array(9)
  const cols = new Array(9)
  const blocks = new Array(9)
  const options = [1, 2, 3, 4, 5, 6, 7, 8, 9];
  for (let i = 0; i < 9; i++) {
    rows[i] = new Set(options)
    cols[i] = new Set(options)
    blocks[i] = new Set(options)
  }
  // 计算当前处于第几个九宫格
  const getBlockIndex = (i, j) => (~~(i / 3)) * 3 + (~~(j / 3))
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (arr[i][j] !== 0) {
        rows[i].delete(arr[i][j])
        cols[j].delete(arr[i][j])
        blocks[getBlockIndex(i, j)].delete(arr[i][j])
      }
    }
  }
  function dfs(row, col) {
    if (col === 9) {
      row++;
      col = 0;
    }
    if (row === 9) {
      // 填完了
      return true;
    }
    // 如果不是0就不需要补充去填
    if (arr[row][col] !== 0) return dfs(row, col + 1);
    const blockIndex = getBlockIndex(row, col)
    // 递归1-9去补充数字
    for (let n = 1; n <= 9; n++) {
      // 必须三个set里面都存在这个数字不然的话就是有冲突
      if (!rows[row].has(n) || !cols[col].has(n) || !blocks[blockIndex].has(n))
        continue;
      arr[row][col] = n;
      rows[row].delete(n)
      cols[col].delete(n)
      blocks[blockIndex].delete(n)
      if (dfs(row, col + 1)) return true;
      // 如果下一个格子不能正常填入就false
      //  那么就不能填这个数字了 然后把这个数字补回去到set中
      arr[row][col] = 0;
      rows[row].add(n)
      cols[col].add(n)
      blocks[blockIndex].add(n)
    }
    // 尝试了1-9都完不成就返回false
    return false;
  }
  dfs(0, 0);
  arr.forEach((e) => console.log(e.join(" ")));
})();