37. Sudoku Solver

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

Empty cells are indicated by the character'.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

思路：回溯

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;
    }

    public boolean isvalid(char[][] board,int i,int j,char c){
        for (int k=0;k<board.length;k++){
            if (board[i][k] == c) return false;
            if (board[k][j] == c) return false;
            if (board[3 * (i / 3) + k / 3][3 * (j / 3) + k % 3] == c) return false;
        }
        return true;
    }

}