如何用独特的解决scheme生成Sudoku板

如何用独特的解决scheme生成Sudoku板? 我认为是初始化一个随机板,然后删除一些数字。 但我的问题是如何保持解决scheme的独特性?

简单:

  1. 使用高效的回溯algorithm查找所有解决scheme。
  2. 如果只有一个解决scheme,你就完成了。 否则,如果您有多个解决scheme,请find大多数解决scheme不同的位置。 在这个位置添加号码。
  3. 转到1。

我怀疑你可以find一个比这更快的解决scheme。

这是我自己的SuDoKu程序的方式:


  1. 从一个完整有效的董事会开始(填写81个号码)

  2. 列出所有81个细胞位置并随机洗牌

  3. 只要列表不是空的,从列表中的下一个位置,并从相关的单元格中删除号码

  4. 使用快速解算器testing唯一性(如果需要,则使用回溯)。 我的求解器能够计算所有的解决scheme,但是当它find一个以上的解决scheme时,它会停下来。

  5. 如果当前板子只有一个解决scheme,转到步骤3)并重复。

  6. 如果当前板子有多个解决scheme,则撤销上次移除(步骤3),并从列表中的下一个位置继续步骤3

  7. 停止testing所有81个职位。


这不仅可以为您提供独特的板子,还可以让您在不破坏解决scheme的独特性的情况下无法移除更多数量的板子。

当然,这只是algorithm的后半部分。 上半部分是先find一个完整的有效的董事会(随机填写!)它工作非常相似,但“在另一个方向”:


  1. 从空板开始

  2. 在空闲小区之一添加一个随机数(小区是随机select的,根据SuDoKu规则从该小区有效的号码列表中随机select号码)

  3. 使用回溯求解器检查当前板是否至less有一个有效的解决scheme。 如果不是,请撤消第2步,并用另一个数字和单元格重复。 请注意,这一步可能会自行生成完整有效的板,但这些板不是随机的。

  4. 重复,直到董事会完全充满数字

你可以作弊。 从现有的数独板开始,可以解决,然后摆弄它。

您可以将任意三行的3×3块与其他行交换。 您可以将三个3×3块的任何一列与另一列交换。 在每个块行或块列中,可以交换单行和单列。 最后,您可以对数字进行排列,因此只要整个棋盘上的排列是一致的,那么在填充的位置就会有不同的数字。

这些变化都不会使解决板无法解决。

除非P = NP,否则没有多项式时间algorithm可以用一个解来生成一般的数独问题。

在他的硕士论文中,Takayuki Yato定义了另一个解决scheme问题 (ASP),其目标是给出一个问题和一些解决scheme,find不同的解决scheme来解决这个问题,或者说不存在。 Yato然后定义了ASP完整性,难以find另一个解决scheme的问题,并且显示数独是ASP完整的。 因为他也certificate了ASP的完整性意味着NP硬度,这意味着如果你允许任意大小的数独棋盘,没有多项式时间algorithm来检查你生成的谜题是否有唯一的解决scheme(除非P = NP)。

对不起,以破坏你的快速algorithm的希望!

提供一个通用的解决scheme并不容易。 你需要知道几件事来产生一个特定types的数独…例如,你不能build立一个超过9个空9数字组(行,3×3块或列)的数独。 在一个单一的解决scheme中,最小给定的数字(即“线索”)被认为是17,但是如果我没有错,这个数独的数字位置是非常具体的。 数独的线索平均数大概是26,我不确定,但是如果你退出一个完整的网格数,直到有26个并且以对称的方式离开,你可能会有一个有效的数独。 另一方面,您可以从完成的网格中随机退出数字,然后使用CHECKER或其他工具对其进行testing,直至出现OK。

我也认为你必须明确地检查唯一性。 如果你的投票数less于17,那么一个独特的解决scheme是不太可能的,尽pipe还没有被发现,尽pipe还不清楚它是否可能存在。

但是你也可以使用SAT求解器,而不是写一个自己的回溯algorithm。 这样,您可以在一定程度上调节find解决scheme的困难程度:如果您限制SAT解算器使用的推理规则,则可以检查是否可以轻松解决这个难题。 只是谷歌“SAT解决数独”。

这是一个经典的数独谜题的方法(数独谜题有一个唯一的解决scheme;预填充的方块围绕中心广场R5C5对称)。

1)从一个完整的网格开始(使用组填充加循环来轻松获取)

2)如果可以使用剩下的线索推断清除的方块,则从两个对称的方块中移除数字。

3)重复(2)直到所有的数字被检查。

使用这种方法,您可以创build一个非常简单的数独谜题编程或不编程。 你也可以使用这种方法来制作更难的数独谜题。 您可能需要在YouTube上search“创build经典数独”以获得一步一步的示例。