Книга: Программирование на языке Пролог для искусственного интеллекта

7.1.2. Решение числового ребуса с использованием nonvar

7.1.2. Решение числового ребуса с использованием nonvar

Известным примером числового ребуса является

D O N A L D
+
G E R A L D
-----------
R O B E R T

Задача состоит в том. чтобы заменить буквы D, О, N и т.д. на цифры таким образом, чтобы вышеприведенная сумма была правильной. Разным буквам должны соответствовать разные цифры, иначе возможно тривиальное решение, например, все буквы можно заменить на нули.

Определим отношение

сумма( N1, N2, N)

где N1, N2 и N представляют три числа данного ребуса. Цель cyммa(N1, N2, N) достигается, если существует такая замена букв цифрами, что N1+N2 = N.

Первым шагом к решению будет выбор представления чисел N1, N2 и N в программе. Один из способов - представить каждое число в виде списка его цифр. Например, число 255 будет тогда представляться списком [2, 2, 5]. Поскольку значения цифр нам не известны заранее, каждая цифра будет обозначаться соответствующей неинициализированной переменной. Используя это представление, мы можем сформулировать задачу так:

  [ D, O, N, A, L, D ]
+ [ G, E, R, A, L, D ]
= [ R, О, B, E, R, T ]

Теперь задача состоит в том. чтобы найти такую конкретизацию переменных D, О, N и т.д., для которой сумма верна. После того, как отношение сумма будет запрограммировано, задание для пролог-системы на решение ребуса будет иметь вид

?- сумма( [D, O, N, A, L, D], [G, E, R, A, L, D],
 [R, O, В, E, R, T ).

Рис. 7.1. Поразрядное сложение. Отношения в показанном i-м разряде такие: D_3i = (C1 + D_1i + D_2i) mod 10; C = (C1 + D_1i + D_2i) div 10 (div — целочисленное деление, mod — остаток от деления).

Для определения отношения сумма над списками цифр нам нужно запрограммировать реальные правила суммирования в десятичной системе счисления. Суммирование производится цифра за цифрой, начиная с младших цифр в сторону старших, всякий раз учитывая цифру переноса справа. Необходимо также сохранять множество допустимых цифр, т.е. цифр, которые еще не были использованы для конкретизации уже встретившихся переменных. Поэтому, вообще говоря, кроме трех чисел N1, N2 и N в рассмотрении должна участвовать некоторая дополнительная информация, как показано на рис. 7.1:

• перенос перед сложением

• перенос после сложения

• множество цифр, доступных перед сложением

• оставшиеся цифры, не использованные при сложении

Для формулировки отношения сумма мы снова воспользуемся принципом обобщения задачи: введем вспомогательное, более общее отношение сумма1. Это отношение будет иметь несколько дополнительных аргументов, соответствующих той дополнительной информации, о которой говорилось выше:

сумма1( N1, N2, N, C1, С, Цифры1, Цифры)

Здесь N1, N2 и N — наши три числа, как и в отношении сумма, C1 — перенос справа (до сложения N1 и N2), а С — перенос влево (после сложения). Пример:

?- сумма1( [H, E], [6, E], [U, S], 1, 1,
 [1, 3, 4, 7, 8, 9], Цифры ).
H = 8
E = 3
S = 7
U = 4
Цифры = [1, 9]

Если N1 и N удовлетворяют отношению сумма, то, как показано на рис. 7.1, C1 и С должны быть равны 0. Цифры1 — список цифр, которые не были использованы для конкретизации переменных. Поскольку мы допускаем использование в отношении сумма любых цифр, ее определение в терминах отношения сумма1 выглядит так:

сумма( N1, N2, N) :-
 cyммa1( N1, N2, N, 0, 0, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], _ ).

Бремя решения задачи переложено теперь на отношение сумма1. Но это отношение является уже достаточно общим, чтобы можно было определить его рекурсивно. Без ограничения общности мы предположим, что все три списка, представляющие три числа, имеют одинаковую длину. Наш пример, конечно, удовлетворяет этому условию, но если это не так, то всегда можно приписать слева нужное количество нулей к более "короткому" числу.

Определение отношения сумма1 можно разбить на два случая:

(1) Все три числа представляются пустыми списками. Тогда

сумма1( [], [], [], 0, 0, Циф, Циф).

(2) Все три числа имеют какую-то самую левую цифру и справа от нее - остальные цифры. То есть, они имеют вид:

[D1 | N1], [D2 | N2], [D | N]

В этом случае должны выполняться два условия:

 (а) Оставшиеся цифры, рассматриваемые как три числа N1, N2 и N, сами должны удовлетворять отношению сумма1, выдавая влево некоторый перенос C2 и оставляя некоторое подмножество неиспользованных цифр Циф2.

 (b) Крайние левые цифры D1, D2 и D, а также перенос C2 должны удовлетворять отношению, показанному на рис. 7.1: C2, D1 и D2 складываются, давая в результате D и перенос влево. Это условие в нашей программе формулируется в виде отношения суммацифр.

Переводя это на Пролог, получаем:

сумма1( [D1 | N1], [D2 | N2], [D | N], C1, С, Циф1, Циф) :-
 сумма1( Nl, N2, N, C1, C2, Циф1, Циф2),
 суммацифр( D1, D2, C2, D, С, Циф2, Циф).

Осталось только описать на Прологе отношение суммацифр. В его определении есть одна тонкая деталь, касающаяся применения металогического предиката nonvar. D1, D2 и D должны быть десятичными цифрами. Если хоть одна из этих переменных еще не конкретизирована, ее нужно конкретизировать какой-нибудь цифрой из списка Циф2. Как только такая конкретизация произошла, эту цифру нужно удалить из множества доступных цифр. Если D1, D2 и D уже конкретизированы, тогда, конечно, ни одна из доступных цифр "потрачена" не будет. В программе эти действия реализуются при помощи недетерминированного вычеркивания элемента списка. Если этот элемент - не переменная, ничего не вычеркивается (конкретизации не было). Вот эта программа:

удалить( Элемент, Список, Список) :-
 nonvar( Элемент), !.
удалить( Элемент, [Элемент | Список ], Список).
удалить(Элемент, [А | Список], [А | Список1]) :-
 удалить( Элемент, Список, Список1).

Полная программа для решения арифметических ребусов приводится на рис. 7.2. В программу включены также определения двух ребусов. Вопрос к пролог-системе для ребуса про DONALD'a, GERALD'a и ROBERT'a с использованием этой программы выглядит так:

?- ребус1( N1, N2, N), сумма( N1, N2, N).
% Решение числовых ребусов
сумма( N1, N2, N) :-
  % Числа представлены в виде списков цифр
 сумма1( N1, N2, N,
  0, 0,
   % Перенос справа и перенос влево равны 0
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], _ ).
   % Все цифры доступны
сумма1( [], [], [], 0, 0, Цифры, Цифры).
сумма1( [D1 | N1], [D2 | N2], [D | N], C1, С, Циф1, Циф) :-
 сумма1( Nl, N2, N, C1, C2, Циф1, Циф2),
 суммацифр( Dl, D2, C2, С, Циф2, Циф).
суммацифр( Dl, D2, C1, D, С, Циф1, Циф) :-
 удалить( D1, Циф1, Циф2),
  % Выбор доступной цифры для D1
 удалить( D2, Циф2, Циф3),
  % Выбор доступной цифры для D2
 удалить( D, Циф3, Циф),
  % Выбор доступной цифры для D
 S is D1 + D2 + C1,
 D is S mod 10,
 С is S div 10.
удалить( A, L, L) :-
 nonvar( A), !.
  % Переменная А уже конкретизирована
удалить( А, [А | L], L).
удалить( А, [В | L], [В | L1]) :-
 удалить( A, L, L1).
% Примеры ребусов
ребус1( [D, O, N, A, L, D],
 [G, E, R, A, L, D],
 [R, O, B, E, R, T].
ребус2( [0, S, E, N, D],
 [0, M, O, R, E],
 [M, O, N, E, Y].

Рис. 7.2.  Программа для арифметических ребусов.

Иногда этот ребус упрощают, сообщая часть решения в виде дополнительного ограничения, например D равно 5. В такой форме ребус можно передать пролог-системе при помощи сумма1:

?- сумма1( [5, O, N, A, L, 5],
 [G, E, R, A, L, 5],
 [R, O, B, E, R, T],
 0, 0, [0, 1, 2, 3, 4, 6, 7, 8, 9], _ ).

Интересно, что в обоих случаях существует только одно решение, т.е. только один способ заменить буквы цифрами.

7.1. Напишите процедуру упростить для упрощения алгебраических сумм, в которых участвуют числа и символы (строчные буквы). Пусть эта процедура переупорядочивает слагаемые так, чтобы символы предшествовали числам. Вот примеры ее использования:

?- упростить( 1 + 1 + а, E).
E = а + 2
?- упростить( 1 + a + 4 + 2 + b + с, E).
E = а + b + с + 7
?- упростить( 3 + x + x, E).
E = 2*x + 3

7.2. Определите процедуру

добавить( Элемент, Список)

для добавления нового элемента в список. Предполагается, что все элементы, хранящиеся в списке, — атомы. Список состоит из всех хранящихся в нем элементов, а за ними следует хвост, который не конкретизирован и служит для принятия новых элементов. Пусть, например, в списке уже хранятся а, b и с, тогда

Список = [а, b, с | Хвост]

где Хвост — переменная. Цель

добавить( d, Список)

вызовет конкретизацию

Xвoст = [d | НовыйХвост] и

Список = [а, b, с, d | НовыйХвост]

Таким способом структура может наращиваться, включая в себя новые элементы. Определите также соответствующее отношение принадлежности.

Оглавление книги