数独游戏 Sudoku
给定一个数独(Sudoku), 我们可以使用深度优先搜索算法(DFS), 迭代加深搜索算法(IDS)或广度优先搜索算法(BFS)来寻找可能的解. 反过来, 如果我们要设计一个算法来生成有效的数独, 我们需要澄清以下问题:
- 生成的数独(Sudoku)必须有可解状态吗? 是的
- 生成的数独(Sudoku)有多个解吗? 我们可以假设返回的Suduoku只有1个唯一解
- 生成的数独(Sudoku)的找解难度? 我们可以为此设置一个参数: 简单, 中等或困难
一共有6.671×10^21个有效的数独状态, 如果我们忽略旋转, 镜像状态等重复的状态, 这个数字就降到了5.4×10^9个状态. 我们可以随机生成一个由数字1-9填充的矩阵, 并检查它是否是有效的数独, 但这非常低效, 因为生成的矩阵极有可能不是有效的数独.
设计一个随机数独的算法
为了设计一个有效的算法, 生成一个随机的有效数独, 我们可以采用以下算法:
- 使用回溯(深度优先搜索)算法来生成一个具有随机性的有效完整数独. 例如, 我们可以随机选择数字, 而不是尝试按顺序填充1到9的数字.
- 每次删除一个随机数字.
- 检查数独状态是否可解且只包含一个解决方案(我们可以使用深度优先搜索算法/回溯或广度优先搜索算法).
- 如果是, 则继续执行步骤2, 直到我们删除了N个数字. 删除的数字的个数对应于难度级别. 删除更多数字会使数独状态更难.
- 如果它既不可解也没有一个解决方案, 我们必须将数字放回去, 然后重试另一个随机数字(步骤2).
这是来自ChatGPT 3.5(Open AI + Microsoft Azure)的答案:
- 创建一个9×9的网格, 并用数字1到9填充它.
- 随机选择一个数字并将其删除.
- 重复步骤2, 直到从网格中删除所有数字.
- 检查网格是否是一个有效的数独.
- 如果网格是有效的数独, 则将其作为解决方案返回.
- 否则, 则重复步骤2-5, 直到找到一个有效的解决方案.
英文: Teaching Kids Programming – How to Design a Random Sudoku? Algorithm to Design a Random Sudoku
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK