当前位置: 首页 > article >正文

穷举vs暴搜vs深搜vs回溯vs剪枝系列一>解数独

题目: 


解析: 

部分决策树: 

 


代码设计&剪枝&回溯: 

 


代码: 

class Solution {
    private boolean[][] row, col;
    private boolean[][][] gird; 

    public void solveSudoku(char[][] board) {
        //下标->数字;0->1, 1->2
        row = new boolean[9][10];
        col = new boolean[9][10];
        gird = new boolean[3][3][10];

        //初始化上面的标记数组
        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++){
                int num = board[i][j]-'0';
                if(board[i][j] != '.'){
                    row[i][num] = col[j][num] = gird[i/3][j/3][num] = true;
                }
            }

        dfs(board);
    }

    private boolean dfs(char[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                    for(int num = 1; num <= 9; num++){
                        //剪枝写法
                        if(!row[i][num] && !col[j][num] && !gird[i/3][j/3][num]){
                            board[i][j] = (char)('0' + num);
                            row[i][num] = col[j][num] = gird[i/3][j/3][num] = true;

                            //填数字往下遍历时候可能会出现 “某一行无数可以填”
                            if(dfs(board) == true) return true;

                            //回溯
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = gird[i/3][j/3][num] = false;
                        }
                    }
                    //一整行都没有返回时(已经试过9个数),也是出现“某一行无数可以填”
                    return false;
                }
            }
        }

        //上面没有返回代表,前面的dfs已经全部填完
        return true;
    }
}

http://www.kler.cn/a/526758.html

相关文章:

  • UE5.3 C++ CDO的初步理解
  • 步入响应式编程篇(三)之spring webFlux与R2DBC
  • 我的求职面经:(2)C++中空指针请使用nullptr不要使用NULL
  • 【逻辑学导论第15版】A. 推理
  • QT设置应用程序图标
  • C++,STL,【目录篇】
  • 《一文读懂!Q-learning状态-动作值函数的直观理解》
  • win32汇编环境,窗口程序中使用滚动条控件的一般操作
  • AI 模型优化与性能调优
  • 芯片AI深度实战:进阶篇之vim内verilog实时基于AST的自定义检视
  • springboot集成钉钉,发送钉钉日报
  • 【Block总结】高效多尺度注意力EMA,超越SE、CBAM、SA、CA等注意力|即插即用
  • RK3568 opencv播放视频
  • 第23节课:前端调试技巧—掌握浏览器开发者工具与性能优化
  • 理解PLT表和GOT表
  • 新春登蛇山:告别岁月,启航未来
  • LeetCode 0219.存在重复元素 II:哈希表
  • 【Leetcode刷题记录】166. 分数到小数
  • [EAI-022] FuSe,在VLA模型基础上,融合触觉和语音等异构模态信息
  • 动态规划两个数组dp问题系列一>最长公共子序列
  • 网站快速收录:利用RSS订阅提升效率
  • fpga系列 硬件:FPGA VITIS PS端HELLO WORLD在 ZYNQ EBAZ4203板上实现
  • ADC 精度 第二部分:总的未调整误差解析
  • 33333333333
  • Autogen_core 测试代码:test_cancellation.py
  • Electron工具Electron Fiddle