多数独AI方法 [英] Multi-Sudoku AI approach
问题描述
我正在为名为 multi-sudoku 的 sudoku 的变体概念化，其中多个板像这样重叠:
I'm conceptualizing a solver for a variant of sudoku called multi-sudoku, where multiple boards overlap like so:
如果我对游戏的理解正确，则必须以使任何两个或多个网格之间的重叠成为每个网格解决方案的一部分的方式来解决每个网格.
If I understand the game correctly, you must solve each grid in such a way that the overlap between any two or more grids is part of the solution for each.
我不确定应该如何考虑.有人有任何提示/概念线索吗?此外，如果您想到了人工智能方面的任何话题，我也想听听.
I'm unsure as to how I should be thinking about this. Anybody got any hints/conceptual clues? Additionally, if any topics in artificial intelligence come to mind, I'd like to hear those too.
推荐答案
约束编程(CP)
Sudoku是一个典型的约束编程问题.您有一组变量(网格中的字段)，每个变量都有一个 domain (此处是数字0至9)和一组约束(这些数字在行，列，块...中仅出现一次).
Constraint programming (CP)
Sudoku is a typical constraint programming problem. You have a set of variables (the fields in the grid) each with a domain (here the digits 0 to 9) and a set of constraints over these variables (the fact that a number occurs only once in a row, column, block,...).
解决约束编程问题的通用方法是电弧一致性(AC):您传播约束.通过(部分)填充的变量，可以减少其余变量的域，等等.最后，如果传播不再可以使域变小，则必须做出 choice .
A generic way to solve constraint programming problems is arc consistency (AC): you propagate constraints. By variables that are (partly) filled in, you can reduce the domain of the remaining variables, etc. Finally if propagation no longer can make the domains smaller, you have to make a choice.
通过选择，您可以为某个变量选择一个值.一个好的策略是选择一个剩余少量可能值的变量.接下来，您将再次传播，并可能做出其他选择，依此类推.
With a choice, you select a value for a certain variable. A good strategy is to select a variable with a small amount of possible values left. Next you propagate again and possibly make another choice and so on.
您的程序有可能发现选择错误:它使一个或多个变量的域为空.在这种情况下，您回溯:撤消您之前做出的选择(以及选择之后的传播)，然后选择另一个值.
It is possible that your program finds out that a choice was wrong: it makes the domain of one or more variables empty. In that case, you backtrack: you undo a choice you've made earlier (as well as the propagation that was done after that choice) and pick another value.
显然，该答案并非旨在提供对该主题的深入概述，但是维基百科页面可以提供更好的概述和指向更多信息的指针.
This answer evidently does not aim to provide an in-depth overview of the topic, but the Wikipedia page can give a better overview and pointers to more information.
有约束编程求解器，例如 ECLiPSe (不是IDE)， MiniZinc 等，在其中可以简单地定义变量，域和约束条件.
There are constraint programming solvers like ECLiPSe (not the IDE), MiniZinc, etc. where one can simply define the variables, domains and constraints.
在ECLiPSe网站上，您可以找到 sudoku的模型.阅读了有关ECLiPSe的一些文档后，您可以将此文件转换为多数独的模型.我进行了一些小的修改，得到以下 quick-and-dirty 解决方案:
On the ECLiPSe website, you can find a model for sudoku. Given you read some documentation about ECLiPSe, you can turn this file into a model for multi-sudoku. I've made some small modifications resulting in the following quick-and-dirty solution:
% 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, _, _, _, _)
)
).
我从约阿希姆·辛普(Joachim Schimpf)借用"了数独的模型，因此功劳他.此外，请注意，此答案不建议在其他工具上使用 ECLiPSe .在约束编程方面，我只是更熟悉Prolog工具链.但是，如果您更喜欢C ++， Gecode 将以大约相同(甚至更好)的性能来达到目的.
I "borrowed" the model of the sudoku from Joachim Schimpf, so credits to him. Furthermore note that this answer does not advice to use ECLiPSe over another tool. I'm simply more familiar with the Prolog toolchain when it comes to constraint programming. But if you are more into C++, Gecode will do the trick with approximately the same (or even better) performance.
生成输出:
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种有效的解决方案.
It took my machine approximately 0.11 seconds. Furthermore there are 60 valid solutions in total.
最后两个矩阵"显示了两个数独的解决方案.如您所见(我还没有完全检查过)，它们共享一个块(相同的输出)，并且所有数独约束都有效.下面显示了该解决方案的一个更方便的表示形式:
The last two "matrices" show the solution for the two Sudoku's. As you can see (I haven't checked it fully), they share a block (the same output), and all sudoku constraints are valid. A more convenient representation of the solution is shown below:
+-----+-----+-----+
|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中的约束编程库，也不了解Python的 ECLiPSe 端口.但是我的经验是，所有现代编程语言都具有这种工具.
I don't know about a constraint programming library in Python, nor do I know of a port of ECLiPSe to Python. But my experience is that all modern programming languages have such tool.
使用约束编程工具(例如 ECLiPSe ， Gecode ，...)的优势首先，您只需要指定您的问题，如何解决是您无需担心的事情.此外，此类库在约束编程方面进行了30年的研究:它们经过了极大的优化，以大多数人无法想象的方式利用约束和结构，并且包含错误的可能性也比定制算法要小.此外，如果找到新的策略，算法等，则 ECLiPSe 的更新将导致模型的处理更快.
The advantage of using a constraint programming tool like ECLiPSe, Gecode,... is first of all that you only have to specify your problem, how it is solved is something you don't have to worry. Furthermore such libraries implement 30 years of research into constraint programming: they are extremely optimized, exploit constraints and structures in a way most people cannot imagine and are less likely to contain bugs (than a custom made algorithm). Furthermore if new strategies, algorithms,... are found, an update of ECLiPSe will result in faster processing of the model.
一个缺点是，使用约束编程仍无法解决一些难题:搜索空间太大，约束非常复杂，无法将域缩小为小集合，并且没有足够的处理能力来做出足够的选择来找到有效的解决方案.另一个缺点是，指定问题并不总是那么容易:尽管程序员旨在设计好的约束，但总会存在复杂的问题，没有为之定义易于使用的约束.
A disadvantage is that some hard problems can still not be solved using constraint programming: the search space is simply too large, the constraints are that complex that the domains are not reduced to small sets, and there is not enough processing power to make enough choices in order to find a valid solution. Another disadvantage is that it is not always easy to specify a problem: although programmers aim to design good constraints, there are always complex problems where there are no easy-to-use constraints defined for.
很显然，还有其他AI技术可以解决问题. 进化计算是一种通常用于解决难题和优化问题的技术:首先填充数独以允许某些值错误，然后在每个步骤修复一个或多个问题.领域.有时他们会引入新的错误，以便最终找到有效的解决方案.
Evidently there are other AI techniques to solve problems. A technique that is commonly used to tackle hard search and optimization problems is evolutionary computing: one starts by filling in the sudoku allowing some values to be wrong, then at each time step they aim to fix one or more fields. Sometimes they introduce new errors in order to find a valid solution eventually.
这篇关于多数独AI方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
