LeetCode_92_SudokuSolver

1. question: 解数独（困难）

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

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sudoku-solver

示例 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] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解

2. answers

这道题和N皇后非常类似。有四个限制：

1. 只能是[1,9]
2. 同行不能出现重复的
3. 同列不能出现重复的
4. 所在区域不能出现重复的

所以，每次递归的时候，需要提前准备好：

1. 下一个要填充的位置（即遍历，找到那个位置）
2. 下个位置可选择的数字。
   1. 同行不能重复（遍历那一行）
   2. 同列不能重复（遍历那一列）
   3. 同区域不能重复（遍历那个区域）

注意，在递归完回溯的时候，如果下个位置找到了结果（下个位置会无限递归下去，所以最终就是递归到最后一个位置），那么就无需递归了，因为题目保证了之后一个结果。如果没找到，需要还原当前位置为’.’，进行当前位置的下一个选择。代码如下所示：

public class Solution_0092 {

    // 找到下一个位置
    public int[] generateRowAndColumn(char[][] board, int row, int column){

//        System.out.println("当前的位置是：" + row + "===" + column);

        // 计算下一个位置的选择
        // 首先找到下一个要填数字的位置。
        all: for (int j = row; j < 9; j++) {
            for (int k = 0; k < 9; k++) {

                if('.' == board[j][k]) {
                    row = j;
                    column = k;
                    break all;
                }
            }
        }

//        System.out.println("下一为要填充的位置是：" + row + "===" + column);

        return new int[]{row, column};
    }

    // 找到下一个位置所有的选择
    public void getRemain(char[][] board, int row, int column, List<Character> remain) {

        for (int j = 1; j <= 9; j++) {
            remain.add((char) (j + 48));
        }

        // 同行
        for (int j = 0; j < 9; j++) {
            if('.' != board[row][j]) {
                remain.remove((Character)board[row][j]);
            }
        }

        // 同列
        for (int j = 0; j < 9; j++) {
            if('.' != board[j][column]) {
                remain.remove((Character)board[j][column]);
            }
        }

        // 同区域
        int startRow, startColumn;

        if(row >= 6) startRow = 6;
        else if(row >= 3) startRow = 3;
        else startRow = 0;

        if(column >= 6) startColumn = 6;
        else if(column >= 3) startColumn = 3;
        else startColumn = 0;

        for (int j = startRow; j < startRow + 3; j++) {
            for (int k = startColumn; k < startColumn + 3; k++) {
                if('.' != board[j][k]) {
                    remain.remove((Character)board[j][k]);
                }
            }
        }
    }

    // 填充数独
    public void recur(char[][] board, int row, int column, List<Character> remain) {

        // 递归终止
        if(board[row][column] != '.') {
            return;
        }

//        System.out.println(remain.toString());

        for(Character i: remain){
            board[row][column] = i;

            // 计算下一个位置的选择
            // 首先找到下一个要填数字的位置。
            int[] ints = generateRowAndColumn(board, row, column);
            int preRow = ints[0];
            int preColumn = ints[1];

            // 计算其同行、同列、同区域内的数字。更新remainNext
            List<Character> remainNext = new ArrayList<>();
            getRemain(board, preRow, preColumn, remainNext);

            // 递归下一位
            recur(board, preRow, preColumn, remainNext);

            // 如果递归下一位后，能够填上数字，说明找到了最终结果，直接返回，不再回溯。
            if(board[preRow][preColumn] != '.') return;

            // 回溯，即还原初始值即可。
            board[row][column] = '.';
        }
    }

    public void solveSudoku(char[][] board) {

        int row = 0, column = 0;
        int[] ints = generateRowAndColumn(board, row, column);
        row = ints[0];
        column = ints[1];

        // 计算其同行、同列、同区域内的数字。
        List<Character> remainNext = new ArrayList<>();
        getRemain(board, row, column, remainNext);

        recur(board, row, column, remainNext);

    }

    public static void main(String[] args) {
        System.out.println();

        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'}
                        };

        Solution_0092 s = new Solution_0092();

        s.solveSudoku(board);

        for (char[] chars : board) {

            for (int j = 0; j < chars.length; j++) {
                System.out.print(chars[j] + "\t");
            }

            System.out.println();
        }

    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。