Ханойские башни.

Древняя игра "Ханойские башни" состоит из набора деревянных дисков и

трех стержней, прикрепленных к основанию. Каждый диск имеет свой диаметр,

а в середине отверстие достаточное, чтобы диск можно было надеть на стер-

жень. В начале игры все диски надеты на левый стержень в том порядке, как

это показано на рис. 18-4.

п п п

=== п п

===== п п

======= п п

========= п п

=========== п п

============= п п

------------------------------------------------------------

Рис. 18-4 Ханойские башни.

Цель игры заключается в том, чтобы перенести все диски с левого на

правый стержень, по одному диску за раз, при этом ни один больший диск не

может ставиться сверху меньшего по диаметру. Эту задачу можно легко вы-

полнить для одного или двух дисков, но когда число дисков становится

больше трех, задача становится более сложной.

Для этой игры есть одна простая стратегия:

- Один диск перемещается непосредственно.

- N дисков переносятся в три этапа:

- перенести N-1 дисков на средний стержень

- перенести последний диск на первый стержень

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

В нашей программе для игры в Ханойские башни есть три предиката:

1. Предикат hanoi с одним параметром, указывающим со сколькими

дисками мы играем;

2. Предикат move, с помощью которого мы описываем перенос N

дисков с одного стержня на другой, используя третий стержень в

качестве промежуточного места для дисков;

3. Предикат inform, который указывает на действие, выполняемое

с конкретным диском.

/* Program CH18EX05.PRO */

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

Для решения задачи Ханойские башни с тремя дисками введем целевое

утверждение hanoi(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 middle to left

Move a disk from middle to right

Move a disk from left to right