问数独逻辑求解器

EN

我将尝试显式或含蓄地回答您提出的问题：

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

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

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

任何解决数独的算法都会验证它确实是可解的。任何数字删除实际上可能会使游戏更难解决，并可能增加有效解决方案的数量，从而使其无效(请参阅Serge Ballesta所做的机智评论)。我还想提一下：“数独游戏通常分为容易、中等和困难三种类型，这些游戏通常有更多的起始线索，但并不总是更容易解决。但是用数学来量化难度是很困难的。”请参阅Mathematics of Sudoku Leads To "Richter Scale" of Puzzle Hardness

“这不应该使用暴力(回溯)来完成，而是应该看着谜题，决定哪些数字会去哪里，基本上就像你和我会解决它一样。”

您要求的是一种能够模拟人类行为和思维来解决此问题的算法。我认为这不是一个可行的要求，很可能属于人工智能的研究领域。人类解决数独等难题的思路因人而异。初学者可能会遵循类似于深度优先搜索和回溯的方法。在处理难题时，这对人类来说不是最有效的方法。在国际象棋这样的游戏中，这根本不是一种可持续的方法。专家们倾向于通过对棋盘进行全局观察来识别模式。我非常确定，数独高手也会遵循类似的过程。请参阅How experts recall chess positions

我赞同Tarik在他的回答中说的话。

我能想到的可能算法(这只是一个想法，并不是最优的，但可以改进)：

第一部分-简单的解决方案：

• 1)为每个空单元格分配要插入的可能数字列表(基于数独规则)。
• 2)遍历每个空单元格并检查要插入的可能数字列表是否只包含一个元素。

如果只包含一个要插入的可能数字，则插入此数字并重复步骤(1)。如果你不能插入更多的数字，请转到第二部分。

第二部分-分支：

• 3)根据要插入的可能数字的数量(从第一部分开始)以升序遍历每个空单元格。
• 4)这里是递归。对于每个要填充给定单元格的可能数，创建单独的数独棋盘，并尝试以相同的方式从步骤(1)

开始求解

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

这是提高编程技能的好练习:)

你必须做的第一部分是非程序性的:你必须找到一个详尽的(到某一点……)解算方法列表。然后依次应用它们，直到你解决了难题并声明它可被你的程序解决，或者保持卡住并决定拒绝它。

但这还不够。如果你能找到一个解决方案，你仍然需要通过蛮力来验证这个解决方案是唯一的。如果不这样做，你可能会生成具有多个解决方案的益智游戏，而这些解决方案被大多数玩家声明为无效。

拒绝你的方法不能解决的有效难题是不太重要的，因为没有人会注意到它们(只要你不让用户输入他们自己的难题)。