13. Логические задачи (головоломки) Пример 13.1. Перестановка кубиков

Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как показано на рисунке. На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо на стол, либо на другой кубик. Для того, чтобы построить требуемый план, мы должны отыскать последовательность ходов, реализующую заданную трансформацию.

% удаление элемента Х из списка, результат - в L

del(X, [X | L], L).

del(X, [Y | L], [Y | L1]):- del(X, L, L1).

% состояние: s(X, Y) где X - предыдущий шаг, Y - последующий допусимый шаг

% Перенести верхний кубик Top1 на столбик Stack2

s( Stacks, [Stackl, [Top1 | Stack2] | OtherStacks] ) :-

del([Top1 | Stackl], Stacks, Stacksl), % Найти первый столбик

del(Stack2, Stacksl, OtherStacks). % Найти второй столбик

goal(Situation):-

member([a,b,c], Situation). % Целевое состояние:

% Вызов поиска:

% solve([[c,a,b], [], []], Solution). % Начальное сотояние

/*

solve(N, [N]):- goal(N).

solve(N, [N | Sol1]):-

s(N, N1),

solve(N1, Sol1).

% solve(Node, Solution):

% Решение Solution представляет собой ациклический путь (узлы в

% котором указаны в обратном порядке) между узлом Node и целью

solve(Node, Solution) :-

depthfirst( [], Node, Solution).

% depthfirst( Path, Node, Solution):

% решение Solution формируется в результате продления пути

% [Node | Path] до целевого узла

depthfirst( Path, Node, [Node | Path] ) :-

goal( Node).

depthfirst( Path, Node, Sol) :-

s( Node, Node1),

not member( Node1, Path), % Предотвращение цикла

depthfirst( [Node | Path], Node1, Sol).

*/

solve( Start, Solution) :- breadthfirst( [ [Start] | Z] - Z, Solution).

breadthfirst( [ [Node | Path] | _] - _, [Node | Path] ) :- goal( Node).

breadthfirst( [Path | Paths] - Z, Solution) :-

extend( Path, NewPaths),

conc( NewPaths, Z1, Z), % Добавить NewPaths в конец

Paths \== Z1, % Множество возможных путей – не пустое

breadthfirst( Paths - Z1, Solution).

Пример 13.2. Ханойский башни

Имеется 3 стержня и N дисков разного диаметра, насаженные последовательно на 1 из стержней. Требуется переместить диски с одного стержня на другой, используя один стержень как вспомогательный.

Правила перемещения дисков:

• разрешается снимать со стержня только верхний диск,

• запрещается класть больший диск на меньший,

• при каждом ходе передвигается только один диск.

% move(число_дисков, откуда, куда, через)

move(1,X,Y,_) :-

write('Перемещаем диск с '),

write(X), write(' стержня на '),

write(Y), nl.

move(N,X,Y,Z) :-

N>1,

M is N-1,

move(M,X,Z,Y),

move(1,X,Y,_),

move(M,Z,Y,X).

% Предикат для запуска поиска решений задачи размерности X

hanoi(X):- move(X, 'лев.', 'прав.', 'центр.').

% Запуск поиска решения:

% ?- hanoi(4).