我正在构思一个名为multi-sudoku的数独变种的解算器,其中多个板重叠如下:
如果我正确理解游戏,您必须以这样的方式解决每个网格,即任何两个或更多网格之间的重叠是每个网格解决方案的一部分.
我不确定我应该怎么想这个.任何人都有任何提示/概念线索?此外,如果想到人工智能中的任何主题,我也想听听.
数独是一个典型的约束编程问题.你有一组变量(在网格中的字段)每一个域(这里的数字0
来9
)和一组约束了这些变量(一个号码的行,列,块只发生一次的事实,.. ).
解决约束编程问题的一般方法是弧一致性(AC):传播约束.通过(部分)填充的变量,您可以减少剩余变量的域等.最后,如果传播不再能使域变小,则必须做出选择.
通过选择,您可以为特定变量选择一个值.一个好的策略是选择一个剩下少量可能值的变量.接下来,您再次传播并可能做出另一个选择,依此类推.
您的程序可能会发现选择错误:它会使一个或多个变量的域为空.在这种情况下,您回溯:撤消之前做出的选择(以及在该选择之后完成的传播)并选择另一个值.
这个答案显然不是为了提供对该主题的深入概述,但维基百科页面可以提供更好的概述和更多信息的指示.
有一些约束编程求解器,如ECLiPSe(不是IDE),MiniZinc等,可以简单地定义变量,域和约束.
用ECLiPSe解决问题在ECLiPSe网站上,您可以找到数独模型.鉴于您阅读了有关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, _, _, _, _) ) ).
我从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个有效的解决方案.
最后两个"矩阵"显示了两个数独游戏的解决方案.正如您所看到的(我没有完全检查过),它们共享一个块(相同的输出),并且所有数独约束都是有效的.更方便的解决方案表示如下:
+-----+-----+-----+ |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 的端口.但我的经验是,所有现代编程语言都有这样的工具.
该优势利用约束编程工具一样的日食,Gecode,......首先是,你只需要的指定你的问题,它是如何解决的是你不必担心.此外,这些库对约束编程进行了30年的研究:它们经过极大优化,以大多数人无法想象的方式利用约束和结构,并且不太可能包含错误(比定制算法).此外,如果找到新的策略,算法......,ECLiPSe的更新将导致更快的模型处理.
一个缺点是,一些困难问题仍然不能使用约束规划解决:搜索空间实在太大,约束是复杂的域不减少到小套,并没有足够的处理能力,使足够的选择为了找到有效的解决方案.另一个缺点是指定问题并不总是容易的:尽管程序员的目标是设计好的约束,但是总是存在复杂的问题,其中没有定义易于使用的约束.
其他技术显然,还有其他AI技术可以解决问题.通常用于解决硬搜索和优化问题的技术是进化计算:首先填充数据允许某些值是错误的,然后在每个时间步骤他们的目标是修复一个或多个字段.有时他们会引入新的错误,以便最终找到有效的解决方案.