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

Широко известный пример числового ребуса приведен ниже.

DONALD + GERALD

ROBERT

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

Глава 7. Дополнительные встроенные предикаты

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

одном

м;

sum С N1, Ы2

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

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

[0,0,К, A, L, D] + [G,E,R,A,L,D]

]

= [R,0, В, Е, R, Т] Number! - ID;:,Dj2, Number2 « [D^ifDzz,

[D31,D-<

Number3

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

1- sura! [D,0,N,A,L,D], [G,E,R,A, L, DJ ,[R, О, Б, E, R, T] ).

Чтобы определить отношение s л . на списках, состоящих из десятичных цифр, необходимо реализовать в программе правила суммирования в десятичной системе счисления. Суммирование выполняется поразрядно, начиная с крайнего правого млад­шего разряда, и продолжается в направлении влево, в сторону старших разрядов; при этом всегда учитывается цифра переноса из предыдущего разряда. Кроме того, необхо­димо предусмотреть использование множества доступных цифр, т.е. цифр, которые еще не использовались для конкретизации ранее встретившихся переменных. Поэто­му в целом, кроме трех чисел, N1, N2 и К, требуется еще некоторая дополнительная информация (рис. 7.1):

• цифра переноса, образовавшаяся до суммирования чисел;

• цифра переноса, образовавшаяся после суммирования чисел;

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

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

Здесь f- перенос \^ равен О О

Перенос справа

Здесь

перенос должен быть равен О

О

С!

Number!	................ □..........................
* Number2	-D3l............
= Nitmber3	■D„......................................................

Рис. 7,1. Поразрядное суммирование; цифры в разря­де i связаны между собой следующими соотноше HUSMU;D_3i = {Cl +D_:i + £Ы mod 10. С = <С1 +Он * Oil) div 10

ЧастьI- Язык Prolog

«»■ Для формулировки отношения sum снова воспользуемся принципом обобщения проблемы; для этого введем вспомогательное, более общее отношение, suml. Отноше­ние suml имеет некоторые дополнительные параметры, которые соответствуют опи­санной выше дополнительной информации:

suml( HI, Ш_г N, C1, С, Digitsl,Digits)

тде N1, N2 и N — три числа, такие же, как в отношении sum, C1 — цифра переноса из предыдущего разряда (до суммирования N1 и N2) и С — цифра переноса в сле­дующий разряд (после суммирования N1 и N2). Пример применения этого отношения показан ниже.

?- suml[ [Н,Е] , [6,Е] , [U,S], 1, 1, [1,3,4,7,8,9], Digits).

S = 8

Е = 3

S = T

U ^~ ч

Digits= [1,9]

Этот пример соответствует следующей операции суммирования: 1+- *- 1

Ft 3 6 3

Т

Как показано на рис. 7.1, переменные С1 и С должны быть равны 0, если N1, N2 и N соответствуют отношению sum. Кроме того, Digitsl — список доступных цифр для конкретизации переменных в числах N1, N2 и И, a Digits — список цифр, кото­рые не использовались при конкретизации этих переменных. Поскольку при подборе чисел, соответствующих отношению sum, разрешается использовать любые десятич­ные цифры, отношение sum может быть определено в терминах отношения suml сле­дующим образом:

suiat HI, N2, Н) :-suml ( Ml, N2, N, 0, 0, [0,1, 2, 3, 4, 5, 6,7, 8, Э] , _) .

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

При определении отношения suml могут рассматриваться два случая, как показа­но ниже.

1. Три числа представлены пустыми списками, таким образом: suml[ [], [], Е], С, С, Digs, Digs).

2. Все три числа имеют какой-то крайний левый (старший) разряд и оставшиеся цифры справа от этого разряда, поэтому они имеют следующую форму:

[Dl i N1], [D2 i Я2] г [D I H]

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

а) Три числа, N1, N2 и К, должны соответствовать отношению suml; при этом
формируется некоторая цифра переноса (С2) в старший разряд и остается
некоторое неиспользуемое подмножество десятичных цифр, Digs2.

б) Самые старшие разряды (Dl, D2 и 3) и цифра переноса (С2) должны соот­
ветствовать соотношениям, показанным на рис. 7.1, согласно которым в
Т>СТ9ЗйЛ2й% йдозкяжья ■щьфр tl, Ъ\ ~& Ъ1 ^щшчфу-хпк.ъ ■а.-иф-ръ ъ и -ц^фра пе­
реноса в старший разряд. Это условие можно сформулировать в программе
как отношение digit sum.

Глава 7. Дополнительные встроенные предикаты

в рассматриваемом слу-

После перевода на язык Prolog условий, представленных чае, получаем следующее:

*ш1( [Dl I HI], [D2 | N2], [D [ К], С1, С, Digsl, Digs) :-small И1, N2, N, Cl, C2, Digsl, Digs2), digitsum( Dl, D2, C2, D, C, Digs2, Digs).

Остается только определить не языке Prolog отношение digitsum. Следует отме­тить один тонкий нюанс, который касается использования металогического предика­та nonvar. Переменные Dl, D2 и D должны представлять собой десятичные цифры. Если одна из этих переменных еще не конкретизирована, она должна стать конкре­тизированной значением одной из цифр в списке Digs2. После этого данную цифру необходимо удалить из набора доступных цифр, А если переменные Dl, D2 или D уже конкретизированы, то, безусловно, ни одна из доступных цифр не должна быть за­трачена на их конкретизацию. Это условие реализуется в программе в виде недетер­минированной операции удаления элемента от списка.. Если элемент не является пе­ременной, то ничего не удаляется (конкретизация не происходит). Ниже приведена программа, соответствующая этому условию. del_var( Item, List, List) :-

nonvar i Item), !. % Элемент Item уже конкретизирован

del_var( Item, [Item [ List], List). i. Удалить голову списка

del_var< Item, [A | List), [A ! List!]) :-

del_var{ Item, List, Listl» . % Удалить элемент Item из хвоста списка

Окончательный вариант программы для решения числовых ребусов приведен в листинге 7.1, Эга программа включает также определения двух задач, С использова­нием данной программы можно задать системе Prolog вопрос, касающийся замены цифрами букв в словах DOKALD, GERALD и ROBERT, следующим образом: ?- puzzieKNl, N2, К), sum! si, N2, в).

Листинг 7.1.Программа решения числовых ребусов

Решение числовых ребусов

sum [Ш\, Ы2, Nj : - suml ( Hi, N2, N, о, о, [0,1,2,3,4,5,6,7,

Ч Числа, представленные как списки цифр

Обе цифры переноса, справа и влево, равны О I Все доступные цифры

■9] ,_)

suml [ [], [], [], С, С, Digits, Digits).

suml[ [D1IN1], [D2IN2], ;0|к:,С1, С, Digsl, Digs) suml(Ml, N2, H, Cl, C2, Digsl, Digs2) , digitsumt Dl, D2, C2 , D, C, Digs2, Digs).

: -

digitsuffii Dl, D2, Cl, D, C, Digsl, Digs)

del_var( Dl, Digsl, Digs2) del_var( D2, Digs2, Digs3), del_var( D, Digs3, Digs) ,

S is Dl + D2+ Cl,

D is S mod 1С,

С is S // 10.

: -

% Выбрать доступную цифру для Dl] .

* Выбрать доступную цифру для D2
% Выбрать доступную цифру для D

Остаток

* Целочисленное деление

del_var( A, L, Li :-

nonvar(A), !. del_var[ A, [A|L], L) .

% Переменная А уже конкретизирована % Удалить голову списка

del_var[ A, [B|L], [B|L1]> del var( A, L, LI) .

: -

Удалить элемент из хвоста списка

* Некоторые задачи

Часть I. Язык Prolog

ouzzlel[ [D,0,N,A,L, D] , [G,E,R,A,L,D], [R,0,B,E,R,T] )

puzzle2( [0,S,E,N,D] ,

[0,M,O,R,E], [M, O, N_rE,Y] ) .

Иногда решение подобных задач можно упростить, указав в качестве дополни­тельного ограничения цифровое значение одной из букв (например, сообщив, что D равно 5). Задачу, представленную а такой форме, можно сообщить системе Prolog с использованием отношения suml следующим образом:

?- sumlC !S,0,H,ft,L,5] , [G,E,R, A,L, 5] , [R,0,B,E,R,T3 ,

О, 0, [0, 1,2,3, 4, 6,7,8,9], _) .

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

Упражнения

7.1. Напишите процедуру simplify для упрощения символических выражений
суммирования, состоящих из цифр и символов (прописных букв). Допустим,
что эта процедура должна переупорядочивать слагаемые в выражениях таким
образом, чтобы символы предшествовали цифрам. Ниже приведены примеры
использования такой процедуры.

?- simpli£y( 1 + 1 + а, Е) .

Е = а + 2

?- simplify( l+a+4+2+b+c, EL

£ = а+ Ь + с + 1

?- simplify) 3 + У. + У., Е! .

Е = 2*х + 3

7.2. Определите процедуру
add_to_tail ( Item, List}

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

List = [а, Ъ, с I Tail]

где Tail — переменная. Цель

add_to_taii( d, List)

вызывает следующую конкретизацию:

Tail = Id | HswTail] v. List = [a, b, c, d I HewTail]

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

Глава 7, Дополнительные встроенные предикаты

7.2. Создание и декомпозиция термов: предикаты =.., functor, arg и name

Для декомпозиции термов и создания новых термов предусмотрены три встроен­ных предиката: functor, arg и "=. .". Вначале рассмотрим предикат =. ., который записывается как инфиксный оператор и читается как "юнив" (univ). Цель

Term =.. L

является истинной, если L - список, содержащий главный функтор Term, за кото­рым следуют его параметры. Применение этого предиката демонстрируется на сле­дующих примерах:

?- f ( а, Ь) =.. L.

L = [f, a, b]

?- Т -. . [rectangle, 3, 5] .

Т = rectangle Г 3, 5)

?- Z ». . [р, X, f(X,Y)] .

Z = р( X, f<X,Y] )

Необходимость декомпозиции терма на его компоненты (функтор и параметры) и создания нового терма из указанного функтора и параметров можно продемонстриро­вать на следующем примере.

Рассмотрим программу, предназначенную для манипулирования геометрическими фигурами. К числу таких фигур относятся квадраты, прямоугольники, треуголь­ники, окружности и т.д. Эти фигуры могут быть представлены в программе в виде термов, в которых функтор обозначает тип фигур, а параметры задают размер фигу­ры, например, как показано ниже.

square! Side)

triangle; Sidel, Side2, Side3)

circle ! R)

Одной из операций над подобными фигурами может быть их увеличение. Такую операцию можно реализовать в виде следующего отношения с тремя параметрами: enlarge! Fig, Factor, Figl)

где Fig и Figl — геометрические фигуры одного и того же типа (с одинаковым функтором), а параметрами фигуры Figl являются параметры фигуры Fig, увели­ченные путем умножения на коэффициент Factor. Для простоты предположим, что все параметры фигуры Fig уже известны (иными словами, они конкретизированы числовыми значениями), известен также и коэффициент Factor, Ниже показан один из способов программирования отношения enlarge.

enlarge! square (A) , F, square(All) :-

Al is F*A. enlarge! gitcle<R) , F, circle(Rl)) :-

RI is F*R1, enlarge! rectangle (A, B) , F, rectangle [Al, Bl) ) :-

Al is F*A, Bl is F*B.

Такой подход позволяет добиться успеха, но становится очень громоздким, если количество типов фигур достаточно велико. Кроме того, он не позволяет заранее учесть все возможные типы фигур, которые в дальнейшем могут быть предусмотрены в программе. Поэтому для каждого нового типа потребуется еще одно предложение, хотя во всех предложениях выполняется, по сути, одно и то же действие: берутся параметры первоначальной фигуры, все эти параметры умножаются на заданный ко­эффициент, после чего создается фигура того же типа с новыми параметрами.

Ниже показана одна (безуспешная) попытка обрабатывать, по меньшей мере, все фигуры с одним параметром с помощью одного предложения.

Часть I. Язык Prolog

Но обычно использование подобный конструкций в языке Prolog не допускается, поскольку функтор должен быть атомом, поэтому переменная Туое не может приме­няться в позиции функтора по требованиям синтаксиса. Возможный способ выхода из этой ситуации состоит в использовании предиката "=. .". В таком случае процеду­ра enlarge может быть представлена полностью обобщенно {для геометрического объекта любого типа) следующим образом:

enlarge! Fig, Г, Figl) :-Fig =.. [Type | Parameters], multiplylist ( Parameters, F, Parameters!) , Figl =.. [Type I Parametersl].

multiplylist( [], _, [] ) . multiplylist ( [X | L] , F, [XI | LI]) :-XI is F*X, multiplylist! L, F, Ll).

Следующий пример использования предиката ^в=. ." относится к области манипу­лирования символьными обозначениями, применяемыми в формулах. При этом часто используется операция, в которой определенное подвыражение заменяется другим выражением. Определим отношение substitute ( Subterm, Term, Subterml, Terml)

следующим образом: если все вхождения подвыражения Sub-term в выражении Term замещаются подвыражением Subterml, то будет получено выражение Terml, напри­мер, как показано ниже.

?- substitute! tliiix), 2*sin<x)*f(smCO), t, F). F= 2*t*f(«

Под вхождением Subterm в Term подразумевается некоторая часть выражения
Terra, которая сопоставляется с подвыражением Subterm. Поиск вхождений осуще­
ствляется сверху вниз, поэтому цель
?- substitute (a + b, f[ a, A+B), v, F) .
приводит к получению следующих результатов:
F = f ( a,v) Г- f ( a, v + v)

А =а, ане А-а + Ь

В= Ь Б = а +Ь

При определении отношения substitute необходимо предусмотреть принятие следующих решений в зависимости от конкретной ситуации: Если Subterm = Term, то Terml = Subterml;

в«противном случае, если Tem ^m™ • типу 'atomic'

то Terml = Tem (ничего не требует замены),

в противном случае замена должна быть выполнена в параметрах Term.

Эти правила могут быть преобразованы в программу Prolog, показанную в лис­тинге 7.2.

Листинг 7.2. Процедура замены субтерна в терме другим субтермом

% substitute! Subterm, Term, Subterml, Terml) .-

I если все ЬХОЖДеНИЯ субтерма Subterm в терме Term будут заменены

% субтермомSubterml, то Судет получен терм Terml

I Случай 1. Заменавсего терма

substitute{ Term, Term, Terml,Terml) :- !.

% Случай 2. Ничего не требует замены, если Term относится к типу 'atomic'

substitute! _, Term, _, Term) :-

Глава 7. Дополнительные встроенные предикаты

atomic (Term) , !.

% Случай 3. Выполнение замены Б параметрах

substitute! Sub, Term, Sufcl, Terml) :-

Term =.. [FiArgsl, % Получить параметры

snbstlist! Sub, Args, £ubi_r argsl!, I Выполнить Е НИХ замену

Terml =.. [Flargsl].

substlist ; _, [] , _, []] .

substlistt Sato, [Term r Terms], Subl, [Terral|Terms!]) :-

Безусловно, в качестве целей могут также использоваться термы, созданные с по­мощью предиката "= . ."'. Преимущество этого подхода состоит в том, что программа приобретает способность в процессе своей работы самостоятельно вырабатывать и выполнять цели, представленные в формах, которые не всегда можно было предви­деть ко времени написания этой программы. Последовательность целей, иллюстри­рующих подобный эффект, может выглядеть таким образом:

obtain! Functor;,

compute ( Arglist!,

Goal -., -Functor I Arglist],

Goal

Здесь obtain и compute представляют собой некоторые определяемые пользова­телем процедуры для получения компонентов цели, которая должна быть создана в программе. После этого цель создается с помощью предиката "= . ."и вызывается на выполнение путем указания ее имени, Goal.

Некоторые реализации Prolog могут требовать, чтобы все цели по мере их появле­ния в программе синтаксически представляли собой либо атомы, либо структуры с атомом в качестве главного функтора. Поэтому в подобном случае переменная, неза­висимо от ее окончательной конкретизации, может оказаться синтаксически непри­емлемой для использования в качестве цели. Эту проблему можно обойти с помощью еще одного встроенного предиката, call, параметром которого является выполняе­мая цель. В соответствии с этим приведенный выше пример может быть переформу­лирован таким образом:

Goal =.. [Functor I arglist], calif Goal)

Иногда может потребоваться извлечь из терма только его главный функтор или один из параметров. Для этого допустимо, безусловно, воспользоваться отношением "= . .". Но может оказаться, что проще и эффективнее использовать одну из двух других встроенных процедур для манипулирования термами: functor и згд. Их на­значение может быть описано следующим образом: цель functor I Terra, F, Ы)

является истинной, если F - главный функтор терма Term и N - арность функтора F. С другой стороны, цель

arg( Ы, Term, A)

является истинной, если А — N-й параметр в терме Terra, при условии, "что парамет­ры пронумерованы слева направо, начиная с 1. Применение этих предикатов демон­стрируется на следующих примерах: ;- functort t( f(X), X, t), Tun, Arityi

Fun = t Arity = 3

?- argl 2, f : X, t (a) , t (b) ) , Y) .

158 Часть I.Язык Prolog

Y = t(a)

1- functor) D, date, 3),

arg( 1, D, 29) ,

arg(2, D, June), arg( 3, D, 1582). D - date ( 29, June, 1982)

Последний пример показывает особую область применения предиката functor. Цель functor ( D, date, 3} создает общий терм с тремя параметрами, главным функтором которого является date. Этот терм является общим в том смысле, что три его параметра представляют собой неконкретизированные переменные, имена кото­рых генерируются системой Prolog, например: D = datet _5, _6, _7)

Затем эти три переменные конкретизируются в приведенном выше примере с по­мощью трех целей arc

С этим набором встроенных предикатов связан предикат пагге, применяемый для создания/декомпозиции атомов (см. главу 6). В данном разделе для полноты снова рассмотрим его назначение. Предикат name ( A, L) принимает истинное значение, если L — список кодов символов ASCII в имени атома А.

Упражнения

7.3. Определите предикат ground ( Terra) таким образом,чтобы он принимал ис­тинное значение, если терм Term не содержит неконкретизированных пере­менных.

7.4. Процедура substitute, описанная в данном разделе, вырабатывает только "самые внешние" подстановки, если даже есть другие варианты. Измените эту процедуру таким образом, чтобы с помощью перебора с возвратами вырабаты­вались все возможные варианты, например, как показано ниже.

7- substitute; a+b, fА+В) , new, KewTerra) .

А - а

В = Ь

NewTerm = f( new) ;

К - a+b

В - a+b

NewTerm = f( new + new)

Первоначальная версия позволяет найти только первый ответ.

7.5. Определите отношение
subsunesi Terml, Ter»2)

таким образом, чтобы оно позволяло определить, является ли выражение Terml более общим, чем выражение Тегш2. например, как показано ниже.

?- subsumes ( X, с}.

yss

'?- subsumes g(X), g[t(Y)) ).

yes

?- subsumesi f(x,x), £(a,b) ).