Sudoku Solver(Hard)数独游戏

Leetcode Source

数独是一款近年来十分流行的逻辑谜题游戏，它规则简单并且无需任何其他技巧。通过应用纯粹的逻辑推理并且不需数学计算，这类让人上瘾的谜题给各个年龄段和不同水平的玩家提供了无穷无尽的娱乐享受以及智力挑战。

标准数独是由一个给与了提示数字的9x9网格组成，我们只需将其空格填上数字，使得每一行，每一列以及每一个3x3子宫格都没有重复的数字出现。

主体还是一个递归函数，找出当前适合的数后再递归调用。找出合适的数的方法就是遍历9个数字填充到当前位置，然后用验证函数进行验证，然后验证通过就继续调用递归函数解出下一个位置，如果验证不通过就再尝试下一个数字。如果遍历了一遍都没有发现合适的数字，那么就返回false。当发现所有空位都填充满了之后，就可以返回true了。

 public void solveSudoku(char[][] board) {
    if (board == null || board.length != 9 || board[0].length != 9)
        return;

    solve(board, 0, 0);
}

private boolean solve(char[][] board, int i, int j) {
    if (j >= 9)
        return solve(board, i + 1, 0);
    if (i == 9)
        return true;

    if (board[i][j] == '.') {
        for (int k = 1; k <= 9; k++) {
            board[i][j] = (char) (k + '0');
            if (isValid(board, i, j)) {
                if (solve(board, i, j + 1))
                    return true;
            }
            board[i][j] = '.';
        }
    } else {
        return solve(board, i, j + 1);
    }

    return false;
}

private boolean isValid(char[][] board, int i, int j) {
    //每一行没有重复的数字出现
    for (int k = 0; k < 9; k++) {
        if (k != i && board[k][j] == board[i][j])
            return false;
    }

    //每一列没有重复的数字出现
    for (int k = 0; k < 9; k++) {
        if (k != j && board[i][k] == board[i][j])
            return false;
    }

    //每一个3x3子宫格没有重复的数字出现
    for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++) {
        for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++) {
            if (row != i && col != j && board[i][j] == board[row][col])
                return false;
        }
    }
    return true;
}