37. Sudoku Solver

Posted on | Edited on | Views:

LeetCode

BackTracking link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public void solveSudoku(char[][] board) {
        if(board==null||board.length==0) return;
        solve(board);
    }
    public boolean solve(char[][] board) {
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]=='.'){
                    for(char c='1';c<='9';c++){
                        if(isValid(board,i,j,c)){
                            board[i][j]=c;
                            if(solve(board)) return true;
                            else board[i][j]='.';
                        }                        
                    }
                    return false;
                }                
            }
        }
        return true;
    }
    private boolean isValid(char[][] board,int row,int column,char c){
        int blkrow=3*(row/3),blkcol=3*(column/3);
        for(int i=0;i<board.length;i++){
            if(board[row][i]==c 
               || board[i][column]==c 
               || board[blkrow+i/3][blkcol+i%3]==c) return false;
        }
        return true;
    }
}

0%