puzzle - 生成所需难度的数独？

Question

所以，我对数独游戏的生成做了大量的阅读。据我所知，获得所需难度的数独谜题的标准方法是生成一个谜题，然后对其进行评分，然后重复，直到获得可接受的评分。这可以通过使用一些更复杂的求解模式(XY-wing、箭鱼等)通过回溯生成来改进，但这并不是我在这里想要做的。

我想做的，但一直无法找到任何真正的资源，是从“难度值”(0-1.0 值，0 是最简单的，1.0 是最难的)生成一个谜题。

例如，我想创建一个中等难度的拼图，因此选择值 0.675。现在使用该值，我希望能够生成一个中等难度的谜题。

有人知道这样的事情吗？或者也许有类似方法的东西？

Answer 1

添加另一个答案以即时生成所需难度的数独。

这意味着与其他方法不同，该算法运行 只有一次 并返回匹配所需难度的数独配置( 在一个范围内具有高概率或概率=1 )

生成(和评级)数独难度的各种解决方案与 human-based techniques and approaches 有关，可以很容易地评价。

然后一个(在生成数独配置之后)重新解决带有类人解算器的数独游戏，根据解算器使用的技术(例如双翼、x 翼、箭鱼等)，还会分配难度率。

这种方法的问题
(以及我对用例的要求)

为了生成具有给定难度的数独，使用以前的方法需要解决数独两次(一次使用基本算法，一次使用类人求解器)。

一个人必须(预)生成许多只能被评为难度的数独解决后通过类人求解器。因此，您无法一次性即时生成所需的数独。

类人求解器可能很复杂，并且在大多数情况下(如果不是全部)与 9x9 数独网格紧密耦合。所以不容易推广到其他数独(例如 4x4、16x16、6x6 等)

类人技术的难度等级是非常主观的。例如，为什么 x-wing 被认为比隐藏单打更难？ (个人已经手动解决了许多已出版的困难数独谜题，但从未使用过此类技术)

使用了另一种方法，它具有以下优点:

可以很好地推广到任意数独(9x9、4x4、6x6、16x16 等)

具有所需难度的数独配置是一次性生成的

难度等级是客观的。

这个怎么运作？

首先，简单的事实是 拼图越难，需要解决的时间就越多 .

但是要解决的时间与每个空单元格要研究的线索(给定)数量和平均替代方案密切相关。

扩展我的 previous answer ，有人提到，对于任何数独谜题，最少的线索数是谜题的客观属性(例如 for 9x9 grids the minimum number of clues for having a valid sudoku is 17)

可以从那里开始并计算每个难度级别的最少线索数(线性相关)。

此外，在数独生成过程的每个步骤中，可以确保每个空单元格的平均替代方案(待调查)在给定范围内(作为所需难度的函数)

根据算法是否使用回溯(对于所讨论的用例，算法没有回溯)，可以以概率 = 1 或在边界内以高概率(分别)达到所需的难度。

使用此算法生成的数独测试和基于先前方法(类人求解器)的难度评级显示了所需难度和估计难度之间的相关性，以及对任意数独配置的更大泛化能力。

(已在线使用 sudoku solver(以及 this one)来关联测试数独的难度)

代码免费提供 on github sudoku.js (along with sample demo application) ，CrossWord.js 的缩小版本，是 JavaScript 中的专业填字游戏构建器，由同一作者