Sudoku as a Constraint Problem
Sudoku as a Constraint Problem
复制标题
数独作为约束问题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Helmut Simonis
中科院分区：
文献类型：
--
作者：
Helmut Simonis
约束编程终于到达了大众，成千上万的报纸读者(特别是在英国)正在解决他们的日常约束问题。他们应用名为“X翼”和“剑鱼”的复杂传播方案来寻找一种看起来相当简单的数独谜题的解决方案。不幸的是，他们没有意识到这是约束编程。在本文中，我们试图从约束的角度来理解谜题，给出求解和生成谜题的模型，并给出一个谜题实例的难度的客观度量。这一措施似乎与分配给普通公众的问题实例的等级(例如，容易到困难)很好地相关。我们还展示了如何使用冗余约束来加强模型，以及如何使用二部匹配和流算法来实现这些约束。
Constraint programming has finally reached the masses, thousands of newspaper readers (especially in the UK) are solving their daily constraint problem. They apply complex propagation schemes with names like “X-Wing” and “Swordfish” to find solutions of a rather simple looking puzzle called Sudoku. Unfortunately, they are not aware that this is constraint programming. In this paper we try to understand the puzzle from a constraint point of view, show models to solve and generate puzzles and give an objective measure of the difficulty of a puzzle instance. This measure seems to correlate well with grades (e.g. easy to hard) that are assigned to problem instances for the general public. We also show how the model can be strengthened with redundant constraints and how these can be implemented using bipartite matching and flow algorithms.