用算法X解决数独

在本文中，我们考虑了Knuth的“算法X”及其在解决数独中的应用。 该算法的优点在于Sudoku无需编程任何高级求解技术即可快速求解。

实际上，这一切都是从Euler项目的任务开始的，为了得到答案，您需要解决50个数独。 似乎他通过编写一个用于解决一个相当愚蠢的搜索的程序而收到了答案，但是不知何故，它对解决方案的速度有些不满意。 在了解了普通人如何解决数独之后，我发现由Donald Knut发明的Algorithm X正在用于此目的。

算法X

该算法解决了准确覆盖集合的问题。 或者，如果您愿意，它会收集一个“离散难题”，其中包含有关可用零件形状的信息。 更正式地：

• 有很多
• 该集合有一组子集Y
• 任务是从Y中选择此类元素Y * ，使S中的每个元素仅包含在Y *中包含的一组元素中
• 也就是说， Y *中所有集合的并集构成（覆盖）集合S ，同时Y *中没有成对相交的集合

例如，考虑集合
S = {1,2,3,4,5}并且
Y = { A = {1，2}，
B = {2，3}，
C = {1，5}，
D = {1，4}，
E = {5}}
集合B ， D和E形成了集合S的精确覆盖。

对于X Knuth算法，集合Y表示为二进制矩阵，其中行对应于元素Y ，如果S _j在Y _i中 ，则A _i，j = 1。 即 对于上面的示例：

确切的覆盖率搜索算法如下：

• 输入数据：设置S和Y ； Stack可能包含在coverage中Stack组Stack （可能最初是空的或已经有一些元素）
  
  1. 如果套件S为空，则所需的封面在纸叠上。
  2. 如果集合Y为空，则找不到覆盖物。
  3. 我们正在寻找集合S中包含在Y的最小集合数中的元素s 。
  4. 从Y中选择所有包含s的 X行。
  5. 对于每组X，重复6-9。
  6. 将X添加到堆栈中作为潜在的coverage元素。
  7. 我们形成集合S'和Y' ： S'是S ，从中删除X中包含的所有元素， Y'是Y中不与X相交的集合。
  8. 我们称S ， Y和Stack为算法X。
  9. 如果在步骤7中发现不可能覆盖，请从Stack顶部移除该元素，然后继续执行下一个X。 如果找到解决方案，我们将其返回。
  10. 如果没有任何X的解，则此输入的任务不解决。

通常，没有什么特别复杂的。 本质上-深入进行常规搜索。 顺便说一句，我们注意到，如果您最初将堆栈设置为非空的，则问题可以表述为“找到包含已经位于堆栈上的元素的确切覆盖范围”。

精妙之处在于，实际上，该算法用于解决Y中的集合“较小”（即 矩阵非常稀疏，因此，例如，在标准存储期间以矩阵形式搜索列之间的交点会花费不可接受的长时间。
因此，Knut 通过“跳舞链接”机制对该算法进行了补充。 矩阵以二维双向链接列表的形式表示：列表中的每一行仅存储列号，该行包含单位。 该列表还包含指向行和列中的下一个和上一个元素的链接。 与组织为二维数组的O （ m * n ）相比，该组织允许您在O （1）时间内从稀疏矩阵中删除列和行。

有趣的是，Ali Assaf提供了一种使用关联列表的跳舞链接机制的替代方法 ，该方法使您可以使用高级语言从字面上的几十行实现X算法。

想法是将列和矩阵行都存储在关联列表中。 在列中，我们在行中分别存储有行索引，行与行之间有非零元素，列索引分别是行。 而且，我们将有序地将索引存储在行中，在数组中，我们注意到，在Knuth的算法中，基本上没有必要修改行，因此不需要为从行中快速删除元素而进行的优化。 但是列将以集合的形式设置，因为 从矩阵中删除行时，必须从所有列中删除其标识符（从所有列中删除时，该行将“自身”消失）。

考虑在Julia上实现该算法。
示例中的矩阵现在如下所示：

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) ) 

为了使算法起作用，您需要一个函数，该函数从与给定相交的矩阵中取出直线，并将该直线返回其位置的函数。

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end 

为了使这两个功能按其应有的作用，只需将元素顺序存储在矩阵的行中即可。 在extract_intersects!()函数中，在外循环的每次迭代中，与base_row相交但不包含在先前迭代中查看的元素的那些行将从矩阵中删除。 这样可以确保在将列插入restore_intersects!()以相反的顺序，在调用push!(columns[col], added_row)时最内层的循环中push!(columns[col], added_row)这些columns[col]列将已经返回到矩阵中，并且在extract_intersects!()列中extract_intersects!()元素将返回其原始位置。

现在算法X本身：

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end 

数独

有一种算法，问题很小-将Sudoku呈现为寻找确切覆盖范围的任务。

我们制定了数独必须满足的要求：

1. 在每个像元中，有一个1到9的数字（如果求解不同大小的平方，则为n ² ）。
2. 在每一行中，每个数字出现一次。
3. 在每一列中，每个数字出现一次。
4. 在每个象限中，每个数字出现一次。

这些要求中的每一项都必须准确地满足1次，即 它们构成了需要涵盖的范围。 它恰好具有4 n ^2个元素（矩阵中的列）。

我们考虑的子集是通过在特定单元格中替换特定数字而形成的。 例如，在1行和4列相交处的数字9“覆盖”一个子集“在单元格（1,4）中是一个数字，在1行中有一个数字9，在4列中有一个数字9，在2个象限中有一个数字9”（这意味着通常数独9×9）。

之后，简单地编写求解算法。

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end 

让我们来看一些例子：

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7 

似乎可行，并且速度可以接受。

应该注意的是，除了期望的集合和覆盖元素的特定表示之外，算法中没有规定任何专门针对Sudoku的技术（例如， 此处或此处 ）。