Пролог сума на списък от числа

Нов съм в Prolog и искам да напиша poppler(Nums, Plate, Tastiness), което приема списък от точно 9 числа като вход и, ако е възможно, връща пермутация на тези числа, която образува вкусна плоча с поплер, когато Plate се чете във формат на главния ред.

Твърди се, че една чиния Poppler е вкусна, ако сборът от Poppler във всеки от трите реда, колони и два главни диагонала е еднакъв. Тази обща сума се нарича неговата вкусност.

Например, това е вкусна чиния Poppler с вкус 15:

2 7 6

9 5 1

4 3 8

Ето моя опит:

size([], 0).
size([Head|T], N) :-
   size(T, N1),
   N is N1+1.

is_equal([U, V, W], [X, Y, Z], Sum) :-
    Sum is U + V + W,
    Sum is X + Y + Z.

poppler(Nums, Plate, Tastiness):- 
    size(Nums, 9),
    poppler(Nums, [A, B, C, D, E, F, G, H, I], Tastiness),
    member(A, Nums),
    member(B, Nums),
    member(C, Nums),
    member(D, Nums),
    member(E, Nums),
    member(F, Nums),
    member(G, Nums),
    member(H, Nums),
    member(I, Nums),
    is_equal([A, B, C], [D, E, F], Tastiness),
    is_equal([A, B, C], [G, H, I], Tastiness),
    is_equal([G, H, I], [D, E, F], Tastiness),
    is_equal([A, D, G], [B, E, H], Tastiness),
    is_equal([A, D, G], [C, F, I], Tastiness),
    is_equal([B, E, H], [C, F, I], Tastiness),
    is_equal([A, E, I], [C, E, G], Tastiness).

Но това не работи. Как мога да го поправя?


list sum prolog magic-square clpfd
person MicM    schedule 19.03.2014    source източник
comment
Един от проблемите: вашата логика на member(A, Nums), и т.н. е погрешна: [A..I] не е задължително да е пермутация на Nums, може да бъде едно и също число няколко пъти.   -  person Sergii Dymchenko    schedule 19.03.2014

Отговори (3)


arrow_upward
2
arrow_downward

Ето фиксирана версия на вашия код с някои коментари. Тестван в SWI-Prolog.

Работи, но е наистина бавен (ще работи за минути за вашия пример). Това е така, защото пространството за търсене е голямо и няма подрязване на пространството за търсене.

Вие наистина трябва да използвате подход за програмиране с ограничения за този проблем - той подрязва пространството за търсене по умен начин и тази програма работи незабавно.

% should really just use length/2
size([], 0).
size([Head|T],N) :- size(T,N1), N is N1+1.

% could use simpler version of this like "is_equal([X, Y, Z], Sum)"
is_equal([U, V, W], [X, Y, Z], Sum) :- Sum is U + V + W, Sum is X + Y + Z.

poppler(Nums, Plate, Tastiness) :- 
    size(Nums, 9),
    [A, B, C, D, E, F, G, H, I] = Plate,

    msort(Nums, Sorted),

    member(A, Nums),
    member(B, Nums),
    member(C, Nums),
    member(D, Nums),
    member(E, Nums),
    member(F, Nums),
    member(G, Nums),
    member(H, Nums),
    member(I, Nums),

    % Check if Plate is a permutation of Nums
    msort(Plate, Sorted),

    is_equal([A, B, C], [D, E, F], Tastiness),
    is_equal([A, B, C], [G, H, I], Tastiness),
    is_equal([G, H, I], [D, E, F], Tastiness),
    is_equal([A, D, G], [B, E, H], Tastiness),
    is_equal([A, D, G], [C, F, I], Tastiness),
    is_equal([B, E, H], [C, F, I], Tastiness),
    is_equal([A, E, I], [C, E, G], Tastiness).
person Sergii Dymchenko    schedule 19.03.2014
comment
Много благодаря. Да, прав си, наистина е бавен. Мисля, че трябва да се обърна към програмирането с ограничения за това. - person MicM; 19.03.2014

arrow_upward
1
arrow_downward

Изглежда като идеален проблем за решаване с логическо програмиране на ограничения.

Ето моето решение в ECLiPSe CLP Prolog (може да се преведе на други системи Prolog):

:- lib(gfd).

poppler(Nums, Plate, S) :-
   [A, B, C, D, E, F, G, H, I] = Plate,
   sorted(Nums, Sorted), sorted(Plate, Sorted),
   % rows
   A + B + C #= S,
   D + E + F #= S,
   G + H + I #= S,
   % colums
   A + D + G #= S,
   B + E + H #= S,
   C + F + I #= S,
   % diagonals
   A + E + I #= S,
   C + E + G #= S,
   labeling(Plate).

Пробно изпълнение:

[eclipse]: poppler([1, 2, 3, 4, 5, 6, 7, 8, 9], Plate, 15).
Plate = [2, 7, 6, 9, 5, 1, 4, 3, 8]
person Sergii Dymchenko    schedule 19.03.2014
comment
Благодаря за отговора. Хрумна ми идеята как да реша този проблем, но не знам къде сбърках в опита си. Искам да знам как да поправя кода си, за да го направя правилен. Между другото, аз използвам swi-prolog. - person MicM; 19.03.2014

arrow_upward
0
arrow_downward

Мисля, че основният ви проблем е, че като използвате member/2, вие генерирате много повече опити, отколкото ще бъдат отхвърлени по-късно. Вместо това можете да използвате пермутация/2:

poppler0(Nums, Plate, Tastiness):-
    Plate = [A, B, C, D, E, F, G, H, I],
    permutation(Nums, Plate),
    is_equal([A, B, C], [D, E, F], Tastiness),
    is_equal([A, B, C], [G, H, I], Tastiness),
    is_equal([G, H, I], [D, E, F], Tastiness),
    is_equal([A, D, G], [B, E, H], Tastiness),
    is_equal([A, D, G], [C, F, I], Tastiness),
    is_equal([B, E, H], [C, F, I], Tastiness),
    is_equal([A, E, I], [C, E, G], Tastiness).

добиви

?- numlist(1,9,L),poppler0(L,X,15).
L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = [2, 9, 4, 7, 5, 3, 6, 1, 8] ;
...

Вместо member/3, select/3 няма да се дублира:

poppler1(Nums, Plate, Tastiness):-
    Plate = [A, B, C, D, E, F, G, H, I],
    %permutation(Nums, Plate),
    select(A, Nums, Num1),
    select(B, Num1, Num2),
    select(C, Num2, Num3),
    select(D, Num3, Num4),
    select(E, Num4, Num5),
    select(F, Num5, Num6),
    select(G, Num6, Num7),
    select(H, Num7, Num8),
    select(I, Num8, []),
    is_equal([A, B, C], [D, E, F], Tastiness),
    is_equal([A, B, C], [G, H, I], Tastiness),
    is_equal([G, H, I], [D, E, F], Tastiness),
    is_equal([A, D, G], [B, E, H], Tastiness),
    is_equal([A, D, G], [C, F, I], Tastiness),
    is_equal([B, E, H], [C, F, I], Tastiness),
    is_equal([A, E, I], [C, E, G], Tastiness).

Освен това, тъй като пермутацията сега е „нарязана“, можем да „избутаме“ някои от тестовете по-рано, за да направим всичко по-бързо:

poppler2(Nums, Plate, Tastiness):-
    Plate = [A, B, C, D, E, F, G, H, I],
    select(A, Nums, Num1),
    select(B, Num1, Num2),
    select(C, Num2, Num3),
    select(D, Num3, Num4),
    select(E, Num4, Num5),
    select(F, Num5, Num6),
    is_equal([A, B, C], [D, E, F], Tastiness),
    select(G, Num6, Num7),
    select(H, Num7, Num8),
    select(I, Num8, []),
    is_equal([A, B, C], [G, H, I], Tastiness),
    is_equal([G, H, I], [D, E, F], Tastiness),
    is_equal([A, D, G], [B, E, H], Tastiness),
    is_equal([A, D, G], [C, F, I], Tastiness),
    is_equal([B, E, H], [C, F, I], Tastiness),
    is_equal([A, E, I], [C, E, G], Tastiness).

?- numlist(1,9,L),time(poppler0(L,X,15)).
% 642,293 inferences, 0.253 CPU in 0.256 seconds (99% CPU, 2540589 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = [2, 7, 6, 9, 5, 1, 4, 3, 8] 
.

8 ?- numlist(1,9,L),time(poppler1(L,X,15)).
% 385,446 inferences, 0.217 CPU in 0.217 seconds (100% CPU, 1777885 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = [2, 7, 6, 9, 5, 1, 4, 3, 8] 
.

9 ?- numlist(1,9,L),time(poppler2(L,X,15)).
% 48,409 inferences, 0.029 CPU in 0.029 seconds (100% CPU, 1643812 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = [2, 7, 6, 9, 5, 1, 4, 3, 8]

Друг малък проблем е, че някаква сума се оценява повече от време, което вероятно се дължи на вашия избор да кодирате теста с is_equal/3. Вместо това бих написал

poppler3(Nums, Plate, Tastiness):-
    Plate = [A, B, C, D, E, F, G, H, I],
    select(A, Nums, Num1),
    select(B, Num1, Num2),
    select(C, Num2, Num3),
    sumlist([A, B, C], Tastiness),
    select(D, Num3, Num4),
    select(E, Num4, Num5),
    select(F, Num5, Num6),
    sumlist([D, E, F], Tastiness),
    select(G, Num6, Num7),
    sumlist([A, D, G], Tastiness),
    sumlist([C, E, G], Tastiness),
    select(H, Num7, Num8),
    sumlist([B, E, H], Tastiness),
    select(I, Num8, []),
    sumlist([G, H, I], Tastiness),
    sumlist([C, F, I], Tastiness),
    sumlist([A, E, I], Tastiness).

това дава

?- numlist(1,9,L),time(poppler3(L,X,15)).
% 14,371 inferences, 0.004 CPU in 0.004 seconds (99% CPU, 3359784 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = [2, 7, 6, 9, 5, 1, 4, 3, 8] 
.

но отново, sumlist/2 е по-общо от необходимото и има допълнителна печалба за вграждане на сумата:

poppler4(Nums, Plate, Tastiness):-
    Plate = [A, B, C, D, E, F, G, H, I],
    select(A, Nums, Num1),
    select(B, Num1, Num2),
    select(C, Num2, Num3),
    A+B+C =:= Tastiness,
    select(D, Num3, Num4),
    select(E, Num4, Num5),
    select(F, Num5, Num6),
    D+E+F =:= Tastiness,
    select(G, Num6, Num7),
    A+D+G =:= Tastiness,
    C+E+G =:= Tastiness,
    select(H, Num7, Num8),
    B+E+H =:= Tastiness,
    select(I, Num8, []),
    G+H+I =:= Tastiness,
    C+F+I =:= Tastiness,
    A+E+I =:= Tastiness.

добиви

?- numlist(1,9,L),time(poppler4(L,X,15)).
% 3,394 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 1827856 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = [2, 7, 6, 9, 5, 1, 4, 3, 8] 
.
person CapelliC    schedule 19.03.2014