37.解数独

链接：37.解数独
难度：Hard
标签：数组、哈希表、回溯、矩阵
简介：编写一个程序，通过已填充的空格来解决数独问题。

题解 1 - typescript

• 编辑时间：2020-09-15
• 执行用时：96ms
• 内存消耗：38.4MB
• 编程语言：typescript
• 解法介绍：[参考连接](https://leetcode-cn.com/problems/sudoku-solver/solution/di-gui-hui-su-wei-yun-suan-by-zoffer-3/)。

class Sudoku {
  private rows = new Array(9).fill(0);
  private cols = new Array(9).fill(0);
  private boxs = Array.from({ length: 3 }, () => new Array(3).fill(0));
  private emptyCells = new Set<number>();
  constructor(private board: string[][]) {}
  solve() {
    //初始化已知的数字
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        const num = this.board[i][j];
        if (num !== '.') {
          //将数字转化为二进制标记
          //1 -> 0b1, 2 -> 0b10, 3 -> 0b100, 4 -> 0b1000 ...
          const sign = 1 << (Number(num) - 1);
          this.rows[i] |= sign;
          this.cols[j] |= sign;
          this.boxs[Math.floor(i / 3)][Math.floor(j / 3)] |= sign;
        } else {
          this.emptyCells.add((i << 4) | j);
        }
      }
    }
    //主逻辑
    return this.fillNext();
  }
  fillNext() {
    let cellInfo = this.getEmptyCell();
    if (cellInfo === null) {
      //没有空格，解题成功
      return true;
    }
    let [i, j, possible] = cellInfo;
    while (possible) {
      //截取其中一个可能性
      const sign = -possible & possible;
      //填入空格
      this.fillCell(i, j, sign);
      //继续下一个填充
      if (this.fillNext()) {
        //填充成功
        return true;
      } else {
        //排除当前数字
        possible ^= sign;
        //清空空格
        this.cleanCell(i, j, sign);
      }
    }
    //穷尽所有可能性，回溯
    return false;
  }
  getEmptyCell() {
    let min = 10;
    let cellInfo = null;
    for (const id of this.emptyCells) {
      const i = id >> 4,
        j = id & 0b1111;
      const possible = this.getCellPossible(i, j);
      const count = this.countPossible(possible);
      if (min > count) {
        //挑选可能性最少的格子，理论上可减少犯错回溯
        cellInfo = [i, j, possible];
        min = count;
      }
    }
    return cellInfo;
  }
  countPossible(possible: number) {
    //计算二进制 1 的数量
    let count = 0;
    while (possible) {
      possible &= possible - 1;
      count++;
    }
    return count;
  }
  fillCell(i: number, j: number, sign: number) {
    //对应位变成1，标记占用
    this.rows[i] |= sign;
    this.cols[j] |= sign;
    this.boxs[Math.floor(i / 3)][Math.floor(j / 3)] |= sign;
    //填入空格
    this.emptyCells.delete((i << 4) | j);
    this.board[i][j] = String(Math.log2(sign) + 1);
  }
  cleanCell(i: number, j: number, sign: number) {
    //对应位变为0，清除占用
    this.rows[i] &= ~sign;
    this.cols[j] &= ~sign;
    this.boxs[Math.floor(i / 3)][Math.floor(j / 3)] &= ~sign;
    //清空格子
    this.emptyCells.add((i << 4) | j);
    this.board[i][j] = '.';
  }
  getCellPossible(i: number, j: number) {
    //获取格子可能的取值，二进制1表示可选
    return (
      (this.rows[i] | this.cols[j] | this.boxs[Math.floor(i / 3)][Math.floor(j / 3)]) ^ 0b111111111
    );
  }
}
function solveSudoku(board: string[][]): void {
  new Sudoku(board).solve();
}