博客

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。

空白格用 ‘.’ 表示。

思路：同样是采用回溯法，用三个数组，分别保存每一次填完数字之后，所在行，列，小方块的记录。并且数组长度都为 int[9][10]，设置这种长度的原因是因为：行列小方块都各有9个，长度为10是为了对应数字1-9的下标，不要0，因此长度设为10。

回溯函数的参数是row 和 col 。这样每次在回溯前都要移动row 和 col，找到数独表中要填数字的位置（这一块代码很精髓）。

同时有一个细节要注意，每次我们在写回溯函数的时候，一般都是void返回类型，但是在这里是boolean返回类型，因为数独我们就只要找到一个解就行了，就是一直往下递归，直到终点，然后返回true即可；而在有的回溯函数中我们要找到多个解，因此在我们找到一个解之后，保存完，仍然需要回溯到之前的位置，去寻找下一个解。

详情见代码吧。

class Solution {

    char board[][];
    boolean[][] rowsUsed = new boolean[9][10];
    boolean[][] colsUsed = new boolean[9][10];
    boolean[][] cubeUsed = new boolean[9][10];

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int index = board[i][j] - '0';
                    rowsUsed[i][index] = true;
                    colsUsed[j][index] = true;
                    cubeUsed[cubeCount(i, j)][index] = true;
                }
            }
        }
        backTracking(0, 0);
    }

    public boolean backTracking(int row, int col) {
        while (row < 9 && board[row][col] != '.') {
            row = col == 8 ? row + 1 : row;
            col = col == 8 ? 0 : col + 1;
        }
        if (row == 9) {
            return true;
        }
        for (int num = 1; num <= 9; num++) {
            if (rowsUsed[row][num] || colsUsed[col][num] || cubeUsed[cubeCount(row, col)][num]) {
                continue;
            }
            board[row][col] = (char) (num + '0');
            rowsUsed[row][num] = colsUsed[col][num] = cubeUsed[cubeCount(row, col)][num] = true;
            if (backTracking(row, col)) {
                return true;
            }
            rowsUsed[row][num] = colsUsed[col][num] = cubeUsed[cubeCount(row, col)][num] = false;
            board[row][col] = '.';
        }
        return false;
    }

    public int cubeCount(int row, int col) {
        int r = row / 3;
        int c = col / 3;
        return r * 3 + c;
    }
}