37. Sudoku Solver

原题：37. Sudoku Solver

思路：backtrace + 适当剪枝，判断是否合法应用了36. Valid Sudoku的解法

时间复杂度：O(n^3)

source code

// Runtime: 192 ms, faster than 16.58% of JavaScript online submissions for Sudoku Solver.
// Memory Usage: 43.7 MB, less than 14.29% of JavaScript online submissions for Sudoku Solver.
var solveSudoku = function (board) {
  //判断是否合法，可以把这个单独抽离，使得整个程序逻辑更加清晰
  const set = new Set();
  const getKey = function (row, col, num) {
    const rowKey = `row_${row}_${num}`;
    const colKey = `col_${col}_${num}`;
    const boxKey = `box_${~~(row / 3)}_${~~(col / 3)}_${num}`;
    return [rowKey, colKey, boxKey];
  };

  const add = function (row, col, num) {
    const [rowKey, colKey, boxKey] = getKey(row, col, num);
    if (set.has(rowKey) || set.has(colKey) || set.has(boxKey)) {
      return false;
    }

    set.add(rowKey);
    set.add(colKey);
    set.add(boxKey);
    board[row][col] = "" + num;

    return true;
  };

  const remove = function (row, col, num) {
    const [rowKey, colKey, boxKey] = getKey(row, col, num);
    set.delete(rowKey);
    set.delete(colKey);
    set.delete(boxKey);
    board[row][col] = ".";
  };

  //初始化
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === ".") {
        continue;
      }
      add(i, j, board[i][j]); //假设初始面板是合法的
    }
  }

  const helper = function () {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] !== ".") {
          continue;
        }
        for (var num = 1; num <= 9; num++) {
          if (add(i, j, num)) {
            if (helper()) {
              return true;
            } else {
              remove(i, j, num);
            }
          }
        }
        if (num > 9) {
          //如果某一个单元格所有数字都不可行，说明前面走错了
          return false;
        }
      }
    }

    return true;
  };

  helper();
};

test cases

const board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"],
];

solveSudoku(board);
console.log(board);

//output:
[ 
  [ '5', '3', '4', '6', '7', '8', '9', '1', '2' ],
  [ '6', '7', '2', '1', '9', '5', '3', '4', '8' ],
  [ '1', '9', '8', '3', '4', '2', '5', '6', '7' ],
  [ '8', '5', '9', '7', '6', '1', '4', '2', '3' ],
  [ '4', '2', '6', '8', '5', '3', '7', '9', '1' ],
  [ '7', '1', '3', '9', '2', '4', '8', '5', '6' ],
  [ '9', '6', '1', '5', '3', '7', '2', '8', '4' ],
  [ '2', '8', '7', '4', '1', '9', '6', '3', '5' ],
  [ '3', '4', '5', '2', '8', '6', '1', '7', '9' ] 
]