Sudoku Solver

Sudoku Solver: 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 digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Input: 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"]]
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"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.
It is guaranteed that the input board has only one solution.

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

class Solution {
  public void solveSudoku(char[][] board) {
      helper(board);
  }

  private boolean helper(char[][] board){
      for(int i = 0; i < board.length; ++i){
        for(int j = 0; j < board.length; ++j){
          if(board[i][j] == '.'){
            for(char k = '1'; k <= '9'; ++k){
              if(isValidSudoku(board, i, j, k)){
                board[i][j] = k;
                if(helper(board)) return true;
                board[i][j] = '.';
              }
            }
            return false;
          }
        }
      }
      return true;
  }

  private boolean isValidSudoku(char[][] board, int row, int column, char value){
      for(int i = 0; i < 9; ++i) if(board[i][column] == value || board[row][i] == value) return false;

      int rowGroup = row / 3, columnGroup = column / 3;
      for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
          if(board[i + rowGroup * 3][j + columnGroup * 3] == value) return false;
        }
      }

      return true;
  }
}

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

function helper(board) {
  for (let i = 0; i < board.length; ++i) {
    for (let j = 0; j < board[i].length; ++j) {
      if (board[i][j] === ".") {
        for (let k = 1; k <= 9; ++k) {
          if (isValidSudoku(board, i, j, String(k))) {
            board[i][j] = String(k);
            if (helper(board)) {
              return true;
            }
            board[i][j] = ".";
          }
        }
        return false;
      }
    }
  }
  return true;
}

function isValidSudoku(board, row, column, value) {
  for (let i = 0; i < 9; ++i) {
    if (board[i][column] === value || board[row][i] === value) {
      return false;
    }
  }

  let rowGroup = Math.floor(row / 3);
  let columnGroup = Math.floor(column / 3);
  for (let i = 0; i < 3; ++i) {
    for (let j = 0; j < 3; ++j) {
      if (board[i + rowGroup * 3][j + columnGroup * 3] === value) {
        return false;
      }
    }
  }

  return true;
}

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.helper(board)

    def helper(self, board: List[List[str]]) -> bool:
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == '.':
                    for k in range(1, 10):
                        if self.isValidSudoku(board, i, j, str(k)):
                            board[i][j] = str(k)
                            if self.helper(board):
                                return True
                            board[i][j] = '.'
                    return False
        return True

    def isValidSudoku(self, board: List[List[str]], row: int, column: int, value: str) -> bool:
        for i in range(9):
            if board[i][column] == value or board[row][i] == value:
                return False

        rowGroup = row // 3
        columnGroup = column // 3
        for i in range(3):
            for j in range(3):
                if board[i + rowGroup * 3][j + columnGroup * 3] == value:
                    return False

        return True

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        helper(board);
    }
private:
    bool helper(vector<vector<char>>& board) {
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; ++k) {
                        if (isValidSudoku(board, i, j, k)) {
                            board[i][j] = k;
                            if (helper(board))
                                return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool isValidSudoku(vector<vector<char>>& board, int row, int column, char value) {
        for (int i = 0; i < 9; ++i)
            if (board[i][column] == value || board[row][i] == value)
                return false;

        int rowGroup = row / 3, columnGroup = column / 3;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i + rowGroup * 3][j + columnGroup * 3] == value)
                    return false;
            }
        }

        return true;
    }
};

Time/Space Complexity:

Time Complexity: O(9^n) where n is number of of empty cells of the initial board
Space Complexity: O(n)

Explanation:

It's a backtracking problem in which we iterate through the board and search for empty cells, when an empty cell is found we try all 9 possibilities for it by first checking if we can place the number in the cell using isValidSudoku. We then check if the board can be solved recursively after we have picked the number for the current cell. If the board can be solved with the current selection we return true, otherwise we backtrack board[i][j] = '.', and if we tried all options and none can be used to reach the final state we return false (that result would be propagated to the main function solveSudoko, at which point we would choose another value for the cell). If there is no other cell to fill, we have arrived at the final solution, so we return true. We implement validation by first checking if the row and column of the current cell, if it already contains the value we have selected. If it does, we return false since we can't choose that value. If the value is not yet presented in the row and column of the board, we check the submatrix 3X3 by first calculating the offset for the group current cell belongs to. If we find the same value in the submatrix, we return false. Otherwise we return true to indicate that the value we selected can be placed in the current cell. There are n cells to fill and for each cell we have 9 options leading to recursion stack of depth n and width 9 making the time complexity O(9^n), while for space complexity we have recursion stack at most n levels deep leading to complexity proportional to the number of empty cells O(n).

Example 1:​

Constraints:​

Solution:​

Time/Space Complexity:​

Explanation:​

Example 1:

Constraints:

Solution:

Time/Space Complexity:

Explanation: