Sudoku Solver

Examples:

Input: [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,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 program fills in the empty cells with numbers from 1 to 9 such that each row, column, and 3x3 sub-grid contains each number exactly once.

Solutions

Backtracking

Time: O(9^(n*n))Space: O(n*n)

The backtracking approach is used to solve the Sudoku puzzle. The program tries to fill in the empty cells with numbers from 1 to 9. If a number is valid (i.e., it does not appear in the same row, column, or 3x3 sub-grid), the program recursively tries to fill in the rest of the puzzle. If it is not possible to fill in the rest of the puzzle, the program backtracks and tries a different number.


public
class SudokuSolver {
  
  
  public void solveSudoku(char[][] board) {
    
    solve(board);
    
  }
  
  
  private boolean solve(char[][] board) {
    
    for (int i = 0;
    i < 9;
    i++) {
      
      for (int j = 0;
      j < 9;
      j++) {
        
        if (board[i][j] == '\u0000') {
          
          for (int num = 1;
          num <= 9;
          num++) {
            
            if (isValid(board, i, j, (char) (num + '0'))) {
              
              board[i][j] = (char) (num + '0');
              
              if (solve(board)) return true;
              
              board[i][j] = '\u0000';
              
            }
            
          }
          
          return false;
          
        }
        
      }
      
    }
    
    return true;
    
  }
  
  
  private boolean isValid(char[][] board, int row, int col, char num) {
    
    for (int i = 0;
    i < 9;
    i++) {
      
      if (board[row][i] == num) return false;
      
    }
    
    for (int i = 0;
    i < 9;
    i++) {
      
      if (board[i][col] == num) return false;
      
    }
    
    int startRow = row - row % 3;
    
    int startCol = col - col % 3;
    
    for (int i = 0;
    i < 3;
    i++) {
      
      for (int j = 0;
      j < 3;
      j++) {
        
        if (board[i + startRow][j + startCol] == num) return false;
        
      }
      
    }
    
    return true;
    
  }
  
}

Constraints:

Examples:

Solutions

Backtracking

Follow-up: