37. Sudoku Solver

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

• Each of the digits 1-9 must occur exactly once in each row.
• Each of the digits 1-9 must occur exactly once in each column.
• Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

Solution

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  solve(board);
};

var solve = function (board) {
  for (var i = 0; i < 9; i++) {
    for (var j = 0; j < 9; j++) {
      if (board[i][j] !== '.') continue;
      for (var k = 1; k <= 9; k++) {
        if (isValid(board, i, j, '' + k)) {
            board[i][j] = '' + k;
          if (solve(board)) {
            return true;
          } else {
            board[i][j] = '.';
          }
        }
      }
      return false;
    }
  }
  return true;
};

var isValid = function (board, i, j, num) {
  for (var k = 0; k < 9; k++) {
    if (board[i][k] === num) return false;
    if (board[k][j] === num) return false;
    if (board[Math.floor(i / 3) * 3 + Math.floor(k / 3)][Math.floor(j / 3) * 3 + (k % 3)] === num) return false;
  }
  return true;
};

Explain:

dfs：

遍历每个点，尝试填入 1~9 的数字，判断是否可以，不行就回滚，直到可以。

Complexity:

• Time complexity : O(9^n). n 为格子数。
• Space complexity : O(1).