【文件属性】：
文件名称：sudoku:使用Dancing Links（DLX）的Sudoku求解器
文件大小：1.33MB
文件格式：ZIP
更新时间：2021-05-09 22:39:25
Python
使用Dancing Links（DLX）的Sudoku求解器
数独可以简化为精确的掩护问题，该问题被认为是NP完全的。 NP-complete的分类仅适用于广义nxn数独，而不适用于9x9数独，因为它是有限实例。
确切的掩护问题是一个决策问题，目标是找到确切的掩护。 给定一个集合S和另一个集合，其中每个元素都是S的子集，是否有可能选择一个子集，以使S中的每个元素恰好存在于所选集合中的一个之中？ 集合的这种选择被认为是集合S的封面。
由Donald Knuth创建的算法X（ALX）可用于查找针对确切掩盖问题的所有解决方案。 跳舞链接（DLX）是Knuth建议的有效实现算法X的技术。
该求解器实现了Knuth所描述的DLX算法，但是将数独简化为精确的覆盖问题并不是真正的完全缩减，因为它直接归结为DLX中使用的链接。 完全的减少是首先将Sudoku简化为二进制矩阵，然后创建DLX中使用的链
【文件预览】：
sudoku-master
----.gitignore(11B)
----dlx.py(8KB)
----requirements.txt(25B)
----.travis.yml(259B)
----LICENSE(34KB)
----README.md(5KB)
----tests()
--------data()
--------__init__.py(0B)
--------test_dlx.py(2KB)
--------test_sudoku.py(919B)
----sudoku.py(8KB)