37 Sudoku Solver

Leetcode

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.

判断数独是否有效的方法使用 Leetcode 36 题的方法。使用递归，如果一个格子为空，尝试放置 1-9 ，如果可以放置，则继续找下一个空格，尝试同样的操作。如果 1-9 都不行，清空格子，返回 false 到上一级。如果全部格子填满，一层一层返回 true ，跳出递归。

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board, 0, 0); 
    }
    
    private boolean solve(char[][] board, int i, int j){
        if(i==9 && j==0) return true;
        char now = board[i][j];
        if(now=='.'){
            for(char c='1';c<='9';++c){
                board[i][j] = c;
                if(isRowValid(board, i) &&
                    isColValid(board, j) &&
                    isBlockValid(board, i, j)){
                    int ii = j+1==9 ? i+1:i;
                    int jj = j+1==9 ? 0:j+1;

                    if( solve(board, ii, jj) ) return true;
                }    
            }
            board[i][j] = '.';
            return false;
        }
        
        return j+1==9 ? solve(board,i+1,0) : solve(board, i, j+1);
    }
    
    
    
    
    
    private boolean isRowValid(char[][] board, int row){
        boolean[] arr=new boolean[9];
        for(int j=0;j<9;++j){
            char c = board[row][j];
            if(c>='1' && c<='9'){
                int val = c-'1';
                if(arr[val]) return false;
                arr[val] = true;
            }
        }
        return true;
    }
    
    private boolean isColValid(char[][] board, int col){
        boolean[] arr=new boolean[9];
        for(int i=0;i<9;++i){
            char c = board[i][col];
            if(c>='1' && c<='9'){
                int val = c-'1';
                if(arr[val]) return false;
                arr[val] = true;
            }
        }
        return true;
    }
    
    private boolean isBlockValid(char[][] board, int i, int j){
        int row=i/3*3;
        int col=j/3*3;
        boolean[] arr=new boolean[9];
        for(int ii=0;ii<3;ii++){
            for(int jj=0;jj<3;jj++){
                char c=board[row+ii][col+jj];
                if(c>='1' && c<='9'){
                    int val = c-'1';
                    if(arr[val]) return false;
                    arr[val] = true;
                }
            }
        }
        return true;         
    }
}