7 liter and 5 liter jugs to 4 liter jug puzzle with depth-first search

Question

I want to use any kind of depth-first search to solve the 7 Liter and 5 Liter to 4 Liter Puzzle in SWI-Prolog

I have no idea how I could start..

I want to get 4 Liters in a Jug at the end

solve(JUG1, JUG2) :- fill(JUG1, JUG2), swap(JUG1, JUG2).
fill(JUG1,JUG2) :- JUG1 = 7, JUG2 = 5.
%i dont know about that
swap(JUG1, JUG2) :- JUG1 = JUG2. 

Answer 1

I had the exact same problem to solve and I found my code on my PC for that:

We are using iterative deepening depth-first search to combine the advantages of a breath and depth search. With the following code we are trying possible combinations to reach our goal which is 4 liter at the end in one jug. If we find a solution we will print it accordingly.

% Iterative deepening depth-first search
dlDfs(Node, Path, DepthLimit, ReturnPath) :-
    goal(Node), reverse(Path, ReturnPath);
    DepthLimit > 0,
    adj(Node,NewNeighbor), not(member(NewNeighbor,Path)),
    L is DepthLimit-1,
    dlDfs(NewNeighbor, [NewNeighbor|Path], L, ReturnPath).

idDfsLoop(Start, D, ReturnPath) :-
    dlDfs(Start, [Start], D, ReturnPath)
    ;
    L is D+1,
    idDfsLoop(Start, L, ReturnPath).

idDfs(Start, ReturnPath) :- idDfsLoop(Start, 1, ReturnPath).

% [L,R] L is 7 liter, R is 5 liter
goal([_,4]).
goal([4,_]).

adj(X,Y) :- adj0(X,Y).

%fill up
adj0([X,Y],[7,Y]).
adj0([X,Y],[X,5]).

%Swap over to another canister
adj0([X,Y],[Z,U]) :- X+Y =< 5, Z is 0, U is X+Y ; X+Y > 5, Z is (X+Y) mod 5, U is 5.
adj0([X,Y],[Z,U]) :- X+Y =< 7, Z is X+Y, U is 0 ; X+Y > 7, Z is 7, U is (X+Y) mod 7.

%empty the cansiter
adj0([X,Y],[0,Y]).
adj0([X,Y],[X,0]).

solution(Start, Return) :- idDfs(Start, Return).

You can call the solution predicate as following:

solution([0,0], R) 

One of the solutions should be for example

R = [[0, 0], [7, 0], [2, 5], [2, 0], [0, 2], [7, 2], [4, 5]]

If you have any questions feel free to answer.