欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-23 22:11:11
编写一个程序,通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则:数字1-9在每一行只能出现一次。数字1-9在每一列只能出现一次。数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。空白格用'.'表示。一个数独。答案被标成红色。Note:给定的数独序列只包含数字1-9和字符'.'。你可以假设给定的数独只有唯一解。给定数独永远是9x9形式的。来源:力扣(LeetCode)链接:https://leetcode-cn.......


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

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

数字 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

相关标签: LeetCode 算法

推荐阅读