我制作了一个生成数独的算法,但效率非常低。每个谜题都需要几分钟才能生成。所以现在我正在尝试以最佳方式重新编写它。但我遇到了一些问题,需要帮助。
有两种方法:
- 从空白网格开始并添加数字,然后检查它是否可解。
- 创建包含所有 81 个数字的完整有效网格,然后删除,直到我们对剩余数字的数量感到满意并且仍然可以解决为止。
首先我使用了第一种方法,但现在我将使用第二种方法,因为我认为它更有效(我们从保证可以解决的有效谜题开始)。我是对的,第二种方法更好?
当我尝试生成完整填充的网格时,我遇到了困难。我的算法是:
- 为每个单元格设置候选者。最初它们是数字 1 到 9。
- 选择没有值的随机单元格。
- 从该单元格中选择随机候选并将其指定为单元格值。其他候选人被丢弃。
- 现在,对于与指定单元格相对应的每一行、单元格和正方形,我从这些候选单元格中删除单元格的值,因此每个数字在行/列/正方形中都是唯一的
- Repeat
该技术保证随机网格没有重复的数字。然而,大多数时候,当我不违反任何安置规则时,就会发生冲突——比如所有候选人都被删除的空单元格等,我需要重新开始。是否有更优雅/有效的方法来用数字填充整个网格而不违反放置规则并且仍然是随机数字?
您看过现有的算法和/或代码吗?
查看https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf算法描述,以及 Peter Norvig 的文章http://norvig.com/sudoku.html http://norvig.com/sudoku.html.
Python 中有一些实现。到目前为止,我从未见过已发布的 C# 解决方案。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)