主页
随机数独游戏的算法设计 (Sudoku)
标签:, , , , , , , , , , , ,

随机数独游戏的算法设计 (Sudoku)

No Comments 2023年4月24日 学习笔记, 技术, 数据结构与算法, 游戏, 程序设计, 算法, 计算机, 资讯, 面试

sudoku-solver 随机数独游戏的算法设计 (Sudoku) 学习笔记 技术 数据结构与算法 游戏 程序设计 算法 计算机 资讯 面试

数独游戏 Sudoku

给定一个数独(Sudoku), 我们可以使用深度优先搜索算法(DFS), 迭代加深搜索算法(IDS)或广度优先搜索算法(BFS)来寻找可能的解. 反过来, 如果我们要设计一个算法来生成有效的数独, 我们需要澄清以下问题:

  • 生成的数独(Sudoku)必须有可解状态吗? 是的
  • 生成的数独(Sudoku)有多个解吗? 我们可以假设返回的Suduoku只有1个唯一解
  • 生成的数独(Sudoku)的找解难度? 我们可以为此设置一个参数: 简单, 中等或困难

一共有6.671×10^21个有效的数独状态, 如果我们忽略旋转, 镜像状态等重复的状态, 这个数字就降到了5.4×10^9个状态. 我们可以随机生成一个由数字1-9填充的矩阵, 并检查它是否是有效的数独, 但这非常低效, 因为生成的矩阵极有可能不是有效的数独.

设计一个随机数独的算法

为了设计一个有效的算法, 生成一个随机的有效数独, 我们可以采用以下算法:

  1. 使用回溯(深度优先搜索)算法来生成一个具有随机性的有效完整数独. 例如, 我们可以随机选择数字, 而不是尝试按顺序填充1到9的数字.
  2. 每次删除一个随机数字.
  3. 检查数独状态是否可解且只包含一个解决方案(我们可以使用深度优先搜索算法/回溯或广度优先搜索算法).
  4. ​如果是, 则继续执行步骤2, 直到我们删除了N个数字. 删除的数字的个数对应于难度级别. 删除更多数字会使数独状态更难.
  5. 如果它既不可解也没有一个解决方案, 我们必须将数字放回去, 然后重试另一个随机数字(步骤2).

这是来自ChatGPT 3.5(Open AI + Microsoft Azure)的答案:

  1. 创建一个9×9的网格, 并用数字1到9填充它.
  2. 随机选择一个数字并将其删除.
  3. 重复步骤2, 直到从网格中删除所有数字.
  4. 检查网格是否是一个有效的数独.
  5. 如果网格是有效的数独, 则将其作为解决方案返回.
  6. 否则, 则重复步骤2-5, 直到找到一个有效的解决方案.

英文: Teaching Kids Programming – How to Design a Random Sudoku? Algorithm to Design a Random Sudoku

面试经历

面试题

面试技巧

面试其它

GD Star Rating
loading...
本文一共 701 个汉字, 你数一下对不对.
随机数独游戏的算法设计 (Sudoku). (AMP 移动加速版本)
上一篇: 整合 ChatGPT Prompt AI到 STEEM 区块链上!
下一篇: 剑桥披萨朝圣者 (Pizza Pilgrims Cambridge)
赞赏我的几个理由.
¥ 打赏支持

扫描二维码，分享本文到微信朋友圈
d2733cb86adbaa2944a10411fade7a7a 随机数独游戏的算法设计 (Sudoku) 学习笔记 技术 数据结构与算法 游戏 程序设计 算法 计算机 资讯 面试

相关文章：

  1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  2. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  3. 40 英镑 购买山寨版的 WINDOWS PHONE – BLU WIN 最近手头紧 结果还摔坏手机了, 然后就在EBAY上把不用的手机都卖了. 摔坏的NOKIA手机卖了7英镑. 三星35 IPHONE4 45英镑. 昨天到剑桥市中心家教2小时 80英镑. 在AMAZON上订了一BLU 手机 40英镑. 虽然是 PRIME 帐号...
  4. 在英国给孩子换学校的经历: 孩子离开了村里的小学 由于搬了家, 孩子上学得提前半小时出门了, 因为早上堵, 也得开车半小时才能到. 之前在 Fen Drayton 村庄上小学, 早上8:45学校门开, 9点敲钟孩子排队依次进入教室, 我们由于在村里, 只需要提前5分钟出门和孩子一起走路就可以了. 现在一下子早上变得很匆忙, 得叫孩子起床, 做早饭,...
  5. 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
  6. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
  7. 给孩子第一台NUC小电脑 Next Unit of Computing Next Unit of Computing (NUC) is a line of small-form-factor computers...
  8. 公司请的专业摄影师 公司来了新的CEO管理之后,很多事情都不一样了, 特别是一些公司对外形象的事情就特别的在意, 比如公司网站用上SSL.现在公司还有空闲的位置,请速来(钱多人不傻). 一月份出差回LUTON,刚好公司请来摄影师给高层管理照像放网站上的,于是我也凑了凑热闹(但是却还不够资格被放在公司网站上),不过没关系,放这里也差不多. 人到中年, 沧桑感强了些. 更新更新: 同事用他NB的单反给谢菲尔得办公室的人也拍了一组这样的照片.看起来很不错, 很专业,灯光,道具应有尽有.我已经用在了LINKEDIN页面上,立马高大上. 本文一共 230 个汉字, 你数一下对不对. 公司请的专业摄影师. (AMP...

评论