博客

1.题目描述：

编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：数字1-9在每一行只能出现一次；数字1-9在每一列只能出现一次；数字1-9在每一个以粗实线分隔的3×3宫内只能出现一次；数独部分空格内已填入了数字，空白格用’.’表示。

2.回溯：

双层for循环首先找到空的位置，再一个for循环开始1-9数字的递归回溯。因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用返回值。

class Solution {
    public void solveSudoku(char[][] board) {
        backTracking(board);
    }

    public boolean backTracking(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') continue;
                for (char k = '1'; k <= '9'; k++){
                    if (isVaild(board, i, j, k)){
                        board[i][j] = k;
                        if (backTracking(board) == true) return true;
                        board[i][j] = '.';
                    }
                }
                return false;//棋盘某一位置1-9全试过但都不行，该次棋盘的填充非数独的解，return false开始回溯
            }
        }
        return true;//遍历到这里说明该次棋盘的填充前面一直没有返回false，那么返回true
    }

    public boolean isVaild(char[][] board, int row, int col, char value) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == value) return false;
        }
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == value) return false;
        } 
        int r = row / 3 * 3;
        int c = col / 3 * 3;
        for (int i = r; i < r + 3; i++) {//这里可以少去判断同行同列已经判断的位置
            for (int j = c; j < c + 3; j++) {
                if (board[i][j] ==  value) return false;
            }
        }
        return true;
    }
}

二刷：关键在于回溯需要boolean返回值！

class Solution {
    public void solveSudoku(char[][] board) {
        backTracking(board);
    }
    public boolean backTracking(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') continue;
                for (int k = 0; k < 9; k++) {
                    if (helper((char)(k + '1'), i , j, board)) {
                        board[i][j] = (char)(k + 1 + '0');
                        if(backTracking(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    public boolean helper(char value, int row, int column, char[][] board) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == value) return false;
        }
        for (int i = 0; i < 9; i++) {
            if (board[i][column] == value) return false;
        }
        for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
            for (int j = column / 3 * 3; j < column / 3 * 3 + 3; j++) {
                if (board[i][j] == value) return false;
            }
        }
        return true;
    } 
}