论文标题
生成可溶解策略的Sudoku线索的确切方法
Exact Method for Generating Strategy-Solvable Sudoku Clues
论文作者
论文摘要
Sudoku拼图通常在初始数字的布置方面具有常规模式，通常可以通过已知的解决技术（称为策略）来解决。在本文中，我们考虑了生成此类Sudoku实例的问题。我们介绍了一个严格的框架，以讨论有关策略的Sudoku实例的解决性。这使我们不仅可以根据一些合理的假设处理已知策略，还可以处理一般策略。我们提出了一种确定一组线索位置的Sudoku线索的确切方法，该线索可通过一组给定的策略解决。这是第一个确切的方法，除了微不足道的蛮力搜索。除了线索生成外，我们还提出了方法的应用，以确定可溶解策略可溶解的Sudoku线索的最小数量。我们进行实验以评估我们的方法，改变了随机的位置和线索数量。我们的方法在许多网格中终止了$ 1 $分钟。但是，随着线索的数量接近$ 20 $，运行时间迅速增加，超过设定的时间限制为$ 600 $秒。我们还评估了几种实例的方法，其中$ 17 $的线索位置是从已知的最低sudokus中获得的，以查看决定不可解性的效率。
A Sudoku puzzle often has a regular pattern in the arrangement of initial digits and it is typically made solvable with known solving techniques, called strategies. In this paper, we consider the problem of generating such Sudoku instances. We introduce a rigorous framework to discuss solvability for Sudoku instances with respect to strategies. This allows us to handle not only known strategies but also general strategies under a few reasonable assumptions. We propose an exact method for determining Sudoku clues for a given set of clue positions that is solvable with a given set of strategies. This is the first exact method except for a trivial brute-force search. Besides the clue generation, we present an application of our method to the problem of determining the minimum number of strategy-solvable Sudoku clues. We conduct experiments to evaluate our method, varying the position and the number of clues at random. Our method terminates within $1$ minutes for many grids. However, as the number of clues gets closer to $20$, the running time rapidly increases and exceeds the time limit set to $600$ seconds. We also evaluate our method for several instances with $17$ clue positions taken from known minimum Sudokus to see the efficiency for deciding unsolvability.
