Пролог сумма списка чисел

Я новичок в Прологе и хочу написать poppler(Nums, Plate, Tastiness), который принимает список ровно из 9 чисел в качестве входных данных и, если возможно, возвращает перестановку этих чисел, которая образует восхитительную тарелку поплера, когда Plate читается в формате строки.

Тарелка Попплера называется вкусной, если сумма Попплеров в каждой из трех строк, столбцов и двух главных диагоналей одинакова. Эта общая сумма называется его вкусовщиной.

Например, это вкуснейшая тарелка Попплер со вкусом 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] не обязательно будет перестановкой чисел, может быть одним и тем же числом несколько раз.   -  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