Для переносу можна запропонувати наступний рекурсивний алгоритм.

* Один диск можна перенести прямо на потрібний сердечник.

* N дисків можна перемістить так:

1.Перемістить останній (N-ий) диск прямо на третій (правий) сердечник;

2.Перемістить N-1 диск на другий (середній) сердечник;

3.Перемістить прямо N-ий диск з третього сердечника на перший (лівий);

4.Перемістить N-1 диск з другого на третій;

5.Перемістить N-ий диск прямо з першого на третій сердечник;

Програма Прологу, яка вирішуз задачу про Ханойські Башні, буде використовувати три предикати:

1. hanoi з одним параметром, який характеризує загальну кількість дисків.

2. move, який описує переміщення N дисків з одного сердечника на інший, використовуючи третій сердечник, як тимчасове місцезнаходження дисків.

3. inform, відображає на екрані дисплею, як проходять переміщення.

domains

loc = right;

middle;

left

predicates

hanoi(integer)

move(integer, loc, loc, loc)

inform(loc, loc)

clauses

hanoi(N) :- move(N, left, middle, right).

move(1, A, _, C) :- inform(A, C), !.

move(N, A, B, C) :- N1=N-1,

move(N1, A, C, B),

inform(A, C),

move(N1, B, A, C).

inform(Loc1, Loc2) :-

write("\nMove a disk from ", Loc1, "to", Loc2).

Для вирішення задачі з трьома дисками, потрібно задати ціль

goal: hanoi(3).

9.6.Ділення слів на склади.

На прикладі вирішення цієї задачі продемонструємо можливості Прологу при обробці текстової інформації в редакторах.

Для вирішення задачі ділення слів на склади, будемо використовувати простий алгоритм, який базується на впорядкуванні голосних і приголосних в слові. Наприклад, розглянемо дві послідовності:

1) приголосна - голосна - приголосна. В цьому випадку, слово ділится після першої голосної:

ruler ---> ru-ler

prolog ---> pro-log

2) голосна - приголосна - приголосна. В цьому випадку , слово ділиться між двома приголосними:

number ---> num-ber

panter ---> pan-ter

Ці два правила добре застосовуються для більшості слів, але не працюють для слів типу handbook и hungry, які не підходять до жодного правила. Такі слова програма повинна обробляти спеціальним чином, наприклад використовувати бібліотеку таких слів.

Напишимо програму. Вона повинна запрошувати ввести слово, яке потрібно розбити на склади. Для застосування нашого алгоритму нам спочатку потрібно розбити слово на символи. Тому нам необхідний наступний опис:

domains

letter = symbol

word =letter*

Нам потрібно мати предикат, який визначає тип букви: голосна чи приголосна. Для розпізнання голосних використаємо набір фактів типу: vocal(a), vocal(e),...,vocal(y). Приголосна визначається як буква, яка не є голосною:

consonant(L):- not(vocal(L)).

Нам також будуть потрібні ще два предикати. Перший, типу:

append(word,word,word) і другий для перетворення стрічки символів в список символів:

string_word(string,word)

Цей предикат буде використовувати стандартний предикат frontchar, який має три параметри. Перший параметр з стрічкою, яка розбивається на дві частини: перший символ стрічки (визначається другим аргументом) і залишок стрічки (третій аргумент). Вмонтовані предикати free і bound визначають чи змінна є вільною чи зв'язною.

Зараз ми вже готові до вирішення основної задачі: визначити предикат divide, який разділяє слово на склади. divide має чотири пареметри і носить рекурсивний характер. Перший і другий аргументи визначають початкове слово, а третій і четвертий параметри визначають уже розбите слово.

Наприклад , перше правило для divide реалізується

divide(Start,[T1,T2,T3 | Rest], D, [T2,T3 | Rest]):-

vocal(T1), consonant(T2), vocal(T3),

append(Start, [T1], D),

де Start - це список першої групи символів слова, яке ми ділимо. Наступні три символи в слові задаються Т1,Т2 і Т3, тоді в Rest зберігаються символи, що залишились. Наприклад, при розбитті слова prolog, це правило задовольниться викликом:

divide([p,r], [o,l,o,g], P1,P2) ,

який перетвориться в

divide([p,r], [o,l,o, | [g]], [p,r,o], [l, o ,g ]) ,

тому що предикат append конкатенує першу голосну до кінця початкових літер слова. P1 становится прив'язаною до [p,r,o], а P2 прив'язана до [l,o,g]. Друге правило для divide реалізується в повній програмі:

domains

letter = char

word = letter*

predicates

divide(word, word, word, word)

vocal(letter)

consonant(letter)

string_word(string, word)

append(word, word, word)

repeat

goal

clearwindow,

repeat,

write("Write a multi-syllable word: "),

readln(S),

string_word(S, Word),

divide([], Word, Part1, Part2),

string_word(Syllable1, Part1),

string_word(Syllable2, Part2),

write("Division: ",Syllable1,"-",Syllable2),nl,

fail.

clauses

divide(Start, [T1, T2, T3|Rest], D1, [T2, T3|Rest]):-

vocal(T1), consonant(T2), vocal(T3), append(Start,

[T1], D1).

divide(Start, [T1, T2, T3, T4|Rest], D1,[T3, T4|Rest]):-

vocal(T1), consonant(T2), consonant(T3), vocal(T4),

append(Start, [T1, T2], D1).

divide(Start, [T1|Rest], D1, D2):-

append(Start, [T1], S),

divide(S, Rest, D1, D2).

vocal('a').vocal('e').vocal('i').

vocal('o').vocal('u').vocal('y').

consonant(B):-

not(vocal(B)), B <= 'z', 'a' <= B.

string_word("", []):-!.

string_word(Str, [H|T]):-

bound(Str), frontchar(Str, H, S), string_word(S, T).

string_word(Str, [H|T]):-

free(Str), bound(H), string_word(S, T),

frontchar(Str,H,S).

append([], L, L):-!.

append([X|L1], L2, [X|L3]) :-

append(L1, L2, L3).

repeat.

repeat :- repeat.

9.7. Задача про N королев.

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

Для вирішення задачі, пронумеруємо вертикальні та горизонтальні рядки шахматної доски від 1 до N. Для нумерації діагоналі , розділимо їх на два типи таким чином , щоб діагональ специфицифікувалась типом і номером, які обчислюються із її вертикальних і горизонтальних рядів:

Diagonal = N + Column - Row (type 1)

Diagonal = Row + Column - 1 (type 2)

Якщо ви дивитесь на шахматну доску на ряд 1 по горизонталі та колонку 1 по вертикалі з лівої сторони , тоді Tun1 розділяє діагоналлю клітку як символ похилої риски вліво (\), а Tun2 - вправо (/). Малюнок9.5. демонструє нумерацію діагоналей Tunу2 на досці 4х4.

| 1 | 2 | 3 | 4 |

1 | 1 | 2 | 3 | 4 |

2 |