我正在构想一种解决名为“多重数独”的数独变体的求解器，其中的多个棋盘像这样重叠：

如果我理解这款游戏正确的话，你必须以这样的方式解决每个棋盘，使得任何两个或多个棋盘之间的重叠部分都是每个棋盘解的一部分。

我不知道该如何思考这个问题。有人有任何提示/概念线索吗？此外，如果想到任何与人工智能相关的主题，我也想听听那些内容。

回答：

约束编程（CP）

数独是一个典型的约束编程问题。你有一组变量（棋盘中的字段），每个变量都有一个域（这里是数字0到9），以及一组这些变量上的约束（一个数字在某一行、列、块中只出现一次的事实）。

解决约束编程问题的通用方法是弧一致性（AC）：你传播约束。通过已经（部分）填充的变量，你可以缩小剩余变量的域，等等。最后，如果传播不再能使域变小，你就必须做出选择。

在选择中，你为某个变量选择一个值。一个好的策略是选择一个可能值较少的变量。接下来你再次传播，并可能做出另一个选择，依此类推。

有可能你的程序会发现一个选择是错误的：它使一个或多个变量的域变空。在这种情况下，你会回溯：你撤销之前做出的一个选择（以及在此选择之后进行的传播），并选择另一个值。

显然，这个回答并不旨在提供该主题的深入概述，但维基百科页面可以提供更好的概述和指向更多信息的指针。

有像ECLiPSe（不是IDE）、MiniZinc等约束编程求解器，人们可以在其中简单地定义变量、域和约束。

使用ECLiPSe解决问题

在ECLiPSe网站上，你可以找到数独的模型。如果你阅读了一些关于ECLiPSe的文档，你可以将这个文件转换为多重数独的模型。我做了一些小的修改，得到以下快速而粗糙的解决方案：

% 感谢Joachim Schimpf的数独模型% http://eclipseclp.org/examples/sudoku.ecl.txt:- lib(ic).:- import alldifferent/1 from ic_global.solve(ProblemName) :-    problem(ProblemName,BA,BB),    multi_sudoku(3,BA,BB),    print_board(BA),    print_board(BB).multi_sudoku(N,BA,BB) :-    sudoku(N,BA,VA),    sudoku(N,BB,VB),    N2 is N*N,    Inc is N2-N,    (multifor([I,J],1,N,1),param(BA,BB,Inc) do        BA[I+Inc,J+Inc] #= BB[I,J]    ),    append(VA,VB,Vars),    labeling(Vars).sudoku(N,Board,Vars) :-    N2 is N*N,    dim(Board,[N2,N2]),    Board[1..N2,1..N2] :: 1..N2,    ( for(I,1,N2), param(Board,N2) do        Row is Board[I,1..N2],        alldifferent(Row),        Col is Board[1..N2,I],        alldifferent(Col)    ),    ( multifor([I,J],1,N2,N), param(Board,N) do        ( multifor([K,L],0,N-1), param(Board,I,J), foreach(X,SubSquare) do        X is Board[I+K,J+L]        ),        alldifferent(SubSquare)    ),    term_variables(Board, Vars).print_board(Board) :-    dim(Board, [N,N]),    ( for(I,1,N), param(Board,N) do        ( for(J,1,N), param(Board,I) do            X is Board[I,J],        ( var(X) -> write("  _") ; printf(" %2d", [X]) )        ), nl    ), nl.%----------------------------------------------------------------------% 样本数据%----------------------------------------------------------------------problem(1, [](    [](_, _, _, _, 6, _, _, _, _),    [](_, _, _, 4, _, 9, _, _, _),    [](_, _, 9, 7, _, 5, 1, _, _),    [](_, 5, 2, _, 7, _, 8, 9, _),    [](9, _, _, 5, _, 2, _, _, 4),    [](_, 8, 3, _, 4, _, 7, 2, _),    [](_, _, _, 2, _, 8, _, _, _),    [](_, _, _, 6, _, 4, _, _, _),    [](_, _, _, _, 5, _, _, _, _)           ),           [](    [](_, _, _, _, 3, _, _, _, _),    [](_, _, _, 8, _, 7, _, _, _),    [](_, _, _, 1, _, 6, 3, _, _),    [](_, 9, 8, _, _, _, 1, 2, _),    [](2, _, _, _, _, _, _, _, 3),    [](_, 4, 3, _, _, _, 6, 5, _),    [](_, _, 7, 3, _, 5, 9, _, _),    [](_, _, _, 4, _, 2, _, _, _),    [](_, _, _, _, 6, _, _, _, _)           )    ).

我“借用了”Joachim Schimpf的数独模型，所以感谢他。此外请注意，这个回答并不建议使用ECLiPSe而不是其他工具。我只是在约束编程方面更熟悉Prolog工具链。但如果你更喜欢C++，Gecode也能以大致相同（甚至更好）的性能完成任务。

这会生成以下输出：

ECLiPSe Constraint Logic Programming System [kernel]Kernel and basic libraries copyright Cisco Systems, Inc.and subject to the Cisco-style Mozilla Public Licence 1.1(see legal/cmpl.txt or http://eclipseclp.org/licence)Source available at www.sourceforge.org/projects/eclipse-clpGMP library copyright Free Software Foundation, see legal/lgpl.txtFor other libraries see their individual copyright noticesVersion 6.1 #199 (x86_64_linux), Sun Mar 22 09:34 2015[eclipse 1]: solve(1).lists.eco  loaded in 0.00 secondsWARNING: module 'ic_global' does not exist, loading library...queues.eco loaded in 0.00 secondsordset.eco loaded in 0.01 secondsheap_array.eco loaded in 0.00 secondsgraph_algorithms.eco loaded in 0.03 secondsmax_flow.eco loaded in 0.00 secondsflow_constraints_support.eco loaded in 0.00 secondsic_sequence.eco loaded in 0.01 secondsic_global.eco loaded in 0.07 seconds  2  1  4  8  6  3  9  5  7  8  7  5  4  1  9  2  6  3  6  3  9  7  2  5  1  4  8  4  5  2  3  7  1  8  9  6  9  6  7  5  8  2  3  1  4  1  8  3  9  4  6  7  2  5  5  4  1  2  3  8  6  7  9  7  2  8  6  9  4  5  3  1  3  9  6  1  5  7  4  8  2  6  7  9  5  3  4  2  8  1  5  3  1  8  2  7  4  6  9  4  8  2  1  9  6  3  7  5  7  9  8  6  5  3  1  2  4  2  6  5  7  4  1  8  9  3  1  4  3  2  8  9  6  5  7  8  2  7  3  1  5  9  4  6  9  1  6  4  7  2  5  3  8  3  5  4  9  6  8  7  1  2

我的机器大约用了0.11秒。此外，总共有60个有效解。

最后两个“矩阵”显示了两个数独的解。如你所见（我没有完全检查），它们共享一个块（相同的输出），并且所有数独约束都是有效的。下面展示了解决方案的更方便的表示：

+-----+-----+-----+|2 1 4|8 6 3|9 5 7||8 7 5|4 1 9|2 6 3||6 3 9|7 2 5|1 4 8|+-----+-----+-----+|4 5 2|3 7 1|8 9 6||9 6 7|5 8 2|3 1 4||1 8 3|9 4 6|7 2 5|+-----+-----+-----+-----+-----+|5 4 1|2 3 8|6 7 9|5 3 4|2 8 1||7 2 8|6 9 4|5 3 1|8 2 7|4 6 9||3 9 6|1 5 7|4 8 2|1 9 6|3 7 5|+-----+-----+-----+-----+-----+            |7 9 8|6 5 3|1 2 4|            |2 6 5|7 4 1|8 9 3|            |1 4 3|2 8 9|6 5 7|            +-----+-----+-----+            |8 2 7|3 1 5|9 4 6|            |9 1 6|4 7 2|5 3 8|            |3 5 4|9 6 8|7 1 2|            +-----+-----+-----+

我不知道Python中有没有约束编程库，也不清楚是否有将ECLiPSe移植到Python的版本。但我的经验是，所有现代编程语言都有这样的工具。

使用像ECLiPSe、Gecode这样的约束编程工具的优势首先在于你只需要指定你的问题，如何解决这个问题是你不需要担心的。此外，这些库实现了30年的约束编程研究：它们极度优化，利用约束和结构的方式是大多数人无法想象的，并且不太可能包含错误（比起自定义算法）。此外，如果发现新的策略、算法等，更新ECLiPSe将导致模型处理速度更快。

一个劣势是有些难题仍然无法通过约束编程解决：搜索空间太大，约束太复杂以至于域无法缩小到小集合，并且没有足够的处理能力来做出足够的选择以找到有效解。另一个劣势是指定问题并不总是容易的：尽管程序员旨在设计好的约束，但总有一些复杂的问题，无法定义易于使用的约束。

其他技术

显然，还有其他的人工智能技术来解决问题。一种常用于处理困难的搜索和优化问题的技术是进化计算：人们从填充数独开始，允许一些值是错误的，然后在每个时间步长中，他们旨在修正一个或多个字段。有时他们会引入新的错误，以便最终找到有效的解。