苏杜克生成器 1.2

作者:

Ralf Schlatterbeck <rsc@runtux.com>

苏杜克生成器是一个生成苏杜克数字谜题的工具。它内部使用遗传算法，因此可以作为遗传算法的入门。生成的苏杜克通常很难解决——适合戒掉苏杜克瘾（或者也许不是）。

它还包括一个简单的深度优先搜索求解器（带有一些优化）用于苏杜克谜题——求解器在生成苏杜克谜题时内部需要。包含的sudoku脚本可以被调用，并从标准输入读取苏杜克。它输出解决方案（如果有）或如果没有唯一的解决方案，则输出多个（最多到最大数量）。

它内部使用我自己的PGApy包装器，用于PGApack遗传算法库（我现在也在维护）。

苏杜克谜题的表示很简单：9行，每行9个数字，例如

000704800
001000200
200050000
407090000
010000080
600008900
100000050
050000706
000069002

数字1-9代表拼图中的给定数字，而0代表空格。解决好的拼图不包含0。我采用了文件扩展名.sud来表示这种格式。示例中的拼图是由sudokumaker创建的，使用了选项-r 42来设置随机种子为42（如果没有给出-r选项，则为默认值），因此可以使用此选项（在64位架构上）来重现拼图。上述示例在用sudoku_as_tex渲染并使用LaTeX编译后，看起来类似于以下内容

支持一些数独拼图的变体。第一个变体增加了对角线（因此在每个对角线上都必须包含数字1-9），可以使用--diagonal选项请求此变体。一个打印的示例（同样使用随机种子42生成，但现在使用--diagonal选项）如下所示

对于对角线变体，我采用了扩展名.sudd – 注意，正常数独和对角线约束数独是不兼容的，如果将其解释为正常数独，则对角线约束数独会有多个解。

第二个变体要求每个象限中都有9种不同的颜色，每种颜色在每个象限中的位置始终相同。每种颜色上都必须有数字1-9。对于这个变体，我采用了扩展名.sudc，就像对角线约束数独一样，如果将其解释为正常数独，则颜色约束数独会有多个解。此变体可以使用--colorconstrained选项请求。一个示例如下

可以使用包含的sudoku_as_tex程序将数独拼图打印为LaTeX。如果给出--diagonal选项，则当前支持以黄色打印对角线。可以使用--colorconstrained选项打印颜色约束数独。以下颜色映射适用

如果这些字母用于颜色约束数独，则上述表格适用。也可以使用其他字母，但在此情况下，打印的颜色分配将是任意的。

第三种变体，有时称为キカグク，使用不规则的颜色形状而不是3x3方块。这些目前只能使用--kikagaku选项打印，但不能使用sudokumaker生成。我使用的格式是.sud格式的修改版。它包含与.sud中相同的格式数字，后面是包含字母的行，其中每个字母代表一种独特的颜色。当然，每个字母必须恰好出现9次。我没有包括一个拼图，因为我目前不能自动生成它们。该格式的空拼图如下

000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
rrrrvvvvg
brbrrvggg
brbrovvvg
bbbbovggg
blooooogp
llldopppp
ldddoypyp
llldyypyp
lddddyyyy

适用于颜色约束数独拼图的相同颜色映射也适用。这将如下渲染

对于遗传算法库，需要并行遗传算法库（PGApack）的Python包装器PGApy。应该有对PGApy的Windows支持，但我还没有在Windows上测试最新更改。

版本1.2：并行版本

• 如果使用pgapy的并行（MPI）版本安装，则评估可以并行化

• 缓存现在在 pre_eval 和 endofgen 中完成： pre_eval 在缓存中查找命中，防止这些个体再次评估。 endofgen 方法填充缓存。

• 随机种子默认为 42

• 移除 --verbose 选项

版本 1.1：添加许可信息

• 添加 LICENSE 文件

• 将许可头插入尚未存在的 Python 文件中

版本 1.0：标记为稳定，Python3

现在标记为开发状态生产/稳定

• Python3

• 稳定

• 移除 SF 标志

• 更新文档，图片

• 添加渲染示例

版本 0.4：打包修复

再次修复包名，坚持使用 sudokumaker 以避免名称冲突。

• 包命名空间现在是 sudokumaker

• Sudokumaker 依赖于 rsclib.sourceforge.net

版本 0.3：颜色，对角线

现在支持颜色限制和对角线限制的 Sudoku。

• 对角线限制的 Sudoku 必须在对角线上有数字 1-9。打印时，对角线以黄色打印。

• 颜色限制的 Sudoku 有 9 种额外的颜色，这些颜色在每一个象限中的位置相同。这些也必须有数字 1-9。打印时我们选择了 9 种不同的浅色。

版本 0.2：更新 README

README（以及从中生成的 SF 主页）有错误的项目链接。此外，python 包索引不接受我的一个分类器。呃。

• 修复 README 中的项目链接（SF 标志）

• 移除 pypi 不接受的分类器

版本 0.1：初始发布

Sudoku Maker 是一个 Sudoku 数字谜题生成器。它内部使用遗传算法。

• 长期沉默开发后的首次发布