题目描述

Note:

给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

题目分析

前面的分析和LeetCode 36的一摸一样，不过是先遍历一遍数独，把已经填好的数字保存在那三个数组中，如果不做36直接上手37还是挺难的。保存完之后就是添加了，再遍历一次获取空的项，填入1-9中的一个数，这个数的前提就是不能重复啦。如果全部填入成功的话，那返回true，如果不行，那就删掉重新再填其他的。

源码

class Solution {
public void solveSudoku(char[][] board) {
    boolean[][] row = new boolean[9][10];
    boolean[][] col = new boolean[9][10];
    boolean[][] block = new boolean[9][10];

    for (int i=0;i<9;i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '0';
                row[i][num] = true;
                col[j][num] = true;
                block[i / 3 * 3 + j / 3][num] = true;
            }
        }
    }
    dfs(board, row, col, block, 0, 0);
}

private boolean dfs(char[][] board, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j) {
    while (board[i][j] != '.') {
        if (++j >= 9) {
            i++;
            j = 0;
        }
        if (i >= 9) {
            return true;
        }
    }
    for (int num = 1; num <= 9; num++) {
        int blockIndex = i / 3 * 3 + j / 3;
        if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) {
            board[i][j] = (char) ('0' + num);
            row[i][num] = true;
            col[j][num] = true;
            block[blockIndex][num] = true;
            if (dfs(board, row, col, block, i, j)) {
                return true;
            } else {
                row[i][num] = false;
                col[j][num] = false;
                block[blockIndex][num] = false;
                board[i][j] = '.';
            }
        }
    }
    return false;
}

}

难点

对于我来说，难点主要是一个。就是如何去填数进去保证填完之后这个数独一定就是成立的。我第一次填进去，填这一行看看能不能组成，不行的话我就必须要回去把那个数删了再填其他的数试试。也就是说我在以这个位置为一个三角形的顶端，往下去试，不成功就换个顶继续试，直到成功为止，这个思想就是很典型的回溯了。

小结

做数独题时，最好做的就是分别保存行列九宫格三个数组，当三个都成立时，那么这个数独也就成立了。填数据一次就填对的几率太小太小了，那么就需要不断试，这时候就要想到组合问题，那么回溯就是一个很经典的办法。

[1]https://leetcode-cn.com/problems/sudoku-solver/