LeetCode 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.

 

Solution:

用回溯和递归实现。

public void solveSudoku(char[][] board) {
    dfsSolve(board);
}

private boolean dfsSolve(char[][] board) {
    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            if(board[i][j] == '.') {
                for(int k=1; k<=9; k++) {
                    board[i][j] = (char)(k+'0');
                    if(isValidSudoku(board, i, j) && dfsSolve(board)) {
                        return true;
                    }
                }
                board[i][j] = '.';
                return false;
            }
        }
    }
    return true; // 一定要返回true，递归的终止条件。当全部空cell都被填充的时候会走到这一步。
}

private boolean isValidSudoku(char[][] board, int x, int y) {
    char val = board[x][y];
    board[x][y] = 'A'; //任意一个非1-9的字符都可以
    for(int i=0; i<9; i++) {
        if(board[i][y] == val) return false;
    }
    for(int j=0; j<9; j++) {
        if(board[x][j] == val) return false;
    }
    for(int i=x/3*3; i<x/3*3+3; i++) {
        for(int j=y/3*3; j<y/3*3+3; j++) {
            if(board[i][j] == val) return false;
        }
    }
    board[x][y] = val;
    return true;
}

 

Python的代码更简洁一点：

def solveSudoku(self, board):
    def isValid(x,y):
        tmp=board[x][y]; board[x][y]='D'
        for i in range(9):
            if board[i][y]==tmp: return False
        for i in range(9):
            if board[x][i]==tmp: return False
        for i in range(3):
            for j in range(3):
                if board[(x/3)*3+i][(y/3)*3+j]==tmp: return False
        board[x][y]=tmp
        return True
    def dfs(board):
        for i in range(9):
            for j in range(9):
                if board[i][j]=='.':
                    for k in '123456789':
                        board[i][j]=k
                        if isValid(i,j) and dfs(board):
                            return True
                        board[i][j]='.'
                    return False
        return True
    dfs(board)