如何创建像Sudoku这样的逻辑纸笔游戏?

问题描述 投票:0回答:2

此问题不仅限于数独,还可以包括Kakuro,Hitori,Nurikabe等。

我了解数独和其他类似难题的算法,但我很难确定如何创建说我想要一个Sudoku生成器(使用最受欢迎的)。我想它需要分两个步骤工作:

    创建有效的解决方案
  1. 除去部分溶液,直到剩下所需的线索为止。
  2. 创建解决方案并非易事,如果您随意走到最后一步并最终陷入僵局,通常它会很好地工作。

删除解决方案的某些部分,以确保只删除多余的部分,这也不是小事。

是否有通用算法可以解决?我该如何实施这样的事情?

我知道我的问题是“广泛的”,到目前为止,我并没有显示很多(将问题分成两部分),但是我没有任何线索可以开始考虑该算法。我不是在寻求解决方案,而是在寻求有关如何开始的提示。

此问题不仅限于数独,还可能包括Kakuro,Hitori,Nurikabe等。我了解解决数独和其他类似难题的算法,但我很难弄清楚...]]] >>

您通常可以按以下方式进行处理:

定义一组可以帮助人类进行游戏的规则。例如,在数独中,这些规则之一可能是:

    称为给定单元格的“影响范围”,即与该给定单元格位于同一行,同一列或同一3x3块中的单元格。规则是此单元格不能具有其影响领域中已经使用的任何值。如果那意味着只剩下一个有效值,则将该值放在此单元格中。
  • 另一个规则可能是:

      如果在同一3x3块中存在无法在其他任何地方使用的值,则将该值放在此单元格中。同样,如果不能在单元格行的其他任何地方使用值;或不能在单元格列的其他任何地方使用。
  • 显然还有其他规则。这些规则可能更复杂。根据人类验证和应用规则的难度来对规则进行排名。通过以人类的方式看待解决游戏的理由,力求做到尽可能完整。将这些规则实现为程序中的功能。在Sudoku示例中,可以将这样的规则函数应用于给定的单元格,并返回成功(即该单元格获得值)或失败(该规则不能用于扣除其值)。

    假设程序应该生成给定难度的数独。我们将解释为这意味着要解决数独问题,将要求玩家至少使用一次至少具有该难度的规则或从未预见到的奇特规则。

  • 现在从已解决的数独开始。随机删除50%的值。检查数独是否可以仅使用难度范围内的已知规则来解决。如果不是,请恢复已删除细胞的25%,然后重复。如果可以解决,请再随机去除25%的细胞。像二进制搜索算法一样,继续将涉及的单元格数量减半(恢复它们或删除它们),直到到达搜索结束为止。对于Sudoku游戏,此过程大约需要进行7次迭代。然后,您将拥有一种“局部最小值”,可以在其中应用规则来求解。

    这远非完美,因为很可能还有一些其他单元可以清除,同时仍然允许规则朝着解决方案努力。因此,如果您想优化此搜索,则可以添加一些其他迭代以删除随机单元,只要仍然可以通过应用规则来解决结果板。

    您可以通过解决一个从一开始就没有分配任何东西的数独难题来创建数独难题。如果您的求解器通过填充正方形而进展,则可以通过在适当的位置停止(或回滚)该过程来“删除”它们。
    algorithm language-agnostic sudoku
    2个回答
    1
    投票
    您通常可以按以下方式进行处理:

    0
    投票
    您可以通过解决一个从一开始就没有分配任何东西的数独难题来创建数独难题。如果您的求解器通过填充正方形而进展,则可以通过在适当的位置停止(或回滚)该过程来“删除”它们。
    © www.soinside.com 2019 - 2024. All rights reserved.