12. Числовий ребус.
Рішення широко відомого приклада числового ребуса
+ |
D O N A L D |
G E R A L D |
|
|
R O B E R T |
полягає в заміні всіх букв на десяткові цифри так, щоб операція підсумовування виявилася вірною. Різним буквам повинні відповідати різні цифри, інакше можливо тривіальне рішення, наприклад, всі букви можна замінити на нулі.
Визначимо наступне відношення:
sum( Nl, N2, N)
де Nl, N2 і N - три числа ребуса. Ціль sum( Nl, N2, N) є істинною, якщо існує така заміна букв цифрами, що N1+N2 = N.
Першим кроком до рішення буде вибір подання чисел Nl, N2 і N у програмі. Один зі способів - представити числа списками десяткових цифр. Наприклад, число 255 представляється списком [2,2,5]. Оскільки цифри наперед не відомі, кожна цифра позначається своєю неконкретизованою змінною. З використанням цього подання маємо формулювання:
[ D, O, N, A, L, D ] + [ G, E, R, A, L, D ] = [ R, О, B, E, R, T ]
Тепер задача в тім, щоб знайти таку конкретизацію змінних, для якої сума є вірною. Якщо відношення sum запрограмоване, рішенням задачі буде відповідь на питання
?- sum([D,O,N,A,L,D],[G,E,R,A,L,D],[R,O,В,Е,R,T).
Щоб визначити відношення sum на списках, що складаються з десяткових цифр, необхідно реалізувати в програмі правила підсумовування в десятковій системі числення. Підсумовування виконується по-разрядно, починаючи із крайнього правого молодшого розряду, і поширюється вліво, убік старших розрядів; при цьому завжди враховується цифра переносу з попереднього розряду. Крім того, необхідно передбачити використання множини доступних цифр, тих, які ще не використано для конкретизації попередніх змінних. Тому в цілому, крім трьох чисел, N1, N2 і N, потрібна ще деяка додаткова інформація (рис. 12.1):
цифра переносу, сформована до підсумовування цифр розряду;
цифра переносу, сформована після підсумовування цифр розряду;
множина цифр, доступних перед підсумовуванням;
цифри, що залишились не використаними при підсумовуванні.
Рис. 12.1. Поразрядне додавання. Відношення в показаному i-му розряді такі: D3i = (C1 + D1i + D2i) mod 10; C = (C1 + D1i + D2i) div 10 (div - цілочисельне ділення, mod – залишок від ділення).
Для формулювання відношення sum знов корисним є принцип узагальнення проблеми; для цього вводять допоміжне, більше загальне відношення suml з додатковими параметрами:
suml(N1, N2, N, C1, С, Digitsl, Digits)
де N1, N2 і N - три числа, такі ж, як у відношенні sum, C1 - цифра переносу з попереднього розряду (до підсумовування N1 і N2) і С - цифра переносу в наступний розряд (після підсумовування N1 і N2). Крім того, Dіgіtsl - список доступних цифр для конкретизації змінних у числах N1, N2 і N, a Dіgіts - список цифр, які ще не використано при конкретизації цих змінних. Приклад застосування цього відношення показаний нижче.
? – suml([H, E], [6, E], [U, S], l, l, [1, 3, 4, 7, 8, 9], Digits ).
Н = 8
Е = 3
S = 7
U = 4
Digits1 = [1, 3, 4, 7, 8, 9]
Digits = [1,9]
Цей приклад відповідає наступній операції підсумовування:
Оскільки при підборі чисел, що відповідають відношенню sum, дозволяється використати будь-які десяткові цифри, відношення sum можна визначити в термінах відношення suml у такий спосіб:
sum( N1, N2, N) :-
suml(Nl, N2, N, 0, 0, [0,1,2,3,4,5,6,7,8,9], _) .
Тепер вся складність рішення проблеми полягає у формулюванні відношення suml. Але це відношення є достатньо загальним для того, щоб визначити рекурсивно. Без втрати загальності, нехай три списки, що представляють три числа, мають однакову довжину (безумовно, що розглянутий приклад задачі задовольняє цьому обмеженню; інакше "більш коротке" число можна доповнити ліворуч нулями).
Відношення suml можна визначити двома твердженнями:
Три числа представлені порожніми списками так:
suml([ ], [ ], [ ], 0, 0, Digs, Digs).
Всі три числа мають деяку крайню ліву цифру й праворуч від неї - інші цифри. Тобто, вони мають вигляд:
[D1 | Nl], [D2 | N2], [D | N]
У цьому випадку повинні виконуватися дві умови:
а) Три числа N1, N2 і N повинні відповідати відношенню suml, формуючи при цьому деяку цифру переносу (С2) у старший розряд і залишаючи деяку підмножину невикористаних десяткових цифр Dіgs2.
б) Найстарші розряди (Dl, D2 і D) і перенос С2 повинні відповідати співвідношенням, показаним на рис. 12.1: С2, D1 і D2 сумуються, даючи в результаті D і перенос С1 уліво. Цю умову можна формулювати в програмі як відношення dіgіtsum.
Після перекладу на мову Prolog розглянутих умов, одержимо:
sum1( [D1 | N1], [D2 | N2], [D | N], С1, С, Digs1, Digs) :- sum1( Nl, N2, N, С1, С2, Digs1, Digs2), digitsum( D1, D2, С2, D, С, Digs2, Digs).
Залишається тільки визначити мовою Prolog відношення dіgіtsum. Важливим є тонкий нюанс щодо використання металогічного предиката nonvar. Змінні Dl, D2 і D повинні бути десятковими цифрами. Якщо одна із цих змінних ще не конкретизована, вона має стати конкретизованою значенням однієї із цифр списку Dіgs2. Після цього дану цифру необхідно видалити з набору доступних цифр. А якщо змінні Dl, D2 або D уже конкретизовані, то, безумовно, жодна з доступних цифр не повинна бути витрачена на їхню конкретизацію. Ця умова реалізується в програмі недетермінованою операцією видалення елемента зі списку. Якщо цей елемент не є змінною, то нічого не видаляється (конкретизація не відбувається). Реалізація цієї умови має вигляд:
del_var(Item,List,List):- nonvar( Item),!. %Елемент Item вже
конкретизований
del_var( Item, [Item [List] , List) . % Видалити голову списку
del_var(Item, [A | List], [A | List]) :-
del_var(Item, List, Listl). % Видалити елемент Item з
хвоста списку
Остаточний варіант програми для рішення числових ребусів наведено нижче. В неї включено також визначення двох ребусів. Питання щодо ребуса про DONALD'a, GERALD'a і ROBERT'a з використанням цієї програми виглядає так:
?- puzzle1( N1, N2, N), sum ( N1, N2, N).
% Програма рішення числових ребусів
sum(Nl, N2, N) :- % Числа представлені як списки цифр
sum1(Nl, N2, N,
0, 0, %Обидві цифри переносу, справа і зліва, равні 0
[0,1,2,3,4,5,6,7,6,9], _) . % Доступними є всі цифри
suml( [], [], [], 0, 0, Digits, Digits).
suml([D1|N1], [D2|N2], [D|N], Cl, C, Digsl, Digs) :-
suml( Nl, N2, N, Cl, C2, Digsl, Digs2),
digitsum( Dl, D2, C2, D, C, Digs2, Digs).
digitsum( Dl, D2, Cl, D, C, Digsl, Digs) :-
del_var(Dl,Digsl,Digs2) , % Вибір доступної цифри для Dl
del_var(D2,Digs2,Digs3), % Вибір доступної цифри для D2
del_var(D,Digs3,Digs), %Вибір доступної цифри для D
S is Dl + D2 + Cl,
D is S mod 10, % Залишок
С is S div 10. % Цілочисельне ділення
del_var(A,L,L):-nonvar(A), !. %Змінна А вже конкретизована
del_var[A,[A|L],L). % Видалити голову списку
del_var[A,[B|L],[B|Ll]):-
del_var(A,L,LI). % Видалити елемент з хвоста списку
% Деякі ребуси
puzzlel([D,O,N,A,L,D], [G,E,R,A,L,D],[R,O,B,E,R,T]).
puzzle2([O, S, E, N, D], [O, M, O, R, E], [M, O, N, E, Y]).
Іноді рішення подібних задач можна спростити, вказавши, як додаткове обмеження, цифрове значення однієї з букв (наприклад, повідомивши, що D дорівнює 5). Задачу, представлену у такій формі, можна повідомити системі Prolog з використанням відношення suml у такий спосіб:
?- suml([5,О,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], _) .
Варто зазначити, що в обох випадках є лише по одному рішень, інакше кажучи, існує єдиний спосіб заміни букв цифрами.