Sudoku Solver – Java

This solution uses DFS (Depth First Search) Algorithm and looks for a unique solution to the given Sudoku Puzzle.

DFS Solution

class Solution {
    public void solveSudoku(char[][] board) {
        if(solve(board, 0, 0)) {
         System.out.println("Solved");   
        }
    }
    
    public boolean solve(char[][] board, int row, int col) {
         if(row>8)
            return true;
        if(col>8)
            return solve(board, row+1, 0);

                if(board[row][col] != '.') {
                    return solve(board, row, col+1);
                } else {
                    for(int k=1; k<=9; k++) {
                        board[row][col] = (char) (k+'0');
                        if(isValid(board, row, col) && solve(board, row, col+1)) {
                          return true;
                        }
                        else
                            board[row][col] = '.';
                    }
        }
        return false;

    }
    
    public boolean isValid(char[][] board, int row, int col) {
        for(int i=0; i<9; i++) {
           if(i!=col && board[row][i] == board[row][col])
               return false;
        }
 
        for(int j=0; j<9; j++) {
            if(j!=row && board[j][col] == board[row][col])
               return false;
        }
               
           
       int x = (row/3)*3;
       int y = (col/3)*3;
       for(int m=x; m<x+3; m++) { 
       for(int n=y; n<y+3; n++) {
           if((m!=row || n!=col) && board[m][n] == board[row][col])
               return false;
           
       }}
        
        return true;
              
    }
}

DFS Solution Optimized

We can get slight runtime optimization by taking a hit on the memory.

class Solution {
    public void solveSudoku(char[][] board) {
        if(solve(board, 0, 0)) {
         System.out.println("Solved");   
        }
    }
    
    public boolean solve(char[][] board, int row, int col) {
         if(row>8)
            return true;
        if(col>8)
            return solve(board, row+1, 0);

                if(board[row][col] != '.') {
                    return solve(board, row, col+1);
                } else {
                    HashSet<Character> set = new HashSet<Character>();
                    buildMaps(board, set, row, col);
                    for(int k=1; k<=9; k++) {
                        board[row][col] = (char) (k+'0');
                        if(!set.contains(board[row][col]) && solve(board, row, col+1)) {
                          return true;
                        }
                        else
                            board[row][col] = '.';
                    }
        }
        return false;

    }
    
    public void buildMaps(char[][] board, HashSet<Character> set, int row, int col) {
        for(int i=0; i<9; i++) {
               set.add(board[row][i]);
        }
        for(int j=0; j<9; j++) {
                set.add(board[j][col]);
        }  
           
       int x = (row/3)*3;
       int y = (col/3)*3;
       for(int m=x; m<x+3; m++) { 
          for(int n=y; n<y+3; n++) {
               set.add(board[m][n]);
           }
       }        
    }    
}

Another alternate solution would be to precompute these values into lists of Hashsets.