Generating Sudoku Puzzles as an Inverse Problem Team
Generating Sudoku Puzzles as an Inverse Problem Team
复制标题
作为逆问题团队生成数独谜题
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
G. Zambon
中科院分区：
文献类型：
--
作者：
G. Zambon
本文将数独谜题的生成作为一个反问题来研究，目的是设计出具有期望性质的数独谜题。我们研究了一些常用的方法来解决数独难题，然后构造方法来反转每一个方法。然后，从一个完整的数独棋盘开始，我们应用这些逆方法来构造一个具有少量线索的谜题。这是通过修改的广度优先搜索来完成的，它确保了我们的谜题将通过我们所描述的方法唯一地可解。此外，该搜索算法利用启发式算法来减少运行时间，并构造具有特殊特征的数独谜题。特别是，我们将能够生成所需难度的谜题。
This paper examines the generation of Sudoku puzzles as an inverse problem, with the intention of engineering Sudoku puzzles with desired properties. We examine a number of methods that are commonly used to solve Sudoku puzzles, and then construct methods to invert each. Then, starting with a completed Sudoku board, we apply these inverse methods to construct a puzzle with a small set of clues. This is accomplished with a modified breadth-first search which ensures that our puzzle will be uniquely solvable by the methods we have described. Furthermore, this search algorithm utilizes heuristics both to reduce runtime, and to construct a Sudoku puzzle with special features. In particular we would be able to generate a puzzle of a desired difficulty.