为何移除8容量水壶后Prolog水壶问题求解失败？

AI 小北

2026-7-20

3升/5升水壶求4升水的Prolog代码问题

原代码基于三水壶（3、5、8升）问题修改，移除8升壶后改为可填充3、5升壶，初始状态两壶均为空，目标是得到4升水，但运行后无法找到解，触发失败提示：

== Starting Search ==
Found 1 states reachable in path length 0
Computing extensions of length : 1
Found 2 states reachable in path length 1
Computing extensions of length : 2
!! Cannot extend statelist !!
!! FAILED: No plan reaches a goal !!
!! Cannot extend statelist !!
!! FAILED: No plan reaches a goal !!
true

问题代码

find_solution :-
    initial_state(Initial),
    write('== Starting Search =='), nl,
    solution([[Initial]], StateList),
    length(StateList, Len),
    Transitions is Len - 1,
    format('~n** FOUND SOLUTION of length ~p **', [Transitions]), nl,
    showlist(StateList).

% Remove the cut operator to find more than one solution.
find_solution.

% Base case for finding a solution.
solution(StateLists, StateList) :-
    member(StateList, StateLists),
    last(StateList, Last),
    goal_state(Last),
    report_progress(StateLists, final).

% Recursive rule that looks for a solution by extending each of the generated state lists to add a further state.
solution(StateLists, StateList) :-
    report_progress(StateLists, ongoing),
    extend(StateLists, Extensions),
    solution(Extensions, StateList).

solution(_, _) :-
    write('!! Cannot extend statelist !!'), nl,
    write('!! FAILED: No plan reaches a goal  !!'), nl,
    fail.

% Extend each statelist in a set of possible state lists.
extend(StateLists, ExtendedStateLists) :-
    setof(
        ExtendedStateList,
        StateList ^ Last ^ Next ^ (
            member(StateList, StateLists),
            last(StateList, Last),
            transition(Last, Next),
            legal_state(Next),
            no_loop_or_loopcheck_off(Next, StateLists),
            append(StateList, [Next], ExtendedStateList)
        ),
        ExtendedStateLists
    ).

no_loop_or_loopcheck_off(_, _) :- loopcheck(off), !.
no_loop_or_loopcheck_off(Next, StateLists) :-
    \+(already_reached(Next, StateLists)).

already_reached(State, StateLists) :-
    member(StateList, StateLists),
    member(State1, StateList),
    equivalent_states(State, State1).

showlist([]).
showlist([H | T]) :- write(H), nl, showlist(T).

report_progress(StateLists, Status) :-
    length(StateLists, NS),
    StateLists = [L | _],
    length(L, N),
    Nminus1 is N - 1,
    write('Found '), write(NS),
    write(' states reachable in path length '), write(Nminus1), nl,
    (Status = ongoing ->
        (write('Computing extensions of length : '), write(N), nl)
        ; true
    ).

%%% Initially jugs a and b are empty,
%%% State representation will be as follows:
%%% A state is a list:  [how_reached, Jugstate1, Jugstate2]
%%% Where each JugstateN is a list of the form: [jugname, capcity, content]
initial_state([initial, [a, 3, 0], [b, 5, 0]]).

%% Define goal state to accept any state where one of the
%% jugs contains 4 liters of water:
goal_state([_, [a, _, _], [b, _, 4]]).
goal_state([_, [a, _, 4], [b, _, _]]).

%%% The state transitions are "pour" operations, where the contents of
%%% one jug are poured into another jug up to the limit of the capacity
%%% of the recipient jug.
%%% There are six possible pour actions from one jug to another:
transition([_, A1], [fill_a, A2]) :- fill(A1, A2).
transition([_,B1], [fill_b, B2]) :- fill(B1, B2).
transition([_, A1, B1], [pour_a_to_b, A2, B2]) :- pour(A1, B1, A2, B2).
transition([_, A1, B1], [pour_b_to_a, A2, B2]) :- pour(B1, A1, B2, A2).


fill([Jug1, Capacity1, 0], [Jug1, Capacity1, Initial1]
    ) :-
    Initial1 is Capacity1.

%fill_a :-
%    retractall(initial_state(_)),
%    assertz(initial_state([initial, [a, 3, 0], [b, 5, 5]])).
%fill_b :-
%    retractall(initial_state(_)),
%    assertz(initial_state([initial, [a, 3, 3], [b, 5, 0]])).

%%% The pour operation is defined as follows:
% Case where there is room to pour the full contents of Jug1 to Jug2
% so Jug 1 ends up empty, and its contents are added to Jug2.
pour([Jug1, Capacity1, Initial1], [Jug2, Capacity2, Initial2], % initial jug states
     [Jug1, Capacity1, 0], [Jug2, Capacity2, Final2]            % final jug states
    ) :-
    Initial1 =< (Capacity2 - Initial2),
    Final2 is Initial1 + Initial2.

% Case where only some of Jug1 contents fit into Jug2
% Jug2 ends up full, and some water will be left in Jug1.
pour([Jug1, Capacity1, Initial1], [Jug2, Capacity2, Initial2], % initial jug states
     [Jug1, Capacity1, Final1], [Jug2, Capacity2, Capacity2]    % final jug states
    ) :-
    Initial1 > (Capacity2 - Initial2),
    Final1 is Initial1 - (Capacity2 - Initial2).

%% Define the other helper predicates
legal_state(_).             % All states that can be reached are legal
equivalent_states(X, X).    % Only identical states are equivalent.
loopcheck(on).              % Don't allow search to go into a loop.

%% Call this goal to find a solution.
%find_solution.

问题根源

核心错误是填充操作的transition规则不匹配状态结构：
状态的格式是[操作描述, 壶A状态, 壶B状态]（三个元素的列表），但原代码中fill对应的transition规则只匹配两个元素的列表，导致初始状态（三个元素）无法触发填充操作，后续搜索只能进入无效循环，最终无法找到解。

修正后的代码

find_solution :-
    initial_state(Initial),
    write('== Starting Search =='), nl,
    solution([[Initial]], StateList),
    length(StateList, Len),
    Transitions is Len - 1,
    format('~n** FOUND SOLUTION of length ~p **', [Transitions]), nl,
    showlist(StateList).

% Remove the cut operator to find more than one solution.
find_solution.

% Base case for finding a solution.
solution(StateLists, StateList) :-
    member(StateList, StateLists),
    last(StateList, Last),
    goal_state(Last),
    report_progress(StateLists, final).

% Recursive rule that looks for a solution by extending each of the generated state lists to add a further state.
solution(StateLists, StateList) :-
    report_progress(StateLists, ongoing),
    extend(StateLists, Extensions),
    solution(Extensions, StateList).

solution(_, _) :-
    write('!! Cannot extend statelist !!'), nl,
    write('!! FAILED: No plan reaches a goal  !!'), nl,
    fail.

% Extend each statelist in a set of possible state lists.
extend(StateLists, ExtendedStateLists) :-
    setof(
        ExtendedStateList,
        StateList ^ Last ^ Next ^ (
            member(StateList, StateLists),
            last(StateList, Last),
            transition(Last, Next),
            legal_state(Next),
            no_loop_or_loopcheck_off(Next, StateLists),
            append(StateList, [Next], ExtendedStateList)
        ),
        ExtendedStateLists
    ).

no_loop_or_loopcheck_off(_, _) :- loopcheck(off), !.
no_loop_or_loopcheck_off(Next, StateLists) :-
    \+(already_reached(Next, StateLists)).

already_reached(State, StateLists) :-
    member(StateList, StateLists),
    member(State1, StateList),
    equivalent_states(State, State1).

showlist([]).
showlist([H | T]) :- write(H), nl, showlist(T).

report_progress(StateLists, Status) :-
    length(StateLists, NS),
    StateLists = [L | _],
    length(L, N),
    Nminus1 is N - 1,
    write('Found '), write(NS),
    write(' states reachable in path length '), write(Nminus1), nl,
    (Status = ongoing ->
        (write('Computing extensions of length : '), write(N), nl)
        ; true
    ).

%%% Initially jugs a and b are empty,
%%% State representation will be as follows:
%%% A state is a list:  [how_reached, Jugstate1, Jugstate2]
%%% Where each JugstateN is a list of the form: [jugname, capcity, content]
initial_state([initial, [a, 3, 0], [b, 5, 0]]).

%% Define goal state to accept any state where one of the
%% jugs contains 4 liters of water:
goal_state([_, [a, _, _], [b, _, 4]]).
goal_state([_, [a, _, 4], [b, _, _]]).

%%% 修正transition规则，匹配三元素状态结构
transition([_, A1, B1], [fill_a, A2, B1]) :- fill(A1, A2).
transition([_, A1, B1], [fill_b, A1, B2]) :- fill(B1, B2).
transition([_, A1, B1], [pour_a_to_b, A2, B2]) :- pour(A1, B1, A2, B2).
transition([_, A1, B1], [pour_b_to_a, A2, B2]) :- pour(B1, A1, B2, A2).

%% 修正fill规则变量名，避免混淆
fill([Jug1, Capacity1, 0], [Jug1, Capacity1, Final1]) :-
    Final1 is Capacity1.

%%% The pour operation is defined as follows:
% Case where there is room to pour the full contents of Jug1 to Jug2
% so Jug 1 ends up empty, and its contents are added to Jug2.
pour([Jug1, Capacity1, Initial1], [Jug2, Capacity2, Initial2], % initial jug states
     [Jug1, Capacity1, 0], [Jug2, Capacity2, Final2]            % final jug states
    ) :-
    Initial1 =< (Capacity2 - Initial2),
    Final2 is Initial1 + Initial2.

% Case where only some of Jug1 contents fit into Jug2
% Jug2 ends up full, and some water will be left in Jug1.
pour([Jug1, Capacity1, Initial1], [Jug2, Capacity2, Initial2], % initial jug states
     [Jug1, Capacity1, Final1], [Jug2, Capacity2, Capacity2]    % final jug states
    ) :-
    Initial1 > (Capacity2 - Initial2),
    Final1 is Initial1 - (Capacity2 - Initial2).

%% Define the other helper predicates
legal_state(_).             % All states that can be reached are legal
equivalent_states(X, X).    % Only identical states are equivalent.
loopcheck(on).              % Don't allow search to go into a loop.

%% Call this goal to find a solution.
%find_solution.

修正说明

修正transition规则：填充操作的transition现在匹配三元素状态，填充单个壶时保留另一个壶的状态，确保状态结构一致。
优化fill规则变量名：把Initial1改为Final1，避免和初始状态变量混淆，逻辑更清晰。

修正后运行find_solution，即可找到正确的解路径。

内容的提问来源于stack exchange，提问作者nikolai nikolov

为何移除8容量水壶后Prolog水壶问题求解失败？

问题代码 #

问题根源 #

修正后的代码 #

修正说明 #

问题代码

问题根源

修正后的代码

修正说明