多数独 AI 方法
Multi-Sudoku AI approach
我正在为 sudoku 的变体概念化求解器，称为 multi-sudoku，其中多个板重叠如下：
如果我对游戏的理解是正确的，你必须以这样的方式解决每个网格，即任何两个或多个网格之间的重叠是每个网格的解决方案的一部分。
我不确定我应该如何考虑这个问题。有人有任何 hints/conceptual 线索吗？此外，如果我想到人工智能方面的任何话题，我也想听听。
约束规划（CP）
数独是典型的约束规划问题。您有一组 变量（网格中的字段），每个变量都有一个 域（这里是数字 0 到 9) 以及对这些变量的一组 约束 （一个数字在一行、列、块中只出现一次的事实，...）。
解决约束规划问题的通用方法是弧一致性（AC）：传播约束。通过（部分）填充的变量，您可以减少剩余变量的域等。最后，如果传播不再可以使域变小，您必须做出选择。
通过选择，您 select 某个 变量的值 。一个好的策略是 select 一个只剩下少量可能值的变量。接下来你再次传播并可能做出另一个选择等等。
您的程序可能发现一个选择是错误的：它使一个或多个变量的域为空。在这种情况下，您 回溯：您撤消之前所做的选择（以及在该选择之后进行的传播）并选择另一个值。
这个答案显然不是为了提供对该主题的深入概述，但 Wikipedia page 可以提供更好的概述和指向更多信息的指针。
有约束规划求解器，如ECLiPSe（不是IDE），MiniZinc, 等等，其中可以简单地定义变量、域和约束。
使用 ECLiPSe 解决问题
在 ECLiPSe 网站上，您可以找到 a model for sudoku。如果您阅读了一些关于 ECLiPSe 的文档，您可以将此文件转换为多数独模型。我做了一些小的修改，得到了以下 快速而简单的 解决方案：
% credits to Joachim Schimpf for his model of sudoku
% 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.
%----------------------------------------------------------------------
% Sample data
%----------------------------------------------------------------------
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, _, _, _, _)
)
).
我 "borrowed" 来自 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-clp
GMP library copyright Free Software Foundation, see legal/lgpl.txt
For other libraries see their individual copyright notices
Version 6.1 #199 (x86_64_linux), Sun Mar 22 09:34 2015
[eclipse 1]: solve(1).
lists.eco loaded in 0.00 seconds
WARNING: module 'ic_global' does not exist, loading library...
queues.eco loaded in 0.00 seconds
ordset.eco loaded in 0.01 seconds
heap_array.eco loaded in 0.00 seconds
graph_algorithms.eco loaded in 0.03 seconds
max_flow.eco loaded in 0.00 seconds
flow_constraints_support.eco loaded in 0.00 seconds
ic_sequence.eco loaded in 0.01 seconds
ic_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 个有效解决方案。
最后两个 "matrices" 显示了两个数独的解决方案。如您所见（我还没有完全检查），它们共享一个块（相同的输出），并且所有数独约束都有效。更方便的解决方案表示如下所示：
+-----+-----+-----+
|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 将加快模型处理速度。
一个缺点是一些难题仍然不能使用约束规划来解决：搜索space实在是太大了，约束太复杂了域没有减少到小集，并且没有足够的处理能力来做出足够的 选择 来找到有效的解决方案。另一个缺点是，指定一个问题并不总是那么容易：尽管程序员的目标是设计好的约束，但总是有复杂的问题没有定义易于使用的约束。
其他技巧
显然还有其他人工智能技术可以解决问题。 进化计算 是一种常用于解决硬搜索和优化问题的技术：首先填写数独，允许某些值是错误的，然后在每个时间步他们都旨在修复一个或多个字段。有时他们会引入新的错误，以便最终找到有效的解决方案。
另一种方法是使用遗传算法。这是基于生物进化。遗传算法是进化算法的一部分，因此具有类比 "fitness-function"。通过重组、选择和变异找到有效的解决方案。
基本概念是随机初始化若干解"individuals"，由"chromosomes"组成（解当然可以是错误的）。定义一个 "fitness-function" 来评估当前 "generation" 中每个个体的质量。以更高的概率将具有更好适应性的个体重新组合成 "child" 解决方案，并以低概率变异新一代中的一些个体。重复直到某些标准 (max_iteration_count, valid_solution_found) 为真。
使遗传算法适合您的问题。您可以执行以下操作。为每个 3x3 或 9x9 数独创建一个本地正确解决方案。这些是染色体。将它们放在一个数据结构中。那是个人。创建一堆它们以形成一代。通过其违反的约束来评估每个人。计算相应的概率。重新组合个体，改变一些染色体，重复。
您可以将其视为局部优化和全局优化的结合。因为你需要某种贪心算法（或者任何你想用来解决局部数独的算法）来找到局部，而 GA 来找到整体全局最优。我认为仅使用 GA 并尝试解决此问题是没有意义的。我最近在一个组合问题上实施了 GA，在没有进行局部优化的情况下，结果在大多数情况下都非常糟糕。
虽然 GA 的好处在于，它们在搜索开始时迈出了很大的一步，向最优收敛，但仍然覆盖了大部分搜索 space。但与 EA 一样，调整参数可能非常棘手。
我正在为 sudoku 的变体概念化求解器，称为 multi-sudoku，其中多个板重叠如下：
如果我对游戏的理解是正确的，你必须以这样的方式解决每个网格，即任何两个或多个网格之间的重叠是每个网格的解决方案的一部分。
我不确定我应该如何考虑这个问题。有人有任何 hints/conceptual 线索吗？此外，如果我想到人工智能方面的任何话题，我也想听听。
约束规划（CP）
数独是典型的约束规划问题。您有一组 变量（网格中的字段），每个变量都有一个 域（这里是数字 0 到 9) 以及对这些变量的一组 约束 （一个数字在一行、列、块中只出现一次的事实，...）。
解决约束规划问题的通用方法是弧一致性（AC）：传播约束。通过（部分）填充的变量，您可以减少剩余变量的域等。最后，如果传播不再可以使域变小，您必须做出选择。
通过选择，您 select 某个 变量的值 。一个好的策略是 select 一个只剩下少量可能值的变量。接下来你再次传播并可能做出另一个选择等等。
您的程序可能发现一个选择是错误的：它使一个或多个变量的域为空。在这种情况下，您 回溯：您撤消之前所做的选择（以及在该选择之后进行的传播）并选择另一个值。
这个答案显然不是为了提供对该主题的深入概述，但 Wikipedia page 可以提供更好的概述和指向更多信息的指针。
有约束规划求解器，如ECLiPSe（不是IDE），MiniZinc, 等等，其中可以简单地定义变量、域和约束。
使用 ECLiPSe 解决问题
在 ECLiPSe 网站上，您可以找到 a model for sudoku。如果您阅读了一些关于 ECLiPSe 的文档，您可以将此文件转换为多数独模型。我做了一些小的修改，得到了以下 快速而简单的 解决方案：
% credits to Joachim Schimpf for his model of sudoku
% 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.
%----------------------------------------------------------------------
% Sample data
%----------------------------------------------------------------------
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, _, _, _, _)
)
).
我 "borrowed" 来自 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-clp
GMP library copyright Free Software Foundation, see legal/lgpl.txt
For other libraries see their individual copyright notices
Version 6.1 #199 (x86_64_linux), Sun Mar 22 09:34 2015
[eclipse 1]: solve(1).
lists.eco loaded in 0.00 seconds
WARNING: module 'ic_global' does not exist, loading library...
queues.eco loaded in 0.00 seconds
ordset.eco loaded in 0.01 seconds
heap_array.eco loaded in 0.00 seconds
graph_algorithms.eco loaded in 0.03 seconds
max_flow.eco loaded in 0.00 seconds
flow_constraints_support.eco loaded in 0.00 seconds
ic_sequence.eco loaded in 0.01 seconds
ic_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 个有效解决方案。
最后两个 "matrices" 显示了两个数独的解决方案。如您所见（我还没有完全检查），它们共享一个块（相同的输出），并且所有数独约束都有效。更方便的解决方案表示如下所示：
+-----+-----+-----+
|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 将加快模型处理速度。
一个缺点是一些难题仍然不能使用约束规划来解决：搜索space实在是太大了，约束太复杂了域没有减少到小集，并且没有足够的处理能力来做出足够的 选择 来找到有效的解决方案。另一个缺点是，指定一个问题并不总是那么容易：尽管程序员的目标是设计好的约束，但总是有复杂的问题没有定义易于使用的约束。
其他技巧
显然还有其他人工智能技术可以解决问题。 进化计算 是一种常用于解决硬搜索和优化问题的技术：首先填写数独，允许某些值是错误的，然后在每个时间步他们都旨在修复一个或多个字段。有时他们会引入新的错误，以便最终找到有效的解决方案。
另一种方法是使用遗传算法。这是基于生物进化。遗传算法是进化算法的一部分，因此具有类比 "fitness-function"。通过重组、选择和变异找到有效的解决方案。
基本概念是随机初始化若干解"individuals"，由"chromosomes"组成（解当然可以是错误的）。定义一个 "fitness-function" 来评估当前 "generation" 中每个个体的质量。以更高的概率将具有更好适应性的个体重新组合成 "child" 解决方案，并以低概率变异新一代中的一些个体。重复直到某些标准 (max_iteration_count, valid_solution_found) 为真。
使遗传算法适合您的问题。您可以执行以下操作。为每个 3x3 或 9x9 数独创建一个本地正确解决方案。这些是染色体。将它们放在一个数据结构中。那是个人。创建一堆它们以形成一代。通过其违反的约束来评估每个人。计算相应的概率。重新组合个体，改变一些染色体，重复。
您可以将其视为局部优化和全局优化的结合。因为你需要某种贪心算法（或者任何你想用来解决局部数独的算法）来找到局部，而 GA 来找到整体全局最优。我认为仅使用 GA 并尝试解决此问题是没有意义的。我最近在一个组合问题上实施了 GA，在没有进行局部优化的情况下，结果在大多数情况下都非常糟糕。
虽然 GA 的好处在于，它们在搜索开始时迈出了很大的一步，向最优收敛，但仍然覆盖了大部分搜索 space。但与 EA 一样，调整参数可能非常棘手。