Почему программа не работает так, как нужно?

Question

[pshevnin]

Добрый день, написал на прологе решение задачи миссионеров и людоедов, но оно не работает так как нужно. Я не очень хорошо пишу на прологе, но сейчас не могу найти баг уже пару дней. Вот код:

% Правила для проверки состояния на допустимость
valid_state(state(Location, Missionaries, Cannibals)) :-
    % Условия проверки на допустимость
    % 1. Количество миссионеров и людоедов должно быть неотрицательным

    
    Missionaries >= 0,
    Cannibals >= 0,
    % 2. Количество миссионеров и людоедов не должно превышать 3
    
    Missionaries =< 3,
    Cannibals =< 3,

    % 3. На каждом берегу должно быть либо больше миссионеров, чем людоедов, либо не быть миссионеров вообще

    (Missionaries >= Cannibals ; Missionaries = 0),
    % 4. То же самое для противоположного берега
    (3 - Missionaries >= 3 - Cannibals ; 3 - Missionaries = 0).

    

% Правила для перемещения
move(state(east, M1, C1), state(west, M1_new, C1_new)) :-
    between(0, 2, X), % Количество миссионеров, пересекающих реку (от 0 до 2)
    MaxCannibals is 2 - X, % Максимальное количество каннибалов в лодке, учитывая текущее количество миссионеров
    between(0, MaxCannibals, Y), % Количество людоедов, пересекающих реку (от 0 до максимально допустимого)
    
    writeln('Current state: (in move)'), writeln(state(east, M1, C1)),
    writeln('Moving from east to west'),

    (X + Y > 0),
    M1_new is 3 - (M1 - X),
    C1_new is 3 - (C1 - Y),
    
    valid_state(state(west, M1_new, C1_new)).
    

move(state(west, M2, C2), state(east, M2_new, C2_new)) :-
    between(0, 2, X), % Количество миссионеров, пересекающих реку (от 0 до 2)
    MaxCannibals is 2 - X, % Максимальное количество каннибалов в лодке, учитывая текущее количество миссионеров
    between(0, MaxCannibals, Y), % Количество людоедов, пересекающих реку (от 0 до максимально допустимого)

    writeln('Current state: (in move)'), writeln(state(west, M2, C2)),
    writeln('Moving from west to east'),
    (X + Y > 0),
    M2_new is 3 - (M2 - X),
    C2_new is 3 - (C2 - Y),
    
    valid_state(state(east, M2_new, C2_new)).
    

breadth_first_search([Goal|_], Goal, _, [Goal]) :-
    writeln('Goal state reached!').

breadth_first_search([State|States], Goal, Visited, [State|Path]) :-
    % Выводим информацию о текущем состоянии
    writeln('===> Entering breadth_first_search/4 with state: '), writeln(State),
    % Выводим информацию о состояниях в списке посещенных
    writeln('Visited states so far: '), writeln(Visited),
    % Выводим информацию о состояниях в очереди

    % Проверяем, что состояние еще не посещалось
    \+ member(State, Visited),
    % Вывод текущего состояния
    writeln('Current state: ======='), writeln(State),

    % Переход в новые состояния
    findall(NextState, (move(State, NextState), \+ member(NextState, States)), NextStates),
   
    % Вывод новых состояний
    writeln('Adding new states to the queue...'),
    writeln('Next states: '), writeln(NextStates),

    % Добавление новых состояний в очередь
    append(States, NextStates, NewStates),
    % Добавление текущего состояния в список посещенных
    

    % Вывод обновленной очереди
    writeln('Current states in queue: '), writeln(NewStates),
    append(Visited, [State], UpdatedVisited),
    breadth_first_search(NewStates, Goal, UpdatedVisited, Path).
    
    
% Предикат для нахождения пути от начального состояния до целевого
find_path(Path) :-
    writeln('Starting breadth-first search...'),
    breadth_first_search([state(east, 3, 3)], state(west, 3, 3), [], Path),
    writeln('Path found: '), writeln(Path). % Выводим найденный путь

Вот часть того, что код выводит, путь он найти не может. У меня есть некоторое предположение, что это связано с посещёнными состояниями, потому что если я убираю проверку на посещённые состояния, программа очень долго работает, но находит возможный путь решения.

Moving from west to east
Current state: (in move)
state(west,0,2)
Moving from west to east
Current state: (in move)
state(west,0,2)
Moving from west to east
Adding new states to the queue...
Next states: 
[]
Current states in queue: 
[state(west,1,1),state(east,3,3)]
===> Entering breadth_first_search/4 with state: 
state(west,1,1)
Visited states so far: 
[state(east,3,3),state(west,0,1),state(west,0,2)]
Current state: =======
state(west,1,1)
Current state: (in move)
state(west,1,1)
Moving from west to east
Current state: (in move)
state(west,1,1)
Moving from west to east
Current state: (in move)
state(west,1,1)
Moving from west to east
Current state: (in move)
state(west,1,1)
Moving from west to east
Current state: (in move)
state(west,1,1)
Moving from west to east
Current state: (in move)
state(west,1,1)
Moving from west to east
Adding new states to the queue...
Next states: 
[]
Current states in queue: 
[state(east,3,3)]
===> Entering breadth_first_search/4 with state: 
state(east,3,3)
Visited states so far: 
[state(east,3,3),state(west,0,1),state(west,0,2),state(west,1,1)]
false.

Заранее спасибо за помощь!