Sudoku Solver (Java Solution)

a Question on Pramp platform

In this question, we are going to write a function called sudokuSolve, which is going to return whether the sudoku board is solvable or not. If it is solvable, the function should return true. Otherwise, return false.

class Solution {
   static boolean sudokuSolve(char[][] board) {
   }
}

We all know the rules of playing sudoku. All the numbers from 1 to 9 should be contained in each row, each column and also in each 3 times 3 square. If we find out that there’s a duplicate in one of these three conditions, we know that the sudoku board is unsolvable then the function should return false.

In the two for loop below we are iterating the whole board one by one, if we find there is a space (in the sudoku board we represent it as “.” ), we will called the possibleCandidates function so that we could have the possible characters that can be filled in this space. After iterating each row and column, we get the shortest list of characters that can be filled in that space. Then, we backtrack the whole list of characters. If we find out all the spaces are filled then we return true. Otherwise, it means that the tried character in the list does not work so we restore it back to ‘.’ again.

class Solution {
 static boolean sudokuSolve(char[][] board) {
    // your code goes here
    int r = -1, c = -1;
    List<Character> candidates = null;
    List<Character> newCandidates = new LinkedList<>();
    for(int row = 0; row < 9; row++){
      for(int col = 0; col < 9; col++){
          if(board[row][col] == '.'){ 
              newCandidates = possibleCandidates(board, row, col);
              if(candidates == null || newCandidates.size() < candidates.size()){
                candidates = newCandidates;
                r = row;
                c = col;
             }
           }
        }
     }
    if(candidates == null) return true;
    for(char val: candidates){
      board[r][c] = val;
      if(sudokuSolve(board)) return true;
      board[r][c] = '.';
    } 
    return false;
  }

In the possibleCandidates function we tried out each numbers from 1 to 9, if we find out that there is one duplicate in its row or column or 3x3 sub-board, we will set the collision to false, which means that this number will not be the possible candidate to put in that place.

static List<Character> possibleCandidates(char[][] board, int row, int col){
    List<Character> candidates = new LinkedList<>();
    boolean collision = false;
    for(char c = '1'; c <= '9'; c++){
      collision = false;
      for(int i = 0; i < 9; i++){
          if(board[i][col] == c || board[row][i] == c || board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == c){
            collision = true;
            break;
          }
      }
      if(collision == false) candidates.add(c);
    }
    return candidates;
  }