数独的proku花了太长时间来解决

Question

我想知道是否有一种很好的方法来使用prolog中的剪切符号来快速解决9x9数独
谜题.我正在解决这个难题而不使用!符号,但它
需要太长时间.
有什么建议？

Answer 1

没有看到代码,没有人能真正帮助你,但这里有一些你可能会觉得有用的通用建议.

Prolog程序通过搜索解决方案空间来工作.大多数情况下,您将遵循生成和测试范例.让我们对Prolog感兴趣的性感示例代码通常是因为产生的时间很少而性感且令人兴奋.实际上,Prolog的表现就像营销一样.产生更好的潜在客户比加快剩下的流程更有价值.这就是切割发挥作用的地方.

削减比你想象的少得多.只有当您知道您的第一个解决方案与其他解决方案一样好或更好时,它才有用.它承诺你的第一个猜测.

在像Sudoku这样的问题中,很容易天真地生成比你需要的更多的解决方案.如果您只是选择一个数字,那么您将为3x3网格生成9 ^ 9个潜在解决方案,但您已经知道类似[9,9,9,9,9,9,9,9,9]的序列对你没用.使用这种方法生成的大多数解决方案都将毫无价值.因此,要求[1,2,3,4,5,6,7,8,9]的排列要好得多,这要好三个数量级!但事实证明,使用数独游戏,您可以做得更好,因为在9的同一行中你不会想要超过一些9或1的数量.

从这个角度来看,应该清楚的是,"只是使用切割"的总体思路有点像给孩子一把手术刀或要求外科医生用一把刀来雕刻感恩节火鸡.它可能是一个很好的工具,但不是在错误的手中或错误的工作.为了对你有所帮助,你首先必须知道你正在产生潜在解决方案的顺序.如果你没有以正确的顺序生成它们,那将会对你造成伤害.这就像营销.你想要高素质的潜在客户,但是如果你把所有的钱都扔在错误的昂贵的线索上,你就会死在水里.

通常情况下,如果你追踪Prolog程序,你就会明白为什么浪费时间来低效地生成事物.如果你想到自己,"它应该已经放弃了!" 然后你就知道了切割的确切位置.你更有可能会想到"为什么你这么傻,在这之前尝试那个？" 如果你发现自己正在考虑这个问 返回并编写一个更智能的生成器,您的代码性能将大大提高.

一个来自我个人经历的轶事.朋友的儿子试图打败一些在线游戏.为此他必须解决一堆字谜.这对于冗长的词汇来说非常乏味.我写了一个使用WordNet作为数据库的Prolog程序.我会拿这些字母并置换它们,直到我在数据库中找到一个单词,然后我将它打印出来.它适用于小字,比如5个字母,但是7或8只是痛苦地缓慢.几年过去了,我突然意识到:我可以做一个索引.如果我只是取字典中的所有单词并对其字符进行排序,那么我可以使用字母字符,对它们进行排序,并查找与索引中的字符匹配的所有单词.构建索引需要时间,但与执行数十亿个排列相比并不多,而且我只需要执行一次以启用快速查找.最初的程序看起来更像我们梦想的Prolog和巫师可以写的,但是第二个使得有可能找到巨大单词的字谜并且不难读(尽管不那么"声明性").这个故事的寓意是,切割永远不会让我实现这种认识,也不会让我的算法表现得和这个一样好.算法质量仍然是最重要的.

Answer 2

考虑使用有限域约束.它们几乎适用于所有现代Prolog系统,并允许包含数独组合在内的许多组合问题的声明性公式.

如果使用有限域约束对此问题进行建模,则不需要任何问题!/0,仍然可以获得非常有效的解决方案.

来自SWI-Prolog的文档library(clpfd):

:- use_module(library(clpfd)).

sudoku(Rows) :-
        length(Rows, 9), maplist(length_(9), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [A,B,C,D,E,F,G,H,I],
        blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).

length_(L, Ls) :- length(Ls, L).

blocks([], [], []).
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
        all_distinct([A,B,C,D,E,F,G,H,I]),
        blocks(Bs1, Bs2, Bs3).

problem(1, [[_,_,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).

示例查询及其结果:

?- problem(1, Rows), sudoku(Rows), maplist(writeln, Rows).
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[2, 4, 6, 1, 7, 3, 9, 8, 5]
[3, 5, 1, 9, 2, 8, 7, 4, 6]
[1, 2, 8, 5, 3, 7, 6, 9, 4]
[6, 3, 4, 8, 9, 2, 1, 5, 7]
[7, 9, 5, 4, 6, 1, 8, 3, 2]
[5, 1, 9, 2, 8, 6, 4, 7, 3]
[4, 7, 2, 3, 1, 9, 5, 6, 8]
[8, 6, 3, 7, 4, 5, 2, 1, 9]