[Leetcode] 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...

DFS题目，记得在遍历之后将状态置会原来的状态否则会影响之后的DFS过程。

public class Solution {

    public void solveSudoku(char[][] board) {
        dfs(board, 0, 0);
    }
    
    private boolean valid(char[][] board, char key, int x, int y) {
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++) {
            if(board[i][y] == key) return false;
        }
        for(int i = 0; i < n; i++) {
            if(board[x][i] == key) return false;
        }
        for(int i = (x/3)*3; i < (x/3+1)*3; i++) {
            for(int j = (y/3)*3; j < (y/3+1)*3; j++) {
                if(board[i][j] == key) return false;
            }
        }
        return true;
    }
    
    private boolean dfs(char[][] board, int x, int y) {
        int m = board.length;
        int n = board[0].length;
        if(x == m) return true;
        if(y == n) return dfs(board, x+1, 0);
        if(board[x][y] != '.') return dfs(board, x, y+1);
        
        for(char i = '1'; i <= '9'; i++) {
            if(valid(board, i, x, y)) {
                board[x][y] = i;
                if(dfs(board, x, y+1)) return true;
                board[x][y] = '.'; // important here, remember to set the status back
            }
        }
        
        return false;
    }

}