在数独游戏中的所有博客帖子，你必须在一个9x9的网格中填写数字1到9，这个网格也被分成3x3个方框。每行、每列和每框必须包含每个数字恰好一次。游戏开始时网格中有许多给定的数字，玩家可以使用多种技术来推断丢失的数字。
简单的变体通常可以通过简单的消除来完成，也就是说，除了一个候选之外，所有候选都会从单元格中删除，因为列、行或框中已经包含了该列、行或框。但是，难度较大的变体需要使用更复杂的技术，即通过多个步骤从单元格中消除候选对象。
编程数独解算器并不是很困难。尽管数独已知是NP-完全的，因为9x9数独中的n相当小，但暴力强制求解可以在几秒钟内完成。更有趣的任务是编写一个类似人类的数独解算器，它使用人类可能的技术来识别下一步。在这篇文章中，我们将讨论一种可以使用相当优雅的图形算法实现的技术。
考虑下面一行数独游戏。完成的单元格包含一个很大的数字。其他单元格包含其余候选数字较小的数字。
该行的单元格1和3只能包含数字1和9。两种可能的解决方案是：
由此我们可以推断，数字1和9永远不会出现在此行的任何其他单元格中。这意味着我们可以从单元格7和8中删除候选的1和9。从现在开始，我们将把元组标记为青色，而可能删除的单元格则标记为紫色。
消除之后，19元组仍然在那里，但是它不再有用了，因为我们不能推断出更多的消除。
这项技术并不局限于配对。下图显示了4789四元组(青色)。因此，可以从单元格1和3(紫色)中消除候选7和9。
元组是大小为n的行、列或框中的单元格的子集，它恰好包含n个不同的候选。
在具有元组T的行、列或框中，可以从T外的单元格中消除T内的所有候选。
此外，我们定义如果T与T之外的单元格共享任何候选，则元组T是有用的。
让我们考虑一个朴素的算法来寻找具有n个不同候选者的大小为n的元组。我们必须考虑具有所有可能的候选组合的所有大小的元组：
对于2和8//1和9之间的每个行、列、框的每个大小n//1和9不要对数字1到9的每个子集有意义，每个数字的大小为n…。
很容易看出，我们的实现必须涉及很多嵌套循环。这本身并不是问题，但我发现很难想象它，因此它不是我直接写下来的。相反，让我们从不同的角度来看这个问题。
考虑一个无向图，其中的顶点是行、列或框的单元格(没有填充解答)。对于每两个共享候选人的单元格，我们将添加一条边。让我们看一下第一个可视化为图表的示例：
组件是所有顶点直接或间接连接的子图。如果您从任何单元格开始，您都可以使用广度优先或深度优先搜索来构建组件。
我们可以看到元组必须是组件的一部分，因为它们需要共享候选项1。但是我们如何判断元组是否有用呢？让我们问相反的问题：什么时候一个元组是没有用的？如果它不与另一个单元格共享任何候选项，那么元组就一定是整个组件。下面是一个例子：
但是，如果元组是更大组件的一部分，那么它一定是有用的，即有可以消除的候选者。在我们的原始示例中，元组帮助我们从其余组件中删除1和9。
让我们再看一个例子。我们可以看到，4789四元组允许我们从紫色顶点中去掉9，因为它们是组件的一部分。
有了这些知识，我发现写下算法相对容易。下面是它可能的样子：
对于每行、列、框C，设g是一个图，其中C中的单元格是每个单元格c1的顶点，g中的每个单元格c2的顶点。如果c1和c2共享候选对象，而g不为空，则让comp为comp的每个子集s中的任意组件，如果s的大小==s中不同的候选数和s<的大小；则comp的大小返回s；从g中删除comp中的所有顶点。
您可以在sudoku-solver.rakhman.info找到我自己在Github和Runnable应用程序上实现的算法。
1从技术上讲，我们可以构造不相连的伪元组，其中每个单元格只有一个候选者，但然后我们可以立即将数字输入到该单元格中。
所有博客帖子