Лекция 25. Пролог. Решение логических задач презентация

из N дисков разного размера. Изначально все диски нанизаны на левый стержень в порядке убывания диаметра. Цель – переместить все диски на правый стержень, используя центральный как запасной. Условия:
Перемещать за один раз можно только один диск (верхний)
Нельзя класть диск на диск меньшего диаметра.

дисков на средний стержень
Перенести последний диск на правый стержень
Перенести N-1 дисков со среднего стержня на правый.

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

loc)
Clauses
hanoy(N) :- move (N, left, middle, right).
move (1, A, _ , C) :- inform (A, C), !.

B), inform (A, C), move (M, B, A, C).
inform (Loc1, Loc2) :- nl, write (“Move a disk from ”, Loc1, “ to ”, Loc2).
Goal
hanoy (3)
Результат:
Move a disk from left to right
Move a disk from left to middle
Move a disk from right to middle
Move a disk from left to right

to right
Move a disk from left to right
yes

шахматных ферзей так, чтобы ни один из них угрожал другому.
Построим модель.
Перенумеруем ряды клеток, расположенных по горизонтали и вертикали от 1 до 8. Для нумерации диагоналей поделим их на два типа:
Diagonal=8+Column-Row (тип 1)
Diagonal=Row+Column-1 (тип 2)
Для примера перенумеруем клетки квадрата 4х4

свободными, а также тех, которые заняты ферзями.
(X, Y) – пара, определяющая позицию ферзя на доске
queen = q (integer, integer)
queens = queen* - список множества позиций

опишем как единый объект:
board = board (queens, freelist, freelist, freelist, freelist)
Для примера:
пустая доска 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 ([1, 1], [2, 3, 4], [2, 3, 4], [2, 3, 4, 5, 6, 7], [2, 3, 4, 5, 6, 7])

все вертикали, горизонтали и диагонали.
Введем предикат
placeN (integer, board, board), для которого опишем правила.
Списки вертикалей и горизонталей пусты
placeN(_, board(D, [ ], [ ], X, Y), board(D, [ ], [ ], X, Y)) :-!.
Связь между двумя расстановками при добавлении ферзя:
placeN (N, Board1, Result) :- place_a_queen(N, Board1, Board2), placeN (N, Board2, Result).

ферзей.
Среди свободных горизонталей ищем ту, на которую можно поставить нового ферзя и удалить ее из списка свободных горизонталей.
findandremove (R, Rows, NewR)
Аналогично действуем для вертикалей с переменной С. С помощью R и C вычислим диагонали и будем искать их в списках свободных диагоналей.

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)

(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).

| Tail]) :- findandremove (X, Rest, Tail).
makelist (1, [1]).
makelist (N, [N | Rest]) :- N1=N-1, makelist (N1, Rest).
nextrow (Row, [Row | Rest], Rest).
goal
nqueens(5), nl, readchar (_).

Ханойских башнях
Задачу расстановки ферзей.