Acwing166 数独题解 - DFS剪枝优化

这篇具有很好参考价值的文章主要介绍了Acwing166 数独题解 - DFS剪枝优化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

166. 数独 - AcWing题库

题意

数独 是一种传统益智游戏,你需要把一个 9×9 的数独补充完整,使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。

请编写一个程序填写数独。

思路

搜索+剪枝(优化搜索顺序、位运算)文章来源地址https://www.toymoban.com/news/detail-838205.html

  • 优化搜索顺序:很明显,我们肯定是从当前能填合法数字最少的位置开始填数字
  • 位运算:很明显这里面check判定很多,我们必须优化这个check,所以我们可以对于,每一行,每一列,每一个九宫格,都利用一个九位二进制数保存,当前还有哪些数字可以填写.
  • lowbit:我们这道题目当前得需要用lowbit运算取出当前可以能填的数字.

code + 详细注释

#include <iostream>

#define lowbit(x) (x & -x) // lowbit操作
#define get(x, y) (row[x] & col[y] & cell[x / 3][y / 3]) // get(x, y) 找到该位置可以填哪些数的状态

using namespace std;

const int N = 9, M = 1 << N;

int one[M], map[M]; // one[state]为该state中有几个1, map[state]为state对应的十进制值
int col[N], row[N], cell[3][3];
char str[100];

void init() { // 初始化(将所有位置都初始化可以填数的状态)
    for (int i = 0; i < N; ++ i) row[i] = col[i] = (1 << N) - 1; 
    // 将行和列都用二进制来优化(刚开始的位置都为1)

    for (int i = 0; i < 3; ++ i)
        for (int j = 0; j < 3; ++ j)
            cell[i][j] = (1 << N) - 1; // 每个3 * 3的小方格也用二进制来优化(刚开始也都为1)
}

void draw(int x, int y, int t, bool is_set) { // 在(x, y)的位置上(is_set)<是/否>填t的操作 
    if (is_set) str[x * N + y] = '1' + t; // 如果填数的话, 将该数转换为字符形式填入字符串中对应的位置
    else str[x * N + y] = '.'; // 否则说明字符串该位置上填的是'.';

    int v = 1 << t; // 找到该数对应二进制之后的位置的数
    if (!is_set) v = -v; // 如果该位置不填数,则将该数取负

    row[x] -= v; //在这个原数对应的行减去该数的二进制数
    col[y] -= v; // 在这个原数对应的列减去该数的二进制数
    cell[x / 3][y / 3] -= v; // 在这个原数对应的小方格减去该数的二进制数
}

bool dfs(int cnt) {
    if (!cnt) return true; // 知道没有位置能填数就结束搜索

    int minv = 10; // 记录当前最少枚举方案
    int x, y; // x, y记录枚举方案最少的位置的x, y

    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
            if (str[i * N + j] == '.') { // 该位置对应的字符串位置上为'.', 才说明能填数
                int state = get(i, j); // 找到该位置上能填的数的状态
                if(one[state] < minv) { // 只有当当前位置的方案少于当前最少方案才有搜索的必要
                    x = i, y = j;
                    minv = one[state];
                }
            }

    int state = get(x, y); // 找到最少枚举方案对应的位置的能填的数的状态
    for (int i = state; i; i -= lowbit(i)) { // 枚举该位置上能填的数,用lowbit操作
        int t = map[lowbit(i)]; // 找到该位置上能填的数
        draw(x, y, t, true); // 填数
        if (dfs(cnt - 1)) return true; // 继续搜索
        draw(x, y, t, false); // 恢复
    }

    return false;
}

int main() {
    for (int i = 0; i < N; ++ i) map[1 << i] = i; // 预处理map[]

    for (int i = 0; i < 1 << N; ++ i)
        for (int j = 0; j < N; ++ j)
            one[i] += (i >> j & 1); // 预处理one[]

    while (cin >> str, str[0] != 'e') { // 多组输入
        init(); // 初始化

        int cnt = 0; // 记录有几个空格需要填数
        for (int i = 0, k = 0; i < N; ++ i) 
            for(int j = 0; j < N; ++ j, ++ k) {
                if (str[k] != '.') { // 如果该位置已经有数了
                    int t = str[k] - '1'; // 找到该位置上的数
                    draw(i, j, t, true); // 在该位置上填上该数
                }
                else cnt ++ ; // 否则说明该位置需要填数
            }

        dfs(cnt); // 开始搜索

        puts(str); // 输出答案
    }

    return 0; // 结束快乐~
}

作者:Hustle
链接:https://www.acwing.com/solution/content/57159/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

到了这里,关于Acwing166 数独题解 - DFS剪枝优化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)

    目录 写在前面: 题目:92. 递归实现指数型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 距离蓝桥杯已经不足一个月了, 根据江湖上的传言, 蓝桥杯最喜欢考的是深度优先搜索和

    2024年02月03日
    浏览(54)
  • 【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs(8)

    目录 写在前面: 题目:1114. 棋盘问题 - AcWing题库 题目描述: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要, 所以,为了学好深度优先搜

    2023年04月09日
    浏览(38)
  • AcWing 24:机器人的运动范围 ← BFS、DFS

    【题目来源】 https://www.acwing.com/problem/content/description/22/ 【题目描述】 地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−1 和 0∼n−1。 一个机器人从坐标 (0,0) 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。 但是不能进入行坐标和列坐标的数位之

    2024年02月14日
    浏览(32)
  • 【Acwing1010】拦截导弹(LIS+贪心)题解

    1.最长上升子序列(lis)的算法思想和算法模板 2.简单了解贪心算法的思想 本题有两问,第一问直接用lis的模板即可,下面重点看第二问 思路是贪心: 贪心流程: 从前往后扫描每一个数,对于每个数: 情况一:如果现有的子序列的结尾都小于当前的数,则创建子序列 情况

    2024年02月07日
    浏览(25)
  • 【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

    【DFS专题】优质题单推荐 10道题(C++ | 洛谷 | acwing) 来自b站大佬的题单 题单链接 每个位置选什么数 与全排列的差别就是第二个for循环开始的位置,换句话说就是每个数该放什么位置。 参数 : 前u个数 选 or 不选 的 需要保存第x位置的状态的时候就需要用st数组来存状态 i

    2023年04月08日
    浏览(46)
  • 【搜索】DFS剪枝与优化

    算法提高课笔记 剪枝 是什么意思呢? 我们知道,不管是内部搜索还是外部搜索,都可以形成一棵搜索树,如果将搜索树全部遍历一遍,效率会很低,但如果我们能在搜索的过程中,提前预知,判断某一些不可能是正确答案的情况,就可以不用遍历其下的子树,从而提高我们

    2024年02月14日
    浏览(55)
  • 【算法心得】正确估计dfs时间复杂度;剪枝优化不怕重构

    https://leetcode.cn/problems/verbal-arithmetic-puzzle/ 这题看到题,“表达式中使用的不同字符数最大为 10”,就觉得dfs就完事了,最多不过10!,10!才1e6,1e7这样。如果字符再少点,6! 7! 8!的,那简直就是嗖的一下就跑完了 结果TLE了 比方说,有7个字符,不是想象中的 7!,而是 10*9*...*4 ,

    2024年02月12日
    浏览(43)
  • 【第二十五课】动态规划:完全背包问题(acwing-3 / 公式推导 / 思路理解 / 优化 / c++代码)

    目录 思路 朴素代码 优化 公式推导上  二维代码  一维代码 公式理解上   在开始看完全背包问题之前,可能需要先了解01背包及其解决办法。 指路👇 【第二十五课】动态规划:01背包问题(acwing-2 / 思路 / 含一维数组优化 / c++代码) 这个问题和01背包的区别就是 每件物品可以

    2024年03月19日
    浏览(62)
  • 【算法 | 模拟No.4】AcWing 756. 蛇形矩阵 & AcWing 40. 顺时针打印矩阵

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年01月16日
    浏览(54)
  • ACWing算法基础课

    y总说 java不能用Scanner读入,要用Buffer.read();快十倍二十倍; y总19年5月的视频,牛13! 包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容。 一定要先移动end(就是把大数移到右边),后移动start; 否则 先找小数,会出现end start重合位置

    2024年02月13日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包