Unexpected Behavior in Prolog Water Sort Puzzle Solver: Duplicate Results, Persistent State, and GoalCheck Inconsistencies - Sta

admin管理员组

文章数量:1122832

I have been working on a side program that solves water-sorting puzzles using Prolog. the program runs normally yet, there are some weird questionable behaviors. we shall make the following constraints about our problem. 1- We have 3 bottles only.

2- We have 2 colors only.

3- The goal state is when 2 bottles are filled and each one of them has a uniform color.

:- include('KB.pl').
:- dynamic bottle/4.



% Bottle 1: Top layer is b, bottom layer is r, initial state is s0
bottle(1, b, r, s0).

% Bottle 2: Top layer is b, bottom layer is r, initial state is s0
bottle(2, b, r, s0).

% Bottle 3: Top layer is e (empty), bottom layer is e, initial state is s0
bottle(3, e, e, s0).

% Valid pour action: The action is valid if:
% 1. The destination bottle is not full (i.e., its top and bottom colors are not the same).
% 2. The source bottle is not empty (i.e., it has a color in the top layer).
% 3. The top color layers of both the source and destination bottles are the same.
% 4. If the destination bottle is empty, pouring is always valid as long as the source bottle is not empty.

validPour(Source, Destination, S) :-
    bottle(Source, TopColor, BotColorSrc, S),  % Get the top and bottom colors of the source bottle
    bottle(Destination, TopColorDest, BotColorDest, S), % Get the top and bottom colors of the destination bottle
    \+ isEmpty(Source, S),
    (
    (TopColor \= e ,(((TopColorDest == e, BotColorDest == TopColor)); isEmpty(Destination, S)))
    ;
    (TopColor == e, BotColorSrc \= e ,(((TopColorDest == e, BotColorDest == BotColorSrc)) ; isEmpty(Destination, S)))
    ).




isEmpty(Bottle, S) :- bottle(Bottle, e, e, S).

% Pour action: Pour from bottle i to bottle j
pour(Source, Destination, Third, S, NextState) :- 
         ( 
     bottle(Source, Color1, BotColorSrc, S); bottle(Source, e, Color1, S)),  % Get the top color of the source bottle
    bottle(Destination, Color2, BotColorDest, S),  % Get the top and bottom colors of the destination bottle
    bottle(Third, Color3, BotColorThird, S),  % Get the top and bottom colors of the third bottle
    NextState=result(pour(Source, Destination), S), 
    Color1 \= e,                            % Ensure the source bottle is not empty
    (   isEmpty(Destination, S) ->          % If the destination is empty
        assert(bottle(Destination, e, Color1, NextState))   % Add the new top and bottom color from the source
    ;
        (   BotColorDest \= e, BotColorDest == Color1, Color2 == e , % If the destination is not empty
            assert(bottle(Destination, Color1, BotColorDest, NextState)) % Add the new top color and retain the bottom color
        )
    ), 
    % Update the source bottle to reflect the removal of its top color
    (   bottle(Source, Color1, BotColorSrc, S) -> 
        assert(bottle(Source, e, BotColorSrc, NextState)) ; 
        bottle(Source, e, Color1, S) -> 
        assert(bottle(Source, e, e, NextState))
    ),
    assert(bottle(Third, Color3, BotColorThird, NextState)).   
   

goalCheck(S) :- 
      % Case 1: Bottles 1 and 2 are uniform and full, Bottle 3 is empty
    (bottle(1, C1, C1, S),
     bottle(2, C2, C2, S),
     bottle(3, e, e, S),
     C1 \= e, C2 \= e, C1 \= C2);

    % Case 2: Bottles 2 and 3 are uniform and full, Bottle 1 is empty
    (bottle(2, C1, C1, S),
     bottle(3, C2, C2, S),
     bottle(1, e, e, S),
     C1 \= e, C2 \= e, C1 \= C2);

    % Case 3: Bottles 1 and 3 are uniform and full, Bottle 2 is empty
    (bottle(1, C1, C1, S),
     bottle(3, C2, C2, S),
     bottle(2, e, e, S),
     C1 \= e, C2 \= e, C1 \= C2).
% Search predicate to find the goal state
%search(S) :-
  % goalCheck(S), halt.  % Base case: if the goal is already achieved.

search(S) :-
    (goalCheck(S), !);  ( 
        (validPour(1, 2, S)-> pour(1, 2,3, S,NextState),search(NextState));
        (validPour(1, 3, S)-> pour(1, 3,2, S,NextState),search(NextState));
        (validPour(3, 1, S)-> pour(3, 1,2, S,NextState),search(NextState));
        (validPour(3, 2, S)-> pour(3, 2,1, S,NextState),search(NextState));
        (validPour(2, 3, S)-> pour(2, 3,1, S,NextState),search(NextState));
        (validPour(2, 1, S)-> pour(2, 1,3, S,NextState),search(NextState))
    ).

goal(S) :-
    search(S).

1- When I try to query goal(S), the first time it returns 'S=s0' then if I press the semicolon I get 'false'. when I query it again I get the normal result which will look something like 'S = result(pour(1, 2), result(pour(2, 3), result(pour(1, 3), s0))).'.

2- If I query goalCheck (S) after goal (S), I get 'S= result(pour ..... etc'), yet I should get true or false only according to the implementation of goalCheck(S). (If I just consulted the file and then ran goalCheck(S), I get false.)

3—If I changed the bottle content and re-consulted the file, I got the same result as if I had not changed the bottles. I have to halt and then re-consult to have an updated result.

I appreciate any help you can provide.

I was retracting bottles(removed it) and tried to eliminate the 2 search(S):- predicates.

I have been working on a side program that solves water-sorting puzzles using Prolog. the program runs normally yet, there are some weird questionable behaviors. we shall make the following constraints about our problem. 1- We have 3 bottles only.

2- We have 2 colors only.

3- The goal state is when 2 bottles are filled and each one of them has a uniform color.

:- include('KB.pl').
:- dynamic bottle/4.



% Bottle 1: Top layer is b, bottom layer is r, initial state is s0
bottle(1, b, r, s0).

% Bottle 2: Top layer is b, bottom layer is r, initial state is s0
bottle(2, b, r, s0).

% Bottle 3: Top layer is e (empty), bottom layer is e, initial state is s0
bottle(3, e, e, s0).

% Valid pour action: The action is valid if:
% 1. The destination bottle is not full (i.e., its top and bottom colors are not the same).
% 2. The source bottle is not empty (i.e., it has a color in the top layer).
% 3. The top color layers of both the source and destination bottles are the same.
% 4. If the destination bottle is empty, pouring is always valid as long as the source bottle is not empty.

validPour(Source, Destination, S) :-
    bottle(Source, TopColor, BotColorSrc, S),  % Get the top and bottom colors of the source bottle
    bottle(Destination, TopColorDest, BotColorDest, S), % Get the top and bottom colors of the destination bottle
    \+ isEmpty(Source, S),
    (
    (TopColor \= e ,(((TopColorDest == e, BotColorDest == TopColor)); isEmpty(Destination, S)))
    ;
    (TopColor == e, BotColorSrc \= e ,(((TopColorDest == e, BotColorDest == BotColorSrc)) ; isEmpty(Destination, S)))
    ).




isEmpty(Bottle, S) :- bottle(Bottle, e, e, S).

% Pour action: Pour from bottle i to bottle j
pour(Source, Destination, Third, S, NextState) :- 
         ( 
     bottle(Source, Color1, BotColorSrc, S); bottle(Source, e, Color1, S)),  % Get the top color of the source bottle
    bottle(Destination, Color2, BotColorDest, S),  % Get the top and bottom colors of the destination bottle
    bottle(Third, Color3, BotColorThird, S),  % Get the top and bottom colors of the third bottle
    NextState=result(pour(Source, Destination), S), 
    Color1 \= e,                            % Ensure the source bottle is not empty
    (   isEmpty(Destination, S) ->          % If the destination is empty
        assert(bottle(Destination, e, Color1, NextState))   % Add the new top and bottom color from the source
    ;
        (   BotColorDest \= e, BotColorDest == Color1, Color2 == e , % If the destination is not empty
            assert(bottle(Destination, Color1, BotColorDest, NextState)) % Add the new top color and retain the bottom color
        )
    ), 
    % Update the source bottle to reflect the removal of its top color
    (   bottle(Source, Color1, BotColorSrc, S) -> 
        assert(bottle(Source, e, BotColorSrc, NextState)) ; 
        bottle(Source, e, Color1, S) -> 
        assert(bottle(Source, e, e, NextState))
    ),
    assert(bottle(Third, Color3, BotColorThird, NextState)).   
   

goalCheck(S) :- 
      % Case 1: Bottles 1 and 2 are uniform and full, Bottle 3 is empty
    (bottle(1, C1, C1, S),
     bottle(2, C2, C2, S),
     bottle(3, e, e, S),
     C1 \= e, C2 \= e, C1 \= C2);

    % Case 2: Bottles 2 and 3 are uniform and full, Bottle 1 is empty
    (bottle(2, C1, C1, S),
     bottle(3, C2, C2, S),
     bottle(1, e, e, S),
     C1 \= e, C2 \= e, C1 \= C2);

    % Case 3: Bottles 1 and 3 are uniform and full, Bottle 2 is empty
    (bottle(1, C1, C1, S),
     bottle(3, C2, C2, S),
     bottle(2, e, e, S),
     C1 \= e, C2 \= e, C1 \= C2).
% Search predicate to find the goal state
%search(S) :-
  % goalCheck(S), halt.  % Base case: if the goal is already achieved.

search(S) :-
    (goalCheck(S), !);  ( 
        (validPour(1, 2, S)-> pour(1, 2,3, S,NextState),search(NextState));
        (validPour(1, 3, S)-> pour(1, 3,2, S,NextState),search(NextState));
        (validPour(3, 1, S)-> pour(3, 1,2, S,NextState),search(NextState));
        (validPour(3, 2, S)-> pour(3, 2,1, S,NextState),search(NextState));
        (validPour(2, 3, S)-> pour(2, 3,1, S,NextState),search(NextState));
        (validPour(2, 1, S)-> pour(2, 1,3, S,NextState),search(NextState))
    ).

goal(S) :-
    search(S).

1- When I try to query goal(S), the first time it returns 'S=s0' then if I press the semicolon I get 'false'. when I query it again I get the normal result which will look something like 'S = result(pour(1, 2), result(pour(2, 3), result(pour(1, 3), s0))).'.

2- If I query goalCheck (S) after goal (S), I get 'S= result(pour ..... etc'), yet I should get true or false only according to the implementation of goalCheck(S). (If I just consulted the file and then ran goalCheck(S), I get false.)

3—If I changed the bottle content and re-consulted the file, I got the same result as if I had not changed the bottles. I have to halt and then re-consult to have an updated result.

I appreciate any help you can provide.

I was retracting bottles(removed it) and tried to eliminate the 2 search(S):- predicates.

• prolog
• water-jug-problem

Share Improve this question Follow edited Nov 21, 2024 at 13:18 false 10.2k1313 gold badges109109 silver badges215215 bronze badges asked Nov 21, 2024 at 13:03 Ahmed HaithamAhmed Haitham 322 bronze badges 3

• I suggest rewriting without using assert. You are manipulating the database runtime essentially your prolog code is very procedural. Execution order matters for example. All of your questions are related to the behavior of assert. – Mo... Commented Nov 21, 2024 at 16:48
• I don't quite understand shall I just remove assert from the whole code ? if I removed assert will it maintain the same functionality ? – Ahmed Haitham Commented Nov 21, 2024 at 17:01
• You shouldn't use assert in your code. No, removing assert won't fix your code but your code was not correct in the first place. You're not retracting the state so your code is returning the intermediate state as a solution. For example, when you're asserting, assert(x(1)). assert(x(2)). assert(x(3)). ... -? x(X) X = 1; X = 2; X= 3. It doesn't overwrite the original fact. TLDR, you have rewrite the code. Instead pass your state as an argument. At least, you have to retract once the state is manipulated and you have to build a solution in the argument. – Mo... Commented Nov 21, 2024 at 17:14

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 1

I am not too sure if I understood the puzzle correctly. But, the problem is assert where you're manipulating the state directly. Then, order execution will change as the fact changes every time the code runs.

Instead, you will just pass around a state and build a solution.

Here is the example code without using assert and pass around state meaning. This is a typical BFS you can just modify the goal state.

% Find a path from the initial state to the goal state using BFS.
solve(Actions) :-
  InitialState = [bottle(1, b, r), bottle(2, b, r), bottle(3, empty, empty)],
  format('Initial state: ~w~n', [InitialState]),
  bfs([[InitialState, []]], [], Actions).

% Breadth-first search for the optimal path.
bfs([[State, ReversedActions]|_], _, Actions) :-
  goal_reached(State),
  reverse(ReversedActions, Actions),
  !,
  format('Optimal goal reached: ~w~n', [State]).
bfs([[State, Actions]|Queue], VisitedStates, Solution) :-
  findall([NextState, [Action|Actions]],
          (valid_pour(State, NextState, Action), \+ member(NextState, VisitedStates)),
          NewStates),
  append(Queue, NewStates, NewQueue),
  bfs(NewQueue, [State|VisitedStates], Solution).

% Check if the goal state is reached.
goal_reached(State) :-
  findall(Color, (member(bottle(_, Color, Color), State), Color \= empty), Colors),
  length(Colors, N),
  N >= 2.

% Validate and perform a pour from one bottle to another.
valid_pour(State, NextState, Action) :-
  member(SrcBottle, State),
  member(DstBottle, State),
  SrcBottle \= DstBottle,
  can_pour(SrcBottle, DstBottle),
  perform_pour(State, SrcBottle, DstBottle, NextState),
  bottle_id(SrcBottle, SrcId),
  bottle_id(DstBottle, DstId),
  Action = pour(SrcId, DstId).

bottle_id(bottle(Id, _, _), Id).

% Check if the source bottle is not empty and the destination bottle is not full or has the same color.
can_pour(SrcBottle, DstBottle) :-
  \+ is_empty(SrcBottle),
  (not_full_or_same_color(DstBottle, SrcBottle)).

% Check if the bottle is empty.
is_empty(bottle(_, empty, empty)).

% Check if the bottle is full.
is_full(bottle(_, Color1, Color2)) :- Color1 \= empty, Color2 \= empty.

% Check if the destination bottle is not full or has the same color.
not_full_or_same_color(Bottle2, Bottle1) :-
  \+ is_full(Bottle2);
  bottle_color(Bottle1, SrcColor),
  bottle_color(Bottle2, DstColor),
  SrcColor = DstColor.

% Check the color of the remaining water.
bottle_color(bottle(_, Color, _), Color) :- Color \= empty.
bottle_color(bottle(_, empty, Color), Color) :- Color \= empty.

% Perform the pour operation.
perform_pour(State, Src, Dst, NextState) :-
  delete(Src, State, State1),
  delete(Dst, State1, State2),
  remove_water(Src, NewSrc, Color),
  add_water(Dst, NewDst, Color),
  insert(NewSrc, State2, State3),
  insert(NewDst, State3, NextState).

% Remove the water from the source bottle.
remove_water(bottle(Id, Color1, Color2), bottle(Id, empty, Color2), Color1).
remove_water(bottle(Id, empty, Color1), bottle(Id, empty, empty), Color1).

% Add the water to the destination bottle.
add_water(bottle(Id, empty, empty), bottle(Id, empty, Color), Color).
add_water(bottle(Id, empty, Color0), bottle(Id, Color, Color0), Color) :- Color0 \= empty.

% Insert an element into a list.
insert(Element, List, Result) :-
  Result = [Element|List].

% Delete an element from a list.
delete(Element, List, Result) :-
  select(Element, List, Result).

Then

?- solve(Actions).
Initial state: [bottle(1,b,r),bottle(2,b,r),bottle(3,empty,empty)]
Optimal goal reached: [bottle(1,r,r),bottle(2,empty,empty),bottle(3,b,b)]
Actions = [pour(1, 3), pour(2, 3), pour(2, 1)].

本文标签：