Как решить криптарифметическую головоломку в прологе

Question

Я должен написать программу Prolog для решения криптарифметической головоломки.

Мне нужно написать функцию решения ([A, M, P, D, Y]), которая присваивает переменным [A, M, P, D, Y] значения от 0 до 9, чтобы оно удовлетворяло уравнению AM+PM= ДЕНЬ. Каждой переменной присваивается другое значение, и A, P и D не могут быть равны 0.

Я начал писать эту функцию, но столкнулся с проблемами при запуске моей программы. Я установил ограничения A, P и D не равными нулю. Проходя через алгоритм, я понял, что D должен быть 1, поэтому я определил это в начале моей программы. Я определил две разные переменные для M (M1 и M2) и установил их равными друг другу, так как разные M в загадке должны быть присвоены одному и тому же значению. Я назначил местоположения различным переменным и добавил их на основе головоломки. Я учел любые переменные, переносимые с помощью переноса в переменных. Моя программа компилируется, но функция не выполняется.

solve([A, M1, M2, P, D, Y]):- D is 1,
A/=0,
P/=0,
D/=0,
M1 = M2,
select(M1, [0,2,3,4,5,6,7,8,9], R1),
select(M2, R1, R2),
Y is (M1+M2) mod 10,
C1 is (M1+M2) // 10,
select(Y, R2, R3),
select(A, R3, R4),
select(P, R4, R5),
select(D, R5, R6),
A is (A+P+C1) mod 10,
D is (A+P+C1)// 10.

Что я делаю неправильно? Что-то не так с моими определениями переменных? Нужно ли мне определять две разные переменные M или достаточно одной?

Answer 1

Вот мое решение для вашей головоломки. Мы просто полагаемся на возвращение PROLOG. Сначала мы выбираем все переменные, а затем проверяем условия головоломки. Я не думаю, что вам нужно определить две г-жи

solve([A,M,P,D,Y]):- 
select(A,[0,1,2,3,4,5,6,7,8,9],WA), % W means Without
not(A=0),
select(M,WA,WMA),
select(P,WMA,WMAP),
not(P=0),
select(D,WMAP,WMAPD),
not(D=0),
select(Y,WMAPD,WMAPDY),
DAY is 100*D+10*A+Y,
AM  is 10*A+M,
PM  is 10*P+M,
DAY is AM+PM.

Answer 2

В дополнение к тому, что опубликовали другие, я хотел бы представить немного другой взгляд на это.

Следующее решение использует GNU Prolog и его ограничения CLP(FD). Такие ограничения доступны во всех широко используемых системах Prolog.

решение (Vs):-
        Vs = [A,M,P,D,Y],
        fd_domain(Vs, 0, 9),
                   А *10 + М
                 + P*10 + M
        #= D*100 + A*10 + Y,
        fd_all_different(Vs),
        A #\= 0,
        P #\= 0,
        D #\= 0.

Теперь я выделю несколько ключевых преимуществ использования ограничений CLP(FD) в этом случае.

Во-первых, очевидно, что мы можем моделировать все требования чрезвычайно простым способом с такими ограничениями. Программа действительно представляет собой почти дословный перевод вашей задачи во встроенные отношения:

• Мне нужно написать функцию решить ([A, M, P, D, Y])

  я использовал solution/1 вместо императива solve/1потому что предикат имеет смысл во всех направлениях, включая конкретные случаи, когда все переменные уже связаны с конкретными целыми числами. В таких случаях мы можем использовать предикат для проверки решений. Называть его "решить" не имеет смысла в тех случаях, когда головоломка уже полностью решена. Кроме того, мы можем использовать предикат для завершения частично инстанцированных решений. В Прологе эффективная практика заключается в том, чтобы избегать необходимости указывать имена предикатов.

• который присваивает переменным [A, M, P, D, Y] значения от 0 до 9

  Об этом говорится через fd_domain(Vs, 0, 9),

• так что оно удовлетворяет уравнению AM+PM=DAY.

  Таким образом, уравнение A*10 + M + P*10 + M #= D*100 + A*10 + Y,

• Каждой переменной присваивается другое значение

  Это выражается встроенным ограничением fd_all_different/1,

• и A, P и D не могут быть равны 0.

  Об этом говорится через A #\= 0 и т.п.

Во-вторых, мы можем использовать наиболее общий запрос для изучения эффектов распространения ограничений:

|?- решение([).Vs = [_ # 3 (2..8), _ # 24 (5..8), 9,1, _ # 87 (0: 2..6)]

или, иначе говоря:

|? - решение ([A, M, P, D, Y]).

A = _ # 3 (2..8)D = 1 M = _ # 24 (5..8)P = 9 Y = _ # 87 (0: 2..6)

Это подтверждает то, что вы говорите: D обязательно 1 в этой загадке. И это также показывает несколько других интересных вещей, которые выходят за рамки того, что вы нашли: P обязательно 9. Кроме того, достаточно строгие ограничения для Mи домены A а также Y также были значительно сокращены.

Это показывает, что распространение ограничений значительно сократило пространство поиска.

Как выглядят конкретные решения? Вот несколько примеров:

|? - решение (Vs), fd_labeling (Vs).Vs = [2,5,9,1,0]?;Vs = [2,7,9,1,4]?;Vs = [2,8,9,1,6]?

да

В-третьих, вы можете запускать различные опции маркировки, чтобы попробовать различные стратегии поиска для исследования пространства решения, без необходимости изменять или перекомпилировать программу.

Наконец, значительно сокращенное пространство поиска обычно приводит к гораздо более быстрым программам. Я оставляю это в качестве упражнения для запуска нескольких тестов, которые показывают, насколько быстрее в этом случае версия на основе CLP(FD).

Смотрите clpfd для получения дополнительной информации об этой важной декларативной парадигме.

Answer 3

Вы пишете: "Моя программа компилируется, но функция не выполняется:"

solve([A, M1, M2, P, D, Y]):- D is 1,
    A/=0,

Неудивительно. Во-первых, нет /= оператор в прологе. Я полагаю, вы имели в виду \=, Но A \= B означает "А не может быть объединен с В". В твоем случае B 0, но A это еще не установленная логическая переменная. Это может быть объединено с чем угодно. Вы должны использовать только \= чтобы проверить неравенство, после того, как были созданы все logvars!

Так, A \= 0 не удается (Другое дело, M1=M2 это лишнее, вы можете просто использовать M на протяжении).

Общий инструмент для решения таких головоломок - уникальный выбор из сужающихся областей:

selectM([A|As],S,Z):- select(A,S,S1),selectM(As,S1,Z).
selectM([],Z,Z).

С ним ваша головоломка просто

solve([A,M,P,D,Y]):-
  selectM([A,P,D],[1,2,3,4,5,6,7,8,9],R),     % R is the remaining domain
  selectM([M,Y],[0|R],_),                     % don't care what remains
  10*(A+P)+M+M =:= 100*D+10*A+Y.

---

У вас есть правильная идея выяснить назначения, прежде чем искать, где это возможно. Используя ваш подход, это можно записать как

solve([A,M,P,D,Y]):-    
  selectM([M,A],[0,1,2,3,4,5,6,7,8,9],R),
  A =\= 0,
  Y  is (M+M) mod 10,     % AM+PM=DAY
  C1 is (M+M) // 10,
  A  is (A+P+C1) mod 10,
  D  is (A+P+C1) // 10,
  selectM([P,D,Y],R,_),   % ensure all are different
  p =\= 0, D =\= 0.

Опять же, мы должны выбрать A перед проверкой его стоимости.

Answer 4

Я думаю, что вашей проблемой являются множественные "назначения" для D. Сначала D привязывается к 1, после этого не может изменить значение (Пролог использует объединение, а не назначение). Тогда оба

...
select(D, R5, R6),
...
D is (A+P+C1)// 10.

потерпит неудачу, когда D отличается от 1