37. 解数独

题目：https://leetcode-cn.com/problems/sudoku-solver/

代码：

class Solution {

    /**
     * 空白格
     */
    private static final char BLANK = '.';

    /**
     * 零
     */
    private static final char ZERO = '0';

    public void solveSudoku(char[][] board) {
        this.solve(board, 0, 0);
    }

    /**
     * 从ij位置开始寻找下一个空格的位置，并且尝试填数字
     *
     * @param board
     * @param i
     * @param j
     * @return
     */
    private boolean solve(char[][] board, int i, int j) {
        //保存上一次填写数字的位置
        int oi = i;
        int oj = j;
        //计算下一个需要填写数字的位置
        while (board[i][j] != BLANK) {
            j++;
            if (j >= 9) {
                //从左往右本行已经到头了，换下一行
                i++;
                j = 0;
            }
            if (i >= 9) {
                //已经超过总行数，证明数独已经解答出来了
                return true;
            }
        }
        //尝试填入1-9的数字
        for (int n = 1; n <= 9; n++) {
            if (this.isValid(board, i, j, n)) {
                //有效，继续填下一位
                board[i][j] = (char) (ZERO + n);
                if (this.solve(board, i, j)) {
                    return true;
                }
            }
        }
        //1-9都不是正确解，回滚上一位
        board[oi][oj] = BLANK;
        return false;
    }

    /**
     * 判断填写的数字是否有效
     *
     * @param board
     * @param i
     * @param j
     * @param n
     * @return
     */
    private boolean isValid(char[][] board, int i, int j, int n) {
        char cn = (char) (ZERO + n);
        //通过i和j计算ij所在九宫格第一位的位置
        int fi = i - i % 3;
        int fj = j - j % 3;
        //判断
        for (int k = 0; k < 9; k++) {
            //行
            if (board[i][k] == cn) {
                return false;
            }
            //列
            if (board[k][j] == cn) {
                return false;
            }
            //九宫格
            if (board[fi + k / 3][fj + k % 3] == cn) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印
     *
     * @param board
     */
    public void print(char[][] board) {
        System.out.println(" -----------------------");
        for (int i = 0; i < 9; i++) {
            System.out.print("| ");
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
                if (j % 3 == 2) {
                    System.out.print("| ");
                }
            }
            if (i % 3 == 2) {
                System.out.println("\n -----------------------");
            } else {
                System.out.println();
            }
        }
        System.out.println();
    }

}

为了方便本地调试，上述代码中增加print方法供打印棋盘board，另附赠一个测试用例：

char[][] board = new char[][]{{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

解题思路：跟51. N 皇后有点类似，也是使用递归+回溯的办法解决。

如图箭头所示，从左往右，从上往下的顺序，寻找每一个空格，并在每一个空格所在位置填入1-9的数字，通过isValid方法判断是否有效，如果有效则填入并继续解答下一个空格，否则继续尝试，都无效的情况下，表达这种情况无解，则回退上一次填入的数字即回溯。

完整的过程参考上方代码，可以本地调试并在需要的位置使用print方法打印出来直观理解。