解数独在二维数组中的逐步回溯_Java

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    //算法思想：
    /*
        每个空位置可以选择1-9中的每一个数，不过过需要满足三个条件
        1、一行中不能存在一样的
        2、一列中不能存在一样的
        3、3*3的区域中不能存在一样的
        只要满足这三个条件，那么剩下的工作就是一个空位接着一个空位去搜索即可
    */
    boolean flag = false;
    char[][] res = new char[9][9];//保存最终结果
    public static void solveSudoku(char[][] board) {
        dfs(board, 0, 0);
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                board[i][j] = res[i][j];
            }
        }
    }
    static void dfs(char[][] board, int a, int b){
        if(flag)return;//剪枝
        if(a == 9){
            flag = true;
            for(int i = 0; i < 9; ++i){
                for(int j = 0; j < 9; ++j){
                    res[i][j] = board[i][j];
                }
            }
            return;
        }
        if(a < 9 && b < 9){
            if(board[a][b] == '.'){//查找本行中的空位置
                for(int k = 1; k <= 9; ++k){//空位置的1-9的选择
                    boolean use = false;
                    for(int q = 0; q < 9; ++q){//扫描所在行和列，验证可行性
                        if((char)(k + 48) == board[a][q] || (char)(k + 48) == board[q][b]){//存在相同数字则换下一个
                            use = true;
                            break;
                        }
                    }
                    //扫描所在3*3块，验证可行性
                    //根据空位置所在的行列找到所在块
                    if(use || isExist(board, a, b, (char)(k + 48)))continue;
                    board[a][b] = (char)(k + 48);
                    dfs(board, a, b + 1);//测试下一个位置
                    if(flag)return;//防止修改board，在这里我们就不需要res数组来保存board了
                    board[a][b] = '.';
                    //if(flag)return;//在这里需要，因为回溯返回过程把board给修改回去了
                }
            }else{
                dfs(board, a, b + 1);//测试下一个位置
            }
        }
        if(a < 9 && b == 9){
            dfs(board, a + 1, 0);//测试下一行位置，并设置到头部
        }
        return;
    }

    static boolean isExist(char[][] board, int n, int s, char ch){
        int a, b, c, d;
        switch(n){
            case 0:
            case 1:
            case 2:
                a = 0;b = 3;
                break;
            case 3:
            case 4:
            case 5:
                a = 3; b = 6;
                break;
            default:
                a = 6; b = 9;
        }
        switch(s){
            case 0:
            case 1:
            case 2:
                c = 0; d = 3;
                break;
            case 3:
            case 4:
            case 5:
                c = 3; d = 6;
                break;
            default:
                c = 6; d = 9;
        }
        for(int i = a; i < b; ++i){
            for(int j = c; j < d; ++j){
                if(board[i][j] == ch){
                    return true;
                }
            }
        }
        return false;
    }

    // public static void main(String[] args) {
    //     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);
    // }
}

使用数组加快查找，直接定位位置，后面的[9]是1-9是否在行列以及块中出现

class Solution {
    boolean[][] rows = new boolean[9][9];//存储行中的1-9
    boolean[][] lines = new boolean[9][9];//存储列中的1-9
    boolean[][][] flag = new boolean[3][3][9];//存储3*3方块中的1-9
    public void solveSudoku(char[][] board) {
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                if(board[i][j] != '.'){
                    int v = board[i][j] - '1';
                    rows[i][v] = lines[j][v] = flag[i/3][j/3][v] = true;
                }
            }
        }
        System.out.print(dfs(board, 0, 0));
    }

    boolean dfs(char[][] board, int x, int y){
        if(y == 9){
            x++;
            y = 0;
        }
        if(x == 9){
            return true;
        }
        
        if(board[x][y] != '.')return dfs(board, x, y + 1);
        for(int i = 0; i < 9; ++i){
            if(board[x][y] == '.' && !rows[x][i] && !lines[y][i] && !flag[x/3][y/3][i]){
                board[x][y] = (char)(i + 49);
                rows[x][i] = lines[y][i] = flag[x/3][y/3][i] = true;
                if(dfs(board, x, y + 1))return true;//防止修改board
                rows[x][i] = lines[y][i] = flag[x/3][y/3][i] = false;
                board[x][y] = '.';
            }
        }
        return false;
    }
}

本文地址：https://blog.csdn.net/StrawberryMuMu/article/details/107692180