Решение арифметического выражения с несколькими ответами (вьетнамский математический лабиринт)

Question

Я должен попытаться решить этот вьетнамский математический вызов (https://www.theguardian.com/science/alexs-adventures-in-numberland/2015/may/20/can-you-do-the-maths-puzzle-for-vietnamese-eight-year-olds-that-has-stumped-parents-and-teachers) с помощью пролога, и я был очень тупик относительно того, как писать предикат. Вот вопрос:

Пусть обычные правила арифметики старшинства (т.е. умножение/деление перед сложением/вычитанием). Ответы должны быть в виде списка цифр, которые будут введены в пробелы в лабиринте слева направо. Назовите предикат mathmaze и попросите его принять один аргумент, который получает экземпляр как правильный список номеров (и дает другие ответы при появлении запроса;;).

Это то, что у меня есть до сих пор, но я понятия не имею, как на самом деле, как заставить его попробовать 1-9 в каждой позиции уравнения.

mathmaze([H|T]) :- 
    A + ((13* B)/C) + D + (12 * E) - F - 11 + G * (H/I) - 10 = 66. 

Answer 1

mathmaze([A,B,C,D,E,F,G,H,I]) :- 
    permutation([1,2,3,4,5,6,7,8,9], [A,B,C,D,E,F,G,H,I]), 
    66 is (A + ((13 * B)/C) + D + (12 * E) - F - 11 + (G * (H/I)) - 10). 

Это говорит:

• Возьмите список 9 переменных
• Составьте список переменных перестановку списка, состоящего из 1 до 9.
• Убедитесь, что переменные оценивают (с использованием) до 66.

T его можно было бы написать с помощью CLPFD, но он не обеспечивает какое-либо нецелое деление, поэтому он будет генерировать ложные ответы, а для проблемы, столь же жесткой, как это, замена перестановки на all_distinct/1 и ins/2 не стоит усилий (но CLPFD, безусловно, полезная библиотека для этого стиля проблемы в целом).

Answer 2

Применение CLP (FD) ограничения

Во-первых, общее замечание: Когда рассуждая над целых в Прологе, я настоятельно рекомендую вам использовать CLP вашей системы (FD)   ТРУДНОСТИ.

Как @JimAshworth правильно указывает, такие ограничения работают только над целых, и, в частности, не обеспечивают деление с дробными результатами.

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

В этом случае я могу устранить разделение

A/B #= C 

просто писать вместо:

A #= B*C 

алгебраически, я просто умножаются как стороны уравнения с B.

Решение

Следовательно, возможное решение может выглядеть следующим образом:

 
mathmaze(Vs) :- 
     Vs = [A,B,C,D,E,F,G,H,I], 
     Vs ins 1..9, 
     all_different(Vs), 
      A*C*I + 13*B*I + D*C*I + 12*E*C*I 
     - F*C*I - 11*C*I + G*C*H - 10*C*I #= 66*C*I. 

Пример запрос и результат:

 
?- mathmaze(Vs), time(labeling([ff], Vs)). 
% 5,869,675 inferences, 7.221 CPU in 7.243 seconds (100% CPU, 812897 Lips) 
Vs = [1, 2, 6, 4, 7, 8, 3, 5, 9]. 

корректность

Давайте теперь использовать другой отправляемые рецептура до тест это результат. С принятым ответом мы получаем:

 
?- mathmaze([1, 2, 6, 4, 7, 8, 3, 5, 9]). 
false. 

Итак, что это: Это решение или нет?

Судя по тому, номера немного с плавающей точкой может помочь нам, это может быть решением:

 
?- X is 1+13*2/6+4+12*7-8-11+3*(5/9)-10. 
X = 66.0. 

Конечно, числа с плавающей точкой имеют чрезвычайно ограниченную помощь в таких случаях, и поэтому мы используем рациональные числа   вместо:

 
?- X is 1+13*(2 rdiv 6) +4+12*7-8-11+3*(5 rdiv 9)-10. 
X = 66. 

Да, это решение! Однако, так как принятый ответ использует числа с плавающей точкой, она не распознается как таковой, потому что:

 
?- 66 is 66.0. 
false. 

Это верно! 66.0 не 66. Добро пожаловать в новаторскую технологию 1940-х годов.

В общей сложности принятый ответ пропустил 136 решений из-за использования чисел с плавающей запятой. Однако, поскольку он находит несколько   решений (6 в   всего), такие ошибки легко упускать из виду. Чтобы быть в безопасности   сторона, я рекомендую вам всегда использовать целые числа, рациональные номера или аналогичные сейф представление при рассуждении о   номера в   Пролог.