3 | 3 | 4 | 5 | 6 |

4 | 4 | 5 | 6 | 7 |

Мал. 9.5. Нумерація діагоналей Типу2 на шахматній досці.

Для вирішення задачі про N королев на Пролозі, ми повинні вміти встановлювати який рядок, колонка і діагональ ще не зайняті , а також вміти відмічати де вже розміщені королеви.

Позицію королеви можна описати за допомогою зазначення номера рядка та колонки:

queen = q(integer, integer) .

Такий опис задає позицію одної королеви. Для фіксації більшої кількості позицій, можемо використать список:

queens = queen* .

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

freelist = integer* .

Шахматну дошку зможемо обробляти як єдиний об'єкт, якщо зробимо наступний опис:

board = board(queens, freelist,freelist,freelist,freelist)

де чотири аргументи типу freelist задають відповідно ряди, колонки та діагоналі Типу1 і Типу2.

Наприклад, шахматну доску 4х4 без королев можна задать:

board([],[1,2,3,4],[1,2,3,4],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7]),

а шахматну доску з однією королевою в самому лівому верхньому кутку опише предикат:

board([q(1,1)],[2,3,4],[2,3,4],[1,2,3,4,5,6,7],[2,3,4,5,6,7])

Накінець, ми можемо вирішити поставлену задачу, описуючи відношення між пустою доскою і доскою з N королевами. Визначимо предикат placeN(integer, board, board) з двома фразами. Королеви розташовуються одна за одною, поки кожний рядок і кожна колонка не будуть зайняті. Тому в першій фразі два списки freerows і freecols - пусті:

placeN(_, board(D,[],[],X,Y), board(D,[],[],X,Y)):- !.

placeN(_, Board1, Rеsult):-

place_a_queen(N, Board1, Board2),

place_N(N, Board2, Result).

В другій фразі предикат place_a_guun описує зв'язок між Board1 і Board2. В Board2 на одну королеву більше, ніж в Board1. Для опису предикату можемо використати наступну декларацію:

plase_a_queen(integer, board, board)

Тому суть задачі з N королевами заключається в тому, щоб описати , як можна розмістити максимальну кількість королев на досці, починаючи з пустої доски. Реалізовувать таке поповнення королев будемо через поповнення списку новою королевою : [q(R,C) | Queens].

Для розміщення наступної королеви нам потрібно серед вільних рядів Rows знайти ряд R, в якому ми зможемо розмістити королеву. Потім видалимо R і з списку вільних рядів NewR. Цю роботу буде виконувати предикат:

findandremove( R, Row, NewR) .

Аналогічні дії ми повинні зробити і з вакантною колонкою С. Із R і C ми також можемо обчислити номера зайнятих діагоналей. А потім ми зможемо визначити чи є серед D1 і D2 вільні діагоналі.

place_a_gueen( N,

board(Queens,Rows,Columns,Dig1,Dig2),

board([q(R,C) | Queens],NewR,NewS,NewD1,NewD2)):-

findandremove( R, Rows, NewR),

findandremove( C, Columns, NewC),

D1 = N + S + R,

findandremove(D1, Diag1, NewD1),

D2 = R + S - 1,

findandremove(D2, Diag2, NewD2).

Далі ми приводимо повну програму, яка містить тільки декілька добавок. Ці добавки розраховані на те, щоб ви одним викликом:

goal: nqueens(5), могли задати пошук рішення для розміщення п'яти королев на досці 5х5.

domains

queen = q(integer, integer)

queens = queen*

freelist = integer*

board = board(queens, freelist, freelist, freelist,

freelist)

predicates

placeN(integer, board, board)

place_a_queen(integer, board, board)

nqueens(integer)

makelist(integer, freelist)

findandremove(integer, freelist, freelist)

nextrow(integer, freelist, freelist)

clauses

nqueens(N) :-

makelist(N, L),

Diagonal = N*2-1,

makelist(Diagonal, LL),

placeN(N, board([], L, L, LL, LL), Final),

write(Final).

placeN(_,

board(D, [], [], D1, D2),

board(D, [], [], D1, D2)):- !.

placeN(N, Board1, Result) :-

place_a_queen(N, Board1, Board2),

placeN(N, Board2, Result).

place_a_queen(N,

board(Queens, Rows, Columns, Diag1, Diag2),

board([q(R,C)|Queens], NewR, NewC, NewD1, NewD2)):-

nextrow(R, Rows, NewR),

findandremove(C, Columns, NewC),

D1 = N+C-R,

findandremove(D1, Diag1, NewD1),

D2 = R+C-1,

findandremove(D2, Diag2, NewD2).

findandremove(X, [X|Rest], Rest).

findandremove(X, [Y|Rest], [Y|Tail]):-

findandremove(X, Rest, Tail).

makelist(1, [1]).

makelist(N, [N|Rest]) :- N1 = N-1,

makelist(N1, Rest).

nextrow(Row, [Row|Rest], Rest).

Вправи.

9.1.Написати програму, яка моделює роботу недетермінованого скінченного автомату.

9.2.Напишіть програму, яка зливає два впорядковані списки в один впорядкований список.

9.3.Граф називається зв`язаним, якщо між довільними двома вершинами існує шлях. Нехай G=(V,E’), де E’ така підмножина Е, що

1) Т - зв`язний граф

2) в Т не має циклів

Написати предикат остдерево(G,T), де Т - остове дерево G.

9.4.Розглянемо наступну задачу планування. Маємо набір задач t1, t2, ..., які мають час виконання відповідно Т1, Т2, ... . Всі задачі потрібно обробити на m ідентичних процесорах. Кожна задача може бути вирішена на довільному процесорі, але в кожний даний момент часу кожний процесор вирішує тільки одну із задач. Між задачами існує відношення порядку, яке визначає, котрі з задач (якщо такі є), мають бути завершені, перш ніж дана задача може бути оброблена. Потрібно розподілити задачі між процесорами таким чином, щоб не порушити відношення порядку, причому так, щоб вся сукупність задач була вирішена за мінімальний час.

10.ОСОБЛИВІ ТЕХНІЧНІ ПРИЙОМИ ДЛЯ ПРОФЕСІОНАЛІВ.

10.1.Потоковий аналіз.

Нагадаємо, що ми домовлялись вхідні (відомі) аргументи предикату позначати типом вводу (і) - input, а вихідні (невідомі) аргументи позначати типом (o) - output. Зразок вхідних і вихідних аргументів в предикаті будемо називати потоковим зразком (flow pattern). Наприклад, якщо предикат викликається з двома аргументами, тоді існує чотири можливості для потокового зразку: (i,i) (i,o) (o,i) (o,o)

При компіляції програми, Пролог виконує глобальний потоковий аналіз предикатів. Він починається з основної цілі. Потім він виконує псевдорозвиток всієї програми, під час якого прив'язує потокові зразки до всіх предикатних викликів в програмі.

Потоковий аналіз досить простий; фактично ми його виконуємо при написанні програми. Ось декілька прикладів:

goal: - curcor(R,C),

R1 = R + 1,

curcor(R1,C).

В першому виклику предикату cursor дві змінні R і C - вільні; що означає - предикат cursor буде викликатися потоковим