Числовий ребус

Member(h(_,_,_,zebra,_),S), member(h(_,_,_,_,water),S).

Neighbour(h(_,_,_,horse,_),h(_,diplomat,_,_,_),S),

Neighbour(h(_,_,_,fox,_),h(_,doctor,_,_,_),S),

Member(h(_,musician,_,_,juice),S),

Member(h(_,diplomat,yellow,_,_),S),

Member(h(_,sculptor,_,snails,_),S),

Next(h(_,_,white,_,_),h(_,_,green,_,_),S),

Member(h(_,_,green,_,coffee),S),

Member(h(italian,_,_,_,tea),S),

Member(h(japanese,painter,_,_,_),S),

Member(h(spanish,_,_,dog,_),S),

Member(h(english,_,red,_,_),S),

neighbour(X1,X2,L):- next(X1,X2,L); next(X2,X1,L).

Найсуттєвіші ознаки наведеного опису задачі:

· У даному прикладі відсутній предикат генерації – перебір здійснюється предикатами member неявно.

· Рішення задачі виходить винятково декларативним.

· Неявний перебір використовує метод гілок і границь.

· Генерація чергової порції рішень проводиться після часткової конкретизації розв'язку.

Рішення широко відомого приклада числового ребуса

+	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-му
розряді такі: D_3i = (C1 + D_1i + D_2i) mod 10; C = (C1 + D_1i + D_2i)
div 10 (div - цілочисельне ділення, mod – залишок від ділення).

Для формулювання відношення sum знов корисним є принцип узагальнення проблеми; для цього вводять допоміжне, більше загальне відношення suml з додатковими параметрами:

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