数独游戏 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
GD Star Rating
loading...
本文一共 701 个汉字, 你数一下对不对.loading...
上一篇: 整合 ChatGPT Prompt AI到 STEEM 区块链上!
下一篇: 剑桥披萨朝圣者 (Pizza Pilgrims Cambridge)
扫描二维码，分享本文到微信朋友圈
