利用计算机程序快速得到9*9大小数独的解法

利用计算机程序快速得到9*9大小数独的解法对于9∗99*99∗9大小的数独游戏,我们可以使用回溯法求得其正确的解,但是,一般的回溯法实现这个过程保证不了时间复杂度,所以我们可以利用二进制压缩的方法来优化其过程。具体思路如下:明确数独的约束:相同一行不能出现重复的数相同一列不能出现重复的数同一宫内不能出现重复的数定义row[i]row[i]row[i]数组代表,第i,ji,ji,j位置,在iii行哪些数被占用,用二进制111表示没有被占用,000表示被占用那么最开始row[i]row[i]row[i]=111111

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

对于 9 ∗ 9 9*9 99 大小的数独游戏,我们可以使用回溯法求得其正确的解,但是,一般的回溯法实现这个过程保证不了时间复杂度,所以我们可以利用二进制压缩的方法来优化其过程。

具体思路如下:

明确数独的约束:

  • 相同一行不能出现重复的数
  • 相同一列不能出现重复的数
  • 同一宫内不能出现重复的数

定义 r o w [ i ] row[i] row[i]数组代表,第 i , j i,j i,j位置,在 i i i 行哪些数被占用,用二进制 1 1 1 表示没有被占用, 0 0 0 表示被占用那么最开始 r o w [ i ] row[i] row[i] = 111111111 111111111 111111111,表示行没有数被占用。

定义 c o l [ j ] col[j] col[j]数组代表,第 i , j i,j i,j位置,第 j j j 列哪些数被占用,用二进制 1 1 1 表示没有被占用, 0 0 0 表示被占用,那么最开始 c o l [ i ] col[i] col[i] = 111111111 111111111 111111111,表示列没有数被占用。

定义 c e l l [ i / 3 ] [ j / 3 ] cell[i/3][j/3] cell[i/3][j/3]数组代表,第 i , j i,j i,j 格所在的宫中那些数被占用,用二进制 1 1 1 表示没有被占用, 0 0 0 表示被占用,那么最开始 c e l l [ i / 3 ] [ j / 3 ] cell[i/3][j/3] cell[i/3][j/3] = 111111111 111111111 111111111,表示宫中没有数被占用。

然后我们需要初始化上面三个数组,因为一开始的数独游戏位置被一些数占用了,那么这些数的位置就会影响 r o w [ i ] , c o l [ j ] , c e l l [ i ] [ j ] row[i],col[j],cell[i][j] row[i],col[j],cell[i][j]的二进制数,我们需要把相应的数,在二进制数的响应位改变成0,表示这个数在此列或行或宫被占用了。

然后我们利用位运算&对三个数组进行&,就可以得到三个数组都没有被占用的数,然后从其中挑选数,进行回溯法即可得到数独的解。

注意要熟悉: l o w b i t ( ) lowbit() lowbit()的用法,是取二进制数第一次出现 1 1 1时的大小,例如 100100 100100 100100,这个数的 l o w b i t ( ) lowbit() lowbit()就是 100 100 100,在这个程序中他用来取&后的数字的二进制可用数是多少,这个可用数我们也提前预处理,映射到了 m a p [ ] map[] map[]数组里,然后这个还有一个贪心策略,即当可用数越少答案就越确定,我们用 o n e s [ ] ones[] ones[]数组记录一下所有可出现状态的1的数量,1的数量少代表当前位置越确定,这个可以对程序执行很大的优化。

下面以一个数独游戏为例:
被解决的数独游戏:
在这里插入图片描述

程序跑出的解:
输入的时候空位置用.代替即可
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

可执行代码:

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 9;
int row[N], col[N], cell[3][3], ones[1 << N], map[1 << N], cnt;
char s[N][N];
inline int lowbit(int x) { 
   
  return (x & -x);
}
inline void init() { 
   
  for (int i = 0; i < N; i++)
    row[i] = col[i] = (1 << N) - 1;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      cell[i][j] = (1 << N) - 1;
}
inline int get(int x, int y) { 
   
  return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt) { 
   
  if (!cnt)
    return true;
  int x, y, mav = 10;
  for (int i = 0; i < N; i++) { 
   
    for (int j = 0; j < N; j++) { 
   
      if (s[i][j] == '.') { 
   
        int t = ones[get(i, j)];
        if (mav > t) { 
   
          mav = t;
          x = i, y = j;
        }
      }
    }
  }
  for (int i = get(x, y); i; i -= lowbit(i)) { 
   
    int t = map[lowbit(i)];
    row[x] -= 1 << t;
    col[y] -= 1 << t;
    cell[x / 3][y / 3] -= 1 << t;
    s[x][y] = '1' + t;
    if (dfs(cnt - 1))
      return true;
    row[x] += 1 << t;
    col[y] += 1 << t;
    cell[x / 3][y / 3] += 1 << t;
    s[x][y] = '.';
  }
  return false;
}
int main() { 
   
  for (int i = 0; i < N; i++)
    map[1 << i] = i;
  for (int i = 0; i < (1 << N); i++) { 
   
    int k = 0;
    for (int j = i; j; j -= lowbit(j)) { 
   
      k++;
    }
    ones[i] = k;
  }
  while (true) { 
   
    for (int i = 0; i < N; i++)
      cin >> s[i];
    init();
    cnt = 0;
    for (int i = 0; i < 9; i++) { 
   
      for (int j = 0; j < 9; j++) { 
   
        if (s[i][j] != '.') { 
   
          int t = s[i][j] - '1';
          row[i] -= 1 << t;
          col[j] -= 1 << t;
          cell[i / 3][j / 3] -= 1 << t;
        } else { 
   
          cnt++;
        }
      }
    }
    dfs(cnt);
    for (int i = 0; i < N; i++) { 
   
      for (int j = 0; j < N; j++) { 
   
        cout << s[i][j] << ' ';
      }
      cout << endl;
    }
  }
  return 0;
}

Jetbrains全家桶1年46,售后保障稳定

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/200817.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 微信公众平台定时群发系统(小懒人定时精灵篇)

    微信公众平台定时群发系统(小懒人定时精灵篇)  所谓微信公众平台定时群发系统就是在你一个时间内把你所要发布的文章都填好,然后在选择群发时间段。我最近在使用“小懒人定时精灵”,使用步骤方便,省了我好大部分的时间,听他们官方说现在正在丰富内容,期待以后有更多的功能。“小懒人定时精灵“解救了那些傻傻地守在电脑旁发送微信的人们,现在微信公众平台的推送也能定时群发了。预先到微信后台编辑一条包括文字、图片、语音、视频、图集,然后到小懒…

  • Mac基础操作教程:Mac电脑如何在录屏时录入声音?「建议收藏」

    Mac基础操作教程:Mac电脑如何在录屏时录入声音?「建议收藏」我们经常因为工作需要而对Mac电脑进行录屏操作,但有些新手用户录屏后发现,屏幕里没有声音,这是因为你没有打开麦克风,下面分享Mac电脑在录屏时录入声音教程。1、点击“启动台”,2、打开启动台里“其他”文件夹中的“截屏”,3、在屏幕下方,点击录制屏幕的图标;4、然后点击“选项”,在下拉菜单中选择“麦克风”;5、最后,点击“录制”按钮即可完成。以上就是小编给您带来的Mac基础操作教程:Mac电脑如何在录屏时录入声音,还有哪些关于Mac电脑的操作问题,欢迎来交流。Mac软件资源下载站http

  • dnf钓鱼网站不小心点开了_dnf易语言源码

    dnf钓鱼网站不小心点开了_dnf易语言源码其实本人当时也没注意很多。就按下了“点此充值”注意!这个所谓的登录根本不是TX的登录,其实就是用一个表单将你的帐号和密码发给盗号的!当你打完帐号密码后按下那个“登录”按钮,你的帐号密码已经到了盗号的手里,不过,他们还差一步,才能将你的号彻底洗干净,那就是你的绑定手机和手机令牌、二级密码。好吧,草了个蛋,这是个.net的页面。继续,当你打完你的号码以后不按“登录”,好吧,我解释一下,因为盗号的人不需…

  • Spring Cloud Bus中的事件的订阅与发布(二)

    Spring Cloud Bus中的事件的订阅与发布(二)

  • pip install 使用国内镜像

    pip install 使用国内镜像让PIP源使用国内镜像,提升下载速度和安装成功率。对于Python开发用户来讲,PIP安装软件包是家常便饭。但国外的源下载速度实在太慢,浪费时间。而且经常出现下载后安装出错问题。所以把PIP安装源替换成国内镜像,可以大幅提升下载速度,还可以提高安装成功率。国内源:新版ubuntu要求使用https源,要注意。清华:https://pypi.tuna.tsinghua.edu.cn/…

  • SQLServer2019安装教程「建议收藏」

    打开应用程序点击安装,点第一个全新得SQLserver独立安装下一步这里可能要等他扫描一下,下一步执行全新安装developer和express选哪一个都可以,(,一共有三个,不选Evaluation就可以,虽然可以用,但是他有180天的期限)接受条款,才能点击下一步选择数据库引擎,点击下一步(需要的可以换目录,但最好别换,换到别的(机械)盘可能效率会低)如果这里报错…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号