Вы можете использовать унификацию здесь вместо is/2
(что обычно используется для оценки выражений).
Например, мы можем определить перемещение от первой башни ко второй башнепри условии, что вторая башня пуста:
changeState((s([A|T1],[], T3)), s(T1, [A], T3)).
или мы можем переместить элемент во вторую башню, который не является пустым, учитывая, что верхняя часть стека является элементом, который больше:
changeState(s([A|T1], [B|T2], T3), s(T1, [A,B|T2], T3)) :-
A < B.
Выше приведено в общей сложности 12 правил: 3 источника, время 2 пункта назначения, 2 варианта (пустой пункт назначения по сравнению с непустым пунктом назначения).Это не очень элегантно.Мы можем сконструировать вспомогательный предикат, который проверяет, является ли стек назначения допустимым, с помощью:
valid_stack([], _).
valid_stack([H|_], X) :-
X < H.
, поэтому мы можем сжать два приведенных выше правила в:
changeState((s([A|T1], T2, T3)), s(T1, [A|T2], T3)) :-
valid_stack(T2, A).
Таким образом, это приведет кв шести правилах: три источника и два пункта назначения.
Таким образом, нам больше не нужно проверять ходы, поскольку, если changeState
успешен, то предлагаемый ход возможен с учетом оригиналасостояние действительно.
Однако это не полное решение (остальное я оставляю как упражнение).Вам понадобится механизм, который перечисляет возможные ходы и гарантирует, что вы не попадете в циклы (например, постоянно перемещаете диск между двумя башнями).
После использования предиката traverse/3
мы получаемсписок ходов к цели:
?- traverse(s([1,2,3,4,5,6], [], []), S, [s([1,2,3,4,5,6], [], [])]).
S = [s([1, 2, 3, 4, 5, 6], [], []), s([2, 3, 4, 5, 6], [1], []), s([3, 4, 5, 6], [1], [2]), s([1, 3, 4, 5|...], [], [2]), s([3, 4, 5|...], [], [1, 2]), s([4, 5|...], [3], [1, 2]), s([1|...], [3], [2]), s([...|...], [...|...], [...]), s(..., ..., ...)|...] [write]
S = [s([1, 2, 3, 4, 5, 6], [], []), s([2, 3, 4, 5, 6], [1], []), s([3, 4, 5, 6], [1], [2]), s([1, 3, 4, 5, 6], [], [2]), s([3, 4, 5, 6], [], [1, 2]), s([4, 5, 6], [3], [1, 2]), s([1, 4, 5, 6], [3], [2]), s([4, 5, 6], [1, 3], [2]), s([2, 4, 5, 6], [1, 3], []), s([1, 2, 4, 5, 6], [3], []), s([2, 4, 5, 6], [3], [1]), s([4, 5, 6], [2, 3], [1]), s([1, 4, 5, 6], [2, 3], []), s([4, 5, 6], [1, 2, 3], []), s([5, 6], [1, 2, 3], [4]), s([1, 5, 6], [2, 3], [4]), s([5, 6], [2, 3], [1, 4]), s([2, 5, 6], [3], [1, 4]), s([1, 2, 5, 6], [3], [4]), s([2, 5, 6], [1, 3], [4]), s([5, 6], [1, 3], [2, 4]), s([1, 5, 6], [3], [2, 4]), s([5, 6], [3], [1, 2, 4]), s([3, 5, 6], [], [1, 2, 4]), s([1, 3, 5, 6], [], [2, 4]), s([3, 5, 6], [1], [2, 4]), s([2, 3, 5, 6], [1], [4]), s([1, 2, 3, 5, 6], [], [4]), s([2, 3, 5, 6], [], [1, 4]), s([3, 5, 6], [2], [1, 4]), s([1, 3, 5, 6], [2], [4]), s([3, 5, 6], [1, 2], [4]), s([5, 6], [1, 2], [3, 4]), s([1, 5, 6], [2], [3, 4]), s([5, 6], [2], [1, 3, 4]), s([2, 5, 6], [], [1, 3, 4]), s([1, 2, 5, 6], [], [3, 4]), s([2, 5, 6], [1], [3, 4]), s([5, 6], [1], [2, 3, 4]), s([1, 5, 6], [], [2, 3, 4]), s([5, 6], [], [1, 2, 3, 4]), s([6], [5], [1, 2, 3, 4]), s([1, 6], [5], [2, 3, 4]), s([6], [1, 5], [2, 3, 4]), s([2, 6], [1, 5], [3, 4]), s([1, 2, 6], [5], [3, 4]), s([2, 6], [5], [1, 3, 4]), s([6], [2, 5], [1, 3, 4]), s([1, 6], [2, 5], [3, 4]), s([6], [1, 2, 5], [3, 4]), s([3, 6], [1, 2, 5], [4]), s([1, 3, 6], [2, 5], [4]), s([3, 6], [2, 5], [1, 4]), s([2, 3, 6], [5], [1, 4]), s([1, 2, 3, 6], [5], [4]), s([2, 3, 6], [1, 5], [4]), s([3, 6], [1, 5], [2, 4]), s([1, 3, 6], [5], [2, 4]), s([3, 6], [5], [1, 2, 4]), s([6], [3, 5], [1, 2, 4]), s([1, 6], [3, 5], [2, 4]), s([6], [1, 3, 5], [2, 4]), s([2, 6], [1, 3, 5], [4]), s([1, 2, 6], [3, 5], [4]), s([2, 6], [3, 5], [1, 4]), s([6], [2, 3, 5], [1, 4]), s([1, 6], [2, 3, 5], [4]), s([6], [1, 2, 3, 5], [4]), s([4, 6], [1, 2, 3, 5], []), s([1, 4, 6], [2, 3, 5], []), s([4, 6], [2, 3, 5], [1]), s([2, 4, 6], [3, 5], [1]), s([1, 2, 4, 6], [3, 5], []), s([2, 4, 6], [1, 3, 5], []), s([4, 6], [1, 3, 5], [2]), s([1, 4, 6], [3, 5], [2]), s([4, 6], [3, 5], [1, 2]), s([3, 4, 6], [5], [1, 2]), s([1, 3, 4, 6], [5], [2]), s([3, 4, 6], [1, 5], [2]), s([2, 3, 4, 6], [1, 5], []), s([1, 2, 3, 4, 6], [5], []), s([2, 3, 4, 6], [5], [1]), s([3, 4, 6], [2, 5], [1]), s([1, 3, 4, 6], [2, 5], []), s([3, 4, 6], [1, 2, 5], []), s([4, 6], [1, 2, 5], [3]), s([1, 4, 6], [2, 5], [3]), s([4, 6], [2, 5], [1, 3]), s([2, 4, 6], [5], [1, 3]), s([1, 2, 4, 6], [5], [3]), s([2, 4, 6], [1, 5], [3]), s([4, 6], [1, 5], [2, 3]), s([1, 4, 6], [5], [2, 3]), s([4, 6], [5], [1, 2, 3]), s([6], [4, 5], [1, 2, 3]), s([1, 6], [4, 5], [2, 3]), s([6], [1, 4, 5], [2, 3]), s([2, 6], [1, 4, 5], [3]), s([1, 2, 6], [4, 5], [3]), s([2, 6], [4, 5], [1, 3]), s([6], [2, 4, 5], [1, 3]), s([1, 6], [2, 4, 5], [3]), s([6], [1, 2, 4, 5], [3]), s([3, 6], [1, 2, 4, 5], []), s([1, 3, 6], [2, 4, 5], []), s([3, 6], [2, 4, 5], [1]), s([2, 3, 6], [4, 5], [1]), s([1, 2, 3, 6], [4, 5], []), s([2, 3, 6], [1, 4, 5], []), s([3, 6], [1, 4, 5], [2]), s([1, 3, 6], [4, 5], [2]), s([3, 6], [4, 5], [1, 2]), s([6], [3, 4, 5], [1, 2]), s([1, 6], [3, 4, 5], [2]), s([6], [1, 3, 4, 5], [2]), s([2, 6], [1, 3, 4, 5], []), s([1, 2, 6], [3, 4, 5], []), s([2, 6], [3, 4, 5], [1]), s([6], [2, 3, 4, 5], [1]), s([1, 6], [2, 3, 4, 5], []), s([6], [1, 2, 3, 4, 5], []), s([], [1, 2, 3, 4, 5], [6]), s([1], [2, 3, 4, 5], [6]), s([], [2, 3, 4, 5], [1, 6]), s([2], [3, 4, 5], [1, 6]), s([1, 2], [3, 4, 5], [6]), s([2], [1, 3, 4, 5], [6]), s([], [1, 3, 4, 5], [2, 6]), s([1], [3, 4, 5], [2, 6]), s([], [3, 4, 5], [1, 2, 6]), s([3], [4, 5], [1, 2, 6]), s([1, 3], [4, 5], [2, 6]), s([3], [1, 4, 5], [2, 6]), s([2, 3], [1, 4, 5], [6]), s([1, 2, 3], [4, 5], [6]), s([2, 3], [4, 5], [1, 6]), s([3], [2, 4, 5], [1, 6]), s([1, 3], [2, 4, 5], [6]), s([3], [1, 2, 4, 5], [6]), s([], [1, 2, 4, 5], [3, 6]), s([1], [2, 4, 5], [3, 6]), s([], [2, 4, 5], [1, 3, 6]), s([2], [4, 5], [1, 3, 6]), s([1, 2], [4, 5], [3, 6]), s([2], [1, 4, 5], [3, 6]), s([], [1, 4, 5], [2, 3, 6]), s([1], [4, 5], [2, 3, 6]), s([], [4, 5], [1, 2, 3, 6]), s([4], [5], [1, 2, 3, 6]), s([1, 4], [5], [2, 3, 6]), s([4], [1, 5], [2, 3, 6]), s([2, 4], [1, 5], [3, 6]), s([1, 2, 4], [5], [3, 6]), s([2, 4], [5], [1, 3, 6]), s([4], [2, 5], [1, 3, 6]), s([1, 4], [2, 5], [3, 6]), s([4], [1, 2, 5], [3, 6]), s([3, 4], [1, 2, 5], [6]), s([1, 3, 4], [2, 5], [6]), s([3, 4], [2, 5], [1, 6]), s([2, 3, 4], [5], [1, 6]), s([1, 2, 3, 4], [5], [6]), s([2, 3, 4], [1, 5], [6]), s([3, 4], [1, 5], [2, 6]), s([1, 3, 4], [5], [2, 6]), s([3, 4], [5], [1, 2, 6]), s([4], [3, 5], [1, 2, 6]), s([1, 4], [3, 5], [2, 6]), s([4], [1, 3, 5], [2, 6]), s([2, 4], [1, 3, 5], [6]), s([1, 2, 4], [3, 5], [6]), s([2, 4], [3, 5], [1, 6]), s([4], [2, 3, 5], [1, 6]), s([1, 4], [2, 3, 5], [6]), s([4], [1, 2, 3, 5], [6]), s([], [1, 2, 3, 5], [4, 6]), s([1], [2, 3, 5], [4, 6]), s([], [2, 3, 5], [1, 4, 6]), s([2], [3, 5], [1, 4, 6]), s([1, 2], [3, 5], [4, 6]), s([2], [1, 3, 5], [4, 6]), s([], [1, 3, 5], [2, 4, 6]), s([1], [3, 5], [2, 4, 6]), s([], [3, 5], [1, 2, 4, 6]), s([3], [5], [1, 2, 4, 6]), s([1, 3], [5], [2, 4, 6]), s([3], [1, 5], [2, 4, 6]), s([2, 3], [1, 5], [4, 6]), s([1, 2, 3], [5], [4, 6]), s([2, 3], [5], [1, 4, 6]), s([3], [2, 5], [1, 4, 6]), s([1, 3], [2, 5], [4, 6]), s([3], [1, 2, 5], [4, 6]), s([], [1, 2, 5], [3, 4, 6]), s([1], [2, 5], [3, 4, 6]), s([], [2, 5], [1, 3, 4, 6]), s([2], [5], [1, 3, 4, 6]), s([1, 2], [5], [3, 4, 6]), s([2], [1, 5], [3, 4, 6]), s([], [1, 5], [2, 3, 4, 6]), s([1], [5], [2, 3, 4, 6]), s([], [5], [1, 2, 3, 4, 6]), s([5], [], [1, 2, 3, 4, 6]), s([1, 5], [], [2, 3, 4, 6]), s([5], [1], [2, 3, 4, 6]), s([2, 5], [1], [3, 4, 6]), s([1, 2, 5], [], [3, 4, 6]), s([2, 5], [], [1, 3, 4, 6]), s([5], [2], [1, 3, 4, 6]), s([1, 5], [2], [3, 4, 6]), s([5], [1, 2], [3, 4, 6]), s([3, 5], [1, 2], [4, 6]), s([1, 3, 5], [2], [4, 6]), s([3, 5], [2], [1, 4, 6]), s([2, 3, 5], [], [1, 4, 6]), s([1, 2, 3, 5], [], [4, 6]), s([2, 3, 5], [1], [4, 6]), s([3, 5], [1], [2, 4, 6]), s([1, 3, 5], [], [2, 4, 6]), s([3, 5], [], [1, 2, 4, 6]), s([5], [3], [1, 2, 4, 6]), s([1, 5], [3], [2, 4, 6]), s([5], [1, 3], [2, 4, 6]), s([2, 5], [1, 3], [4, 6]), s([1, 2, 5], [3], [4, 6]), s([2, 5], [3], [1, 4, 6]), s([5], [2, 3], [1, 4, 6]), s([1, 5], [2, 3], [4, 6]), s([5], [1, 2, 3], [4, 6]), s([4, 5], [1, 2, 3], [6]), s([1, 4, 5], [2, 3], [6]), s([4, 5], [2, 3], [1, 6]), s([2, 4, 5], [3], [1, 6]), s([1, 2, 4, 5], [3], [6]), s([2, 4, 5], [1, 3], [6]), s([4, 5], [1, 3], [2, 6]), s([1, 4, 5], [3], [2, 6]), s([4, 5], [3], [1, 2, 6]), s([3, 4, 5], [], [1, 2, 6]), s([1, 3, 4, 5], [], [2, 6]), s([3, 4, 5], [1], [2, 6]), s([2, 3, 4, 5], [1], [6]), s([1, 2, 3, 4, 5], [], [6]), s([2, 3, 4, 5], [], [1, 6]), s([3, 4, 5], [2], [1, 6]), s([1, 3, 4, 5], [2], [6]), s([3, 4, 5], [1, 2], [6]), s([4, 5], [1, 2], [3, 6]), s([1, 4, 5], [2], [3, 6]), s([4, 5], [2], [1, 3, 6]), s([2, 4, 5], [], [1, 3, 6]), s([1, 2, 4, 5], [], [3, 6]), s([2, 4, 5], [1], [3, 6]), s([4, 5], [1], [2, 3, 6]), s([1, 4, 5], [], [2, 3, 6]), s([4, 5], [], [1, 2, 3, 6]), s([5], [4], [1, 2, 3, 6]), s([1, 5], [4], [2, 3, 6]), s([5], [1, 4], [2, 3, 6]), s([2, 5], [1, 4], [3, 6]), s([1, 2, 5], [4], [3, 6]), s([2, 5], [4], [1, 3, 6]), s([5], [2, 4], [1, 3, 6]), s([1, 5], [2, 4], [3, 6]), s([5], [1, 2, 4], [3, 6]), s([3, 5], [1, 2, 4], [6]), s([1, 3, 5], [2, 4], [6]), s([3, 5], [2, 4], [1, 6]), s([2, 3, 5], [4], [1, 6]), s([1, 2, 3, 5], [4], [6]), s([2, 3, 5], [1, 4], [6]), s([3, 5], [1, 4], [2, 6]), s([1, 3, 5], [4], [2, 6]), s([3, 5], [4], [1, 2, 6]), s([5], [3, 4], [1, 2, 6]), s([1, 5], [3, 4], [2, 6]), s([5], [1, 3, 4], [2, 6]), s([2, 5], [1, 3, 4], [6]), s([1, 2, 5], [3, 4], [6]), s([2, 5], [3, 4], [1, 6]), s([5], [2, 3, 4], [1, 6]), s([1, 5], [2, 3, 4], [6]), s([5], [1, 2, 3, 4], [6]), s([], [1, 2, 3, 4], [5, 6]), s([1], [2, 3, 4], [5, 6]), s([], [2, 3, 4], [1, 5, 6]), s([2], [3, 4], [1, 5, 6]), s([1, 2], [3, 4], [5, 6]), s([2], [1, 3, 4], [5, 6]), s([], [1, 3, 4], [2, 5, 6]), s([1], [3, 4], [2, 5, 6]), s([], [3, 4], [1, 2, 5, 6]), s([3], [4], [1, 2, 5, 6]), s([1, 3], [4], [2, 5, 6]), s([3], [1, 4], [2, 5, 6]), s([2, 3], [1, 4], [5, 6]), s([1, 2, 3], [4], [5, 6]), s([2, 3], [4], [1, 5, 6]), s([3], [2, 4], [1, 5, 6]), s([1, 3], [2, 4], [5, 6]), s([3], [1, 2, 4], [5, 6]), s([], [1, 2, 4], [3, 5, 6]), s([1], [2, 4], [3, 5, 6]), s([], [2, 4], [1, 3, 5, 6]), s([2], [4], [1, 3, 5, 6]), s([1, 2], [4], [3, 5, 6]), s([2], [1, 4], [3, 5, 6]), s([], [1, 4], [2, 3, 5, 6]), s([1], [4], [2, 3, 5, 6]), s([], [4], [1, 2, 3, 5, 6]), s([4], [], [1, 2, 3, 5, 6]), s([1, 4], [], [2, 3, 5, 6]), s([4], [1], [2, 3, 5, 6]), s([2, 4], [1], [3, 5, 6]), s([1, 2, 4], [], [3, 5, 6]), s([2, 4], [], [1, 3, 5, 6]), s([4], [2], [1, 3, 5, 6]), s([1, 4], [2], [3, 5, 6]), s([4], [1, 2], [3, 5, 6]), s([3, 4], [1, 2], [5, 6]), s([1, 3, 4], [2], [5, 6]), s([3, 4], [2], [1, 5, 6]), s([2, 3, 4], [], [1, 5, 6]), s([1, 2, 3, 4], [], [5, 6]), s([2, 3, 4], [1], [5, 6]), s([3, 4], [1], [2, 5, 6]), s([1, 3, 4], [], [2, 5, 6]), s([3, 4], [], [1, 2, 5, 6]), s([4], [3], [1, 2, 5, 6]), s([1, 4], [3], [2, 5, 6]), s([4], [1, 3], [2, 5, 6]), s([2, 4], [1, 3], [5, 6]), s([1, 2, 4], [3], [5, 6]), s([2, 4], [3], [1, 5, 6]), s([4], [2, 3], [1, 5, 6]), s([1, 4], [2, 3], [5, 6]), s([4], [1, 2, 3], [5, 6]), s([], [1, 2, 3], [4, 5, 6]), s([1], [2, 3], [4, 5, 6]), s([], [2, 3], [1, 4, 5, 6]), s([2], [3], [1, 4, 5, 6]), s([1, 2], [3], [4, 5, 6]), s([2], [1, 3], [4, 5, 6]), s([], [1, 3], [2, 4, 5, 6]), s([1], [3], [2, 4, 5, 6]), s([], [3], [1, 2, 4, 5, 6]), s([3], [], [1, 2, 4, 5, 6]), s([1, 3], [], [2, 4, 5, 6]), s([3], [1], [2, 4, 5, 6]), s([2, 3], [1], [4, 5, 6]), s([1, 2, 3], [], [4, 5, 6]), s([2, 3], [], [1, 4, 5, 6]), s([3], [2], [1, 4, 5, 6]), s([1, 3], [2], [4, 5, 6]), s([3], [1, 2], [4, 5, 6]), s([], [1, 2], [3, 4, 5, 6]), s([1], [2], [3, 4, 5, 6]), s([], [2], [1, 3, 4, 5, 6]), s([2], [], [1, 3, 4, 5, 6]), s([1, 2], [], [3, 4, 5, 6]), s([2], [1], [3, 4, 5, 6]), s([], [1], [2, 3, 4, 5, 6]), s([1], [], [2, 3, 4, 5, 6]), s([], [], [1, 2, 3, 4, 5, 6])]
В SWI-Prolog нужно нажать W , вы просите интерактивную оболочку напечатать полный список .