数独生成器算法

Question

我做了一个生成sudokus的算法,但效率非常低.每个难题都需要几分钟才能生成 所以现在我试图以最佳方式再次编写它.但我遇到了一些我需要帮助的问题.

1. 有两个aproaches,从空白网格开始并添加数字,然后检查它是否可以解决.第二种方法是创建包含所有81个数字的完整有效网格,然后删除,直到我们对剩余数字的数量感到满意并且它仍然可以解决.

首先我使用第一种方法,但现在我将使用第二种,因为我认为它更有效(我们从有效的拼图开始,保证可以解决).我说第二种方法更好吗？

1. 当我试图生成完全填充的网格时,我遇到了困难.我的算法是:

   • 为每个细胞设置候选者.最初他们是数字1到9.
   • 选择无值的随机单元格.
   • 从该单元格中选择随机候选项并将其指定为单元格值.其他候选人被丢弃.
   • 现在对于每一行,对应于指定单元格的单元格和正方形I从这些候选中移除单元格的值,因此每个数字在行/列/正方形中是唯一的
   • 重复

此技术保证随机网格没有重复的数字.但是,大多数情况下,当我没有违反任何放置规则时,就会发生冲突 - 比如所有候选人都已被移除的空单元格,我需要重新开始.是否有更优雅/有效的方法用数字填充整个网格而不破坏放置规则和仍然是随机数？

谢谢.

Answer 1

你看过现有的算法和/或代码吗？

查看http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf获取算法描述,以及Peter Norvig的文章http://norvig.com/sudoku.html.

Python中有一些实现.到目前为止,我从未见过已发布的C#解决方案.

祝好运!