Prolog
Шрифт:
Цифры = [1, 9]
Если Nl и N удовлетворяют отношению сумма, то, как показано на рис. 7.1, С1 и С должны быть равны 0. Цифры1– список цифр, которые не были использованы для конкретизации переменных. Поскольку мы допускаем использование в отношении сумма любых цифр, ее определение в терминах отношения сумма1 выглядит так:
сумма( Nl, N2, N) :-
cyммa1( Nl, N2, N, 0, 0, [0, l, 2, 3, 4, 5, 6, 7, 8, 9], _ ).
Бремя
Определение отношения сумма1 можно разбить на два случая:
(1) Все три числа представляются пустыми списками. Тогда
сумма1( [ ], [ ], [ ], 0, 0, Циф, Циф).
(2) Все три числа имеют какую-то самую левую цифру и справа от нее - остальные цифры. То есть, они имеют вид:
[D1 | Nl], [D2 | N2], [D | N]
В этом случае должны выполняться два условия:
(а) Оставшиеся цифры, рассматриваемые как три числа Nl, N2 и N, сами должны удовлетворять отношению сумма1, выдавая влево некоторый перенос С2 и оставляя некоторое подмножество неиспользованных цифр Циф2.
(b) Крайние левые цифры D1, D2 и D, а также перенос С2 должны удовлетворять отношению, показанному на рис. 7.1: С2, D1 и D2 складываются, давая в результате D и перенос влево. Это условие в нашей программе формулируется в виде отношения суммацифр.
Переводя это на Пролог, получаем:
сумма1( [D1 | N1], [D2 | N2], [D | N], С1, С, Циф1, Циф) :-
сумма1( Nl, N2, N, С1, С2, Циф1, Циф2),
суммацифр( D1, D2, С2, 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: