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 можна визначити двома твердженнями:

1. Три числа представлені порожніми списками так:

suml([ ], [ ], [ ], 0, 0,Digs, Digs).

2. Всі три числа мають деяку крайню ліву цифру й праворуч від неї - інші цифри. Тобто, вони мають вигляд:

[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 розглянутих умов, одержимо:

sum 1([D1 | N1], [D2 | N2], [D | N], С1, С, Digs 1, Digs ):-
sum 1(Nl, N2, N, С1, С2, Digs 1, Digs 2),
digitsum (D1, D2, С2, D, С, Digs 2, 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):- % Числа представлені як списки цифр

Дата добавления: 2014-01-04