数独逻辑求解器

Question

由于缺乏信息，我在这里锁定了最后一个问题，现在我将尝试进一步解释，以消除混淆。

好的，先离开，获取一些关于我正在做什么的背景信息<我开始了一个制作数独游戏的个人项目，学习面向对象编程、数组列表、算法、模型/控制/设计层，并扩展我的编程知识<我在制作这个游戏方面已经走了很长的路，它即将完成，但我遇到了一个需要帮助解决的小问题。

当我生成3个数独，一个简单，一个中等和一个困难时，我遇到了问题。
简单和中等难度的数独是可以解决的，但困难的数独是无法解决的。

工作原理：
首先，我有一个使用随机数生成和验证的算法来生成有效的数独板，然后我将其传递给另一个算法，该算法遍历9x9板上的所有数字，并按百分比概率删除它们，该百分比概率在调用该方法时指定，例如，简单删除一个数字的概率为50%，困难删除一个数字的概率为65%。

我的问题：
好的，我的问题是我生成了一个难度为“硬”的数独，但发现它无法解决。现在我没有验证方法来检查这个谜题是否可以以任何方式解决，所以长话短说，如果它可以解决，那是偶然的。

我需要的：
我需要一个算法或方法来验证这个难题是否可以解决，因为现在我只有一个随机的机会可以解决，因为随机数删除的机会。这不应该使用蛮力（回溯）来完成，而是应该查看拼图并决定哪些数字去哪里，基本上就像你和我解决它一样。这样我不仅可以验证它是否有一个单一的解决方案，还可以验证你和我是否可以解决它。

变量和类如何连接的小图形视图：

使用上述示例对数独的结构进行可视化表示：

数独中1到9的数字是1到9的单元格。

如果您需要有关该计划的任何更详细的信息，请告诉我，我会将其添加到此表格中，我只是尽量保持简短和简单，同时仍然试图涵盖与此问题相关的所有内容。

Answer 1

你必须做的第一部分是非编程的：你必须找到一个详尽的（在某种程度上...）解决方法列表。然后依次应用它们，直到你解决了这个难题并宣布它可以被你的程序解决，或者继续卡住并决定拒绝它。

但这还不够。如果你能找到一个解决方案，你仍然必须用暴力来验证这个解决方案是唯一的。如果不这样做，您可能会生成具有多个解决方案的谜题，而这些解决方案被大多数玩家宣布为无效。

拒绝您的方法无法解决的有效谜题并不重要，因为没有人会注意到它们（只要您不让用户输入他们自己的谜题）。

Answer 2

我同意Tarik在他的回答中所说的。

我能想到的可能算法（这只是想法，不是最佳的，但可以改进）：

第一部分-直接解决：

• 1） 为每个空单元格分配可能要插入的数字列表（基于数独规则）
• 2） 迭代每个空单元格，检查要插入的可能数字列表是否只包含一个元素

如果只包含一个可能要插入的数字，请插入此数字并重复步骤（1）。如果无法插入更多数字，请转到第二部分。

第二部分-分支：

• 3）根据要插入的可能数字的数量（从第一部分开始）按升序迭代每个空单元格。
• 4）递归来了。对于要填写给定单元格的每个可能的数字，创建单独的数独板，并尝试从步骤（1）开始以相同的方式解决它

这种递归方法（深度优先搜索）将允许您找到所有可能的解决方案。

这是很好的锻炼，以提高你的编程技能：）

Answer 3

我将尝试明确或暗示地回答您提出的问题：

“首先，我有一个使用随机数生成和验证生成有效数独板的算法”

如果您的算法确实生成了一个有效的数独板，那么它应该是可解的。如果这不是你所说的可解性，请详细说明。

“我需要一个算法或方法来验证这个谜题是否可以解决，因为现在我只有一个随机的机会，因为随机数删除的机会。”

任何求解数独的算法都将验证它确实是可解的。任何数字删除实际上都可能使游戏更难解决，并可能增加有效解决方案的数量，从而使其无效（参见SergeBallesta的得体评论）。我还想提一下：“数独游戏通常分为简单、中等或困难三类，通常有更多的起始线索，但并不总是更容易解决。但从数学上量化难度是很困难的。”。参见数独的数学导致谜题硬度的“里氏标尺”

“这不应该使用暴力（回溯）来完成，而是应该看看谜题并决定数字的去向，基本上就像你和我解决它一样。”

您需要的是一种算法，该算法可以模拟人类在解决此问题时的行为和思维。我认为这不是一个可行的要求，可能属于人工智能的研究领域。人类解决数独等谜题的思路因人而异。初学者可能会采用类似于回溯深度优先搜索的方法。在处理棘手问题时，这不是人类最有效的方法。在国际象棋等游戏中，这根本不是一种可持续的方法。专家们倾向于通过对董事会的全局观点来识别模式。我很肯定，数独高手也会遵循类似的过程。了解专家如何回忆棋局