37. Sudoku Solver

这道题和36. Valid Sudoku是配套的，如果理解了那道题目中的数独生成程序，这道题就很简单，程序稍微改改就可以了，核心思路是一样的。

而且这道题限定了给定的数独只有唯一一个正确解，又简化很多。

题外话：据说如果要确定只有唯一正确解，至少要给出17个元素。

我的解法：

public class Solution {
    // 其实leetcode中最好不要用这种成员变量或者static变量，可能引发些奇怪的问题
    // 见https://leetcode.com/faq/#different-output
    // 但是我需要一个全局变量，表示当前是否找到了一个解
    private boolean success = false;

    public void solveSudoku(char[][] board) {
        int[][] rowFlag = new int[10][10];
        int[][] colFlag = new int[10][10];
        int[][] cubeFlag = new int[10][10];
        // 遍历给定的数独，初始化状态
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.')
                    continue;
                int cubeNum = (row / 3) * 3 + col / 3;
                int value = board[row][col] - '0';
                rowFlag[row][value] = 1;
                colFlag[col][value] = 1;
                cubeFlag[cubeNum][value] = 1;
            }
        }
        // 每次计算前都要初始化success变量
        success = false;
        // 找出[0,0]之后需要填的下一个元素
        Point firstCell = findNextCell(board, 0, 0);
        // 如果[0,0]是需要填的，就从[0,0]开始
        if (board[0][0] == '.')
            fillBoard(board, 0, 0, rowFlag, colFlag, cubeFlag);
        // 否则从下一个格子开始
        else if (firstCell != null)
            fillBoard(board, firstCell.x, firstCell.y, rowFlag, colFlag, cubeFlag);
    }

    public void fillBoard(char[][] board, int row, int col, int[][] rowFlag, int[][] colFlag, int[][] cubeFlag) {
        int cubeNum = (row / 3) * 3 + col / 3;
        Point nextCell = findNextCell(board, row, col);
        // 这个格子可能填写1~9，一个个试过去
        for (int i = 1; i <= 9; i++) {
            if (rowFlag[row][i] == 0 && colFlag[col][i] == 0 && cubeFlag[cubeNum][i] == 0) {
                board[row][col] = (char) ('0' + i);
                rowFlag[row][i] = 1;
                colFlag[col][i] = 1;
                cubeFlag[cubeNum][i] = 1;
                // 如果没有下一个格子要填了，说明我们已经找到了正确的解，将success变量置为true
                // 否则就继续填写下一个格子
                if (nextCell == null) {
                    success = true;
                } else
                    fillBoard(board, nextCell.x, nextCell.y, rowFlag, colFlag, cubeFlag);

                // ATTENTION!
                // 注意这里，sucess是个全局变量，如果已经找到了正确的解，所有嵌套的递归都要直接返回，不用再继续尝试了
                if (success)
                    return;

                // 状态rollback，注意同时要把borad的状态还原，不然findNextCell时会出错
                board[row][col] = '.'; // ATTENTION!
                rowFlag[row][i] = 0;
                colFlag[col][i] = 0;
                cubeFlag[cubeNum][i] = 0;
            }
        }
    }

    // 找到下一个需要填写的格子，不包括当前格
    public Point findNextCell(char[][] board, int row, int col) {
        int i = row, j = col;
        while (i < 9 && j < 9) {
            j++;
            if (j >= 9) {
                i++;
                j = 0;
            }
            if (i < 9) {
                if (board[i][j] == '.') {
                    //System.out.println("next cell for (" + row + "," + col + ") is (" + i + "," + j + ")");
                    return new Point(i, j);
                }
            }
        }
        return null;
    }
}
// 一个辅助类
class Point {
    int x;
    int y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }
}

比较容易出错的地方有2个：1.对success变量的处理；2.还原board的状态。

很意外的是这个解法居然能beat 94.3% java submissions，我目前的最好成绩了吧。。。