限制 Prolog 中的搜索 - Magic Square

我想用 Prolog 程序求解最完美幻方。

维基页面：https://en.wikipedia.org/wiki/Most-perfect_magic_square https://en.wikipedia.org/wiki/Most-perfect_magic_square

当我输入查询“magic_square(4, [[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4] ]）”。 （这是一个有效的幻方）我的程序返回 true。所以我认为我的规则基础是正确的。

不幸的是，如果超过 9 个值未知，则需要很长时间才能找到解决方案。

我需要帮助来限制我的搜索，以便程序在合理的时间内找到解决方案。理想情况下，它还应该适用于 12 x 12 网格（以及其他 4 的倍数）并且没有给出值：magic_square(12, Matrix)。

多谢！

这是我的代码：

:- use_module(library(clpfd)).

diag2_sum(0, _, _, _).
diag2_sum(I0, C1, Row1, Row3) :-
    I0 > 0,
    nth1(I0,Row1,A),
    (I0 =:= 2 -> I2 = 4 ; I2 is mod(I0 + 2,4)),
    nth1(I2,Row3,B),
    C1 =:= A + B,
    I1 is I0 - 1,
    diag2_sum(I1, C1, Row1, Row3).

diag_sum([_,_], _, _).
diag_sum([Row1|Tail], C1, N) :-
    nth1(2,Tail,Row3),
    diag2_sum(N, C1, Row1,Row3),
    diag_sum(Tail, C1, N).

square_sum_x(_, _, _, 0).
square_sum_x(Row1, Row2, C2, I0) :-
    (I0 =:= 3 -> I2 = 4 ; I2 is mod(I0 + 1,4)),
    nth1(I0,Row1,Elem1),
    nth1(I2,Row1,Elem2),
    nth1(I0,Row2,Elem3),
    nth1(I2,Row2,Elem4),
    C2 =:= Elem1 + Elem2 + Elem3 + Elem4,
    I1 is I0 - 1,
    square_sum_x(Row1, Row2, C2, I1).


square_sum_y(_, _, 0, _).
square_sum_y(Matrix, C2, I0, N) :-
    (I0 =:= 3 -> I2 = 4 ; I2 is mod(I0 + 1,4)),
    nth1(I0,Matrix,Row1),
    nth1(I2,Matrix,Row2),
    
    square_sum_x(Row1,Row2, C2, N),
    I1 is I0 - 1,
    square_sum_y(Matrix, C2, I1, N).

magic_square(N, Matrix) :-
    Nmax is N * N,
    C1 is Nmax + 1,
    C2 is C1 * 2,
    write(C1),nl,write(C2),nl,
    length(Matrix, N),
    maplist(same_length(Matrix), Matrix),
    append(Matrix, Vs),
    Vs ins 1..Nmax, all_different(Vs),
    maplist(label, Matrix),
    %write(Matrix),nl,
    diag_sum(Matrix, C1, N),
    square_sum_y(Matrix, C2, N, N).

% some queries i tryed out:
% magic_square(4, [[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]]).    
% magic_square(4, [[7, 12, 1, 14], [2, 13, 8, B4], [C1, C2, C3, C4], [D1, D2, D3, D4]]).
% magic_square(4, [[7, A2, A3, 14], [2, B2, 8, B4], [C1, C2, 10, C4], [D1, D2, D3, 4]]).

我确认，有 10 个孔的查询似乎需要很长时间，即使有 9 个孔，在 SWI-Prolog 中也不是很快：

?- time(magic_square(4, [[_, _, _, _], [_, _, 8, 11], [_, _, 10, 5], [_, 6, 15, 4]])).
17
34
% 88,086,790 inferences, 3.449 CPU in 3.449 seconds (100% CPU, 25543070 Lips)
true .

那么这些时间都去哪儿了呢？让我们使用 SWI-Prolog 的分析器：

?- profile(magic_square(4, [[_, _, _, _], [_, _, 8, 11], [_, _, 10, 5], [_, 6, 15, 4]])).
17
34
true.

这将打开一个 GUI 窗口。如果我们点击magic_square/2在谓词列表中，我们看到：

请注意该行__aux_maplist/2_label+0/1：你94.7%的执行时间都花在那里！这是你的maplist(label, Matrix)线，在到达有趣的部分之前你会陷入困境diag_sum and square_sum_y谓词实际上定义了幻方是什么。

基本上都是通过发帖all_different(Vs)然后立即对其进行标记，您要求 Prolog 枚举可以填补输入项中的漏洞的不同数字的所有排列。此类排列的数量以及因此执行时间呈指数增长。

在了解所有约束之前，不应以这种方式使用标签。标签应该是你在谓词中做的最后一件事，或者更好的是，它应该由与你定义约束的谓词不同的谓词来完成。

所以你可以这样设置：

% "Core relation" defining the shape of the solution and constraints.
magic_square_(N, Matrix) :-
    Nmax is N * N,
    C1 is Nmax + 1,
    C2 is C1 * 2,
    write(C1),nl,write(C2),nl,
    length(Matrix, N),
    maplist(same_length(Matrix), Matrix),
    append(Matrix, Vs),
    Vs ins 1..Nmax, all_different(Vs),
    diag_sum(Matrix, C1, N),
    square_sum_y(Matrix, C2, N, N).

magic_square(N, Matrix) :-
    magic_square_(N, Matrix),
    maplist(label, Matrix).

Now diag_sum and square_sum_x将使用未绑定（但受约束）的变量进行调用C1 and C2， 分别。这可以！这就是您使用CLP(FD)时想要的！但是您需要将这些变量的数值平等目标从=:=（期望地面值）#=（实际上适用于约束变量）。

现在您可以快速处理 9 个变量：

?- Matrix = [[_, _, _, _], [_, _, 8, 11], [_, _, 10, 5], [_, 6, 15, 4]], time(magic_square(4, Matrix)).
17
34
% 8,473 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 1506518 Lips)
Matrix = [[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]] ;
% 33 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 749778 Lips)
false.

和 10：

?- Matrix = [[_, _, _, _], [_, _, 8, 11], [_, _, 10, 5], [_, _, 15, 4]], time(magic_square(4, Matrix)).
17
34
% 8,933 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 4338676 Lips)
Matrix = [[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]] .

还有更多：

?- Matrix = [[_, _, _, _], [_, _, 8, _], [_, _, 10, _], [_, _, _, 4]], time(magic_square(4, Matrix)).
17
34
% 24,710 inferences, 0.009 CPU in 0.009 seconds (99% CPU, 2658996 Lips)
Matrix = [[7, 2, 11, 14], [12, 13, 8, 1], [6, 3, 10, 15], [9, 16, 5, 4]] .