HackerHeap

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. 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 1:

class Solution {
    public void solveSudoku(char[][] board) {
        helper(board);
    }
    
    public boolean helper(char[][] board){
        for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    if(board[i][j]!='.'){
                        continue;
                    }
                    for(char k='1';k<='9';k++){
                        if(isValid(board, i, j, k)){
                            board[i][j] = k;
                           if (helper(board)){
                               return true;
                           }
                            board[i][j] = '.';
                        }
                        
                    }
                    return false;
                }
        }
        return true;
    }
    
    
    public boolean isValid(char[][] board, int row, int column, char k){
            for(int i=0;i<9;i++){
                if(board[row][i]!='.' && board[row][i]==k) return false;
                
                if(board[i][column]!='.' && board[i][column]==k) return false;
                
                if(board[3 * (row / 3) + i / 3][3 * (column / 3) + i % 3]!='.' && board[3 * (row / 3) + i / 3][3 * (column / 3) + i % 3]== k) return false;
            }
        
        return true;
            
    }
}