37. 解数独-蒲公英云

37. 解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1：

在这里插入图片描述

输入：board = [[“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”]]
输出：[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

在这里插入图片描述

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据保证输入数独仅有一个解

思路：(回溯)

由于题目有三个条件，所以应该存储每个条件的数字使用情况；
遍历数字，只有在三个条件中都未使用的时，将该数暂存到该位置：
- 如果在以上数字条件下，下面的位置都能找到合适的数字，则成立；
- 如果在上述数字条件下，下面的位置遍历1-9，都不能找到合适的数字，则返回false，回溯上一步结果，上一步继续往后遍历，直到9，如果找不到继续回溯；

本题关键：
将 backtracking 函数的返回类型设为 boolean 类型，如果下一次迭代返回结果为 true，则填入数字正确，否则才数字不正确，回溯，继续遍历剩余数字：

bod[r][c] = (char)(num + '0');
rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = true;
if(backtracking(nr , nc)) {
    return true;
}else {//不成立回溯
    bod[r][c] = '.';
    rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = false;
    continue;
}

代码：(Java)

public class sudoku {
    public static void main(String[] args) {
        //TODO Auto-generated method stub
        char [][] board = {
                {
    '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'}
        };
        solveSudoku(board);
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                System.out.print(board[i][j]+ " ");
            }
            System.out.println();
        }
    }
    private static boolean[][] rowsUsed = new boolean[9][10];
    private static boolean[][] colsUsed = new boolean[9][10];
    private static boolean[][] cubesUsed = new boolean[9][10];
    private static char[][] bod;
    public static void solveSudoku(char[][] board) {
        bod = board;
        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                if(bod[r][c] != '.') {
                    int num =  Character.getNumericValue(bod[r][c]);
                    rowsUsed[r][num] = true;
                    colsUsed[c][num] = true;
                    cubesUsed[cubeNum(r, c)][num] = true;
                }
            }
        }
        backtracking(0, 0);
    }
    private static boolean backtracking(int r, int c) {
        // TODO Auto-generated method stub
        if(r == 9) {
            return true;
        }
        int nr, nc;
        if(c == 8) {
            nr = r + 1;
            nc = 0;
        }else {
            nr = r;
            nc = c + 1;
        }
        if(bod[r][c] != '.') {
            return backtracking(nr , nc);
        }
        for(int num = 1; num <= 9; num++) {
            if(rowsUsed[r][num] || colsUsed[c][num] || cubesUsed[cubeNum(r, c)][num]) {
                continue;
            }
            bod[r][c] = (char)(num + '0');
            rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = true;
            if(backtracking(nr , nc)) {
    //判断条件为递归结果
                return true;
            }else {
    //不成立回溯
                bod[r][c] = '.';
                rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = false;
                continue;
            }
        }
        return false;    
    }
    private static int cubeNum(int i, int j) {
    //返回第几个方块
        // TODO Auto-generated method stub
        int r = i / 3;
        int c = j / 3;
        return r * 3 + c;
    }
}