Улучшение решения задачи о ханойских башнях (Prolog)

@desengeener · Регистрация: 18.12.2020

Студворк — интернет-сервис помощи студентам

Добрый день, решаю задачу о ханойских башнях на прологе, написал ниже приведённой код, который правильно решает задачу.
Но столкнулся с желанием отобразить последовательность действий при решении более наглядно - в виде 3х списков, где каждый список - отдельный стержень.
Пример для трёх колец - [1,2,3][][], [2,3][1][], [3][1][2], [3][][1,2], [][3][1,2], [1][3][2], [1][2,3][], [][1,2,3][].

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
move(1,X,Y,_) :-
   write('Move top disk from '), write(X), write(' to '), 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).
 
Запуск: 
move(3, lift, mid, right)
Вывод: 
Move top disk from lift to mid
Move top disk from lift to right
Move top disk from mid to right
Move top disk from lift to mid
Move top disk from right to lift
Move top disk from right to mid
Move top disk from lift to mid

Как мне видится, это не так сложно. Достаточно прописать предикаты соответствия списков и колец(X,Y,Z), а далее в каждой итерации после write('Move top disk from ')... перемещать первый элемент списка X в начало списка Y, и удалять его из X.
Я не слишком хорошо дружу с Prolog'ом, у самого сделать не получается, возможно поможете, подскажите какие встроенные функции лучше использовать и как реализовать.
Отдельно хотел бы попросить о помощи Catstail, видел много ваших ответов в темах по Haskell и Prolog, очень помогли.

Добавлено через 1 час 41 минуту
Похоже, моё начальное предположение оказалось неверным, по поводу изменения списков в функции move(1,X,Y,_), ведь она не вызывает саму себя, следовательно, изменения произведённые в ней просто не сохранятся в общей рекурсивной функции.
Получается, изменение списков нужно делать в move(N,X,Y,Z), а вывод в move(1,X,Y,_).
Остался вопрос, как контролировать изменения и сопоставить списки со стрежнями(какое-то подобие свитч кейса?!).
Вот что у меня есть на данном этапе:

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
move(1,X,Y,_,[H1|T1],[H2|T2],[H3|T3]) :-
   write('Move top disk from '), write(X), write(' to '), write(Y), nl,
   write([H1|T1]), write([H2|T2]), write([H3|T3]), nl.
 
move(N,X,Y,Z,[H1|T1],[H2|T2],[H3|T3]) :-
   N>1,
   M is N-1,
   move(M,X,Z,Y,[H1|T1],[H2|T2],[H3|T3]),
   move(1,X,Y,_,[H1|T1],[H2|T2],[H3|T3]),
   move(M,Z,Y,X,[H1|T1],[H2|T2],[H3|T3]).
 
start(N,X,Y,Z) :-
    A=[1,2,3,-],
    B=[-],
    C=[-],
    write(A), write(B), write(C), nl,
    move(N,X,Y,Z,A,B,C).

@desengeener · 14.05.2023, 14:46 **[ТС]**

Разобрался, как сопоставить списки с X,Y,Z - просто при передаче аргументов в рекурсии меняю последовательность списков. Чтобы не запутаться "кто есть кто" добавил в конец каждого списка идентификатор (first, second, third).

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
move(1,X,Y,_,[H1|T1],[H2|T2],[H3|T3]) :-
   write('Move top disk from '), write(X), write(' to '), write(Y), nl,
   write([H1|T1]), write([H2|T2]), write([H3|T3]), nl.
 
move(N,X,Y,Z,[H1|T1],[H2|T2],[H3|T3]) :-
   N>1,
   M is N-1,
   move(M,X,Z,Y,[H1|T1],[H3|T3],[H2|T2]),
    %изменения здесь!?
    /* T2 = H2 + T2, H2 = H1, delete H1 */
   move(1,X,Y,_,[H1|T1],[H2|T2],[H3|T3]),
   move(M,Z,Y,X,[H3|T3],[H2|T2],[H1|T1]).
 
start(N,X,Y,Z) :-
    A=[1,2,3,'first'],
    B=['second'],
    C=['third'],
    write(A), write(B), write(C), nl,
    move(N,X,Y,Z,A,B,C).

Осталось разобраться с работой со списками, как реализовать то самое "T2 = H2 + T2, H2 = H1, delete H1" на Prolog'е

Добавлено через 3 часа 8 минут
Моё видение задачи изменилось, похоже это невозможно сделать без глобальных переменных со списками и изменением их в move(1,X,Y,_), что противоречит главному постулату функционального программирования - функции не взаимодействуют с глобальным состоянием. Я в тупике, не знаю как реализовать списковое решение. Если у кого-то получится найти адекватное решение списками на просторах интернета, дайте знать, у меня не получилось. Возможно, кто-то на энтузиазме поможет с решением, подкинет идей реализации.

@arlat · 15.05.2023, 07:45

Вывод результатов перестановок в список

Добавлено через 3 минуты
Если Вы хотите, чтобы диски были еще именованы, то это другой вопрос...

@Catstail · 18.05.2023, 12:18

desengeener, вот решение с демонстрацией промежуточных состояний:

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mklist(N,N,[N]) :- !.
mklist(N,K,[K|T]) :- K < N, K1 is K+1, mklist(N,K1,T).
 
move(1,2,[[H|I1],I2,I3],[I1,[H|I2],I3]) :-!.
move(1,3,[[H|I1],I2,I3],[I1,I2,[H|I3]]) :-!.
move(2,3,[I1,[H|I2],I3],[I1,I2,[H|I3]]) :-!.
move(2,1,[I1,[H|I2],I3],[[H|I1],I2,I3]) :-!.
move(3,2,[I1,I2,[H|I3]],[I1,[H|I2],I3]) :-!.
move(3,1,[I1,I2,[H|I3]],[[H|I1],I2,I3]) :-!.
 
h(1,From,To,Inp,Res) :- write(Inp), write(" -> "),
    move(From,To,Inp,Res), write(Res),nl,!.
h(N,From,To,Inp,Res) :- N1 is N-1, 
    Work is 6-From-To,
    h(N1,From,Work,Inp,Res1),
    write(Res1), write(" -> "),
    move(From,To,Res1,Res2), write(Res2),nl,
    h(N1,Work,To,Res2,Res),!.
 
hanoi(N,From,To) :- mklist(N,1,Start), h(N,From,To,[Start,[],[]],_).

Три диска с первого на третий:

Prolog
1
2
3
4
5
6
7
8
9
10
hanoi(3,1,3)
 
 
[[1, 2, 3], [], []] -> [[2, 3], [], [1]]
[[2, 3], [], [1]]   -> [[3], [2], [1]]
[[3], [2], [1]]     -> [[3], [1, 2], []]
[[3], [1, 2], []]   -> [[], [1, 2], [3]]
[[], [1, 2], [3]]   -> [[1], [2], [3]]
[[1], [2], [3]]     -> [[1], [], [2, 3]]
[[1], [], [2, 3]]   -> [[], [], [1, 2, 3]]

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@arlat 798 / 601 / 158 Регистрация: 07.10.2013 Сообщений: 1,330
	15.05.2023, 07:45
	Вывод результатов перестановок в список Добавлено через 3 минуты Если Вы хотите, чтобы диски были еще именованы, то это другой вопрос... 2

Улучшение решения задачи о ханойских башнях (Prolog)

Решение