Problem Definition

There are two containers with capacities x and y. A well containing an inexhaustible supply of water is available.

A desired amount, z of water must be obtained in large container by

completely filling up container and/or emptying one container into another or onto the ground. Possible moves are:

- filling the smaller jug from the water supply

- filling the larger jug from the water supply

- pouring out the contents of the smaller jug (onto the ground)

- pouring out the contents of the larger jug (onto the ground)

- pouring the contents of the smaller jug into the larger jug, until the larger jug is full, or the smaller jug is empty

- pouring the contents of the larger jug into the smaller jug, until the smaller jug is full, or the larger jug is empty

This is two-jugs version, three-jugs version is also popular.



Solution Idea

This problem has a naturally graph-like representation. State state can be easily implemented to CN. If we try to draw state space, elements will be like below;

-format of state : state (smallJug, largeJug).

-initial state : (0, 0).

-final state : (_, z). Any possible state that final jug value is z. (z is desired value for the problem)

Every possible move should be primitive, thus state can be change through these primitives.



Global Variables

"maxStates" specifies maximum number of states in solution path. If it is exceed, it causes failure.

"state" is a record contains values of small jug and large jug values in the current state.

"path" is an array consists of st (current state), st_name (move name) and cost (cumulative cost).

"small_jug_cap" is capacity of small jug. It is defined by user at beginning.

"large_jug_cap" is capacity of large jug. It is defined by user at beginning.

"final_value" is desired value in large jug at the end.

"pathP" is a integer value that shows next index in the solution path.

"solutionPath" is a "path" type It contains all steps in one solution.

const maxStates = 40; type state = record smallJug : integer; largeJug : integer; end; path = array [0..maxStates-1] of record st:state; st_name:String; cost:integer; end; var cost, small_jug_cap, large_jug_cap, pathP, final_value : integer; solutionPath : path; function SpiderSolutions : integer; { for CNP execution ! }


Subnets




Subnet: MainNetwork
Parameters:
Variables: var initialState:state
----------------------------------

Subnet: SubNetwork
Parameters: st:state
Variables: var newState:state
----------------------------------



Primitives


Print

After one solution is found, this primitive prints every state in solution path. (small jug, large jug, cost and movement to reach that state)


procedure Print; var i:integer; begin if FORW then begin for i := 0 to pathP-1 do begin write('smallJug = ',solutionPath[i].st.smallJug); write(', largeJug = ', solutionPath[i].st.largeJug); write(', cost = ', solutionPath[i].cost ); writeln(', move =', solutionPath[i].st_name); end; writeln(); writeln('Press Enter to see another solution'); writeln(); readln; end; end;

Initialize(var s : state)

This primitive asks user for small jug capacity, large jug capacity, desired final value for the large jug and assign them to variables.

It also adds first state to solution path. First state is small jug value = 0, final jug value = 0, cost = 0 and move = --- (none)

Parameters:

var s : state, state to be initialized


procedure Initialize(var s : state); var name:String = '---'; begin if FORW then begin writeln('Water Jug Problem - Recursive Solution'); writeln('==================================='); write('Enter small jug capacity:'); readln(small_jug_cap); write('Enter large jug capacity:'); readln(large_jug_cap); write('Enter final large jug content:'); readln(final_value); writeln(); s.smallJug := 0; s.largeJug := 0; pathP := 0; solutionPath[pathP].st := s; solutionPath[pathP].st_name := name; solutionPath[pathP].cost := 0; inc(PathP); end end;

FillSmall(s:state; var newState: state)

This primitive fills water the small jug, and it assigns "cost" and "move" variables.

Parameters:

s:state, current state to fill small operation is implemented

var:newState, final state after fill small operation


procedure FillSmall(s:state; var newState: state); var name:String = 'fs'; begin if FORW then begin newState.largeJug := s.largeJug; newState.smallJug := small_jug_cap; solutionPath[pathP].st := newState; solutionPath[pathP].st_name := name; solutionPath[pathP].cost := solutionPath[pathP-1].cost + small_jug_cap - solutionPath[pathP-1].st.smallJug; inc(pathP); FAILURE := InPath(newState) or IsFound(s); end else begin dec(pathP); end; end;

FillLarge(s:state; var newState: state)

This primitive fills water to the large jug, and it assigns "cost" and "move" variables.

Parameters:

s:state, current state to fill large operation is implemented

var:newState, final state after fill large operation


procedure FillLarge(s:state; var newState: state); var name:String = 'fl'; begin if FORW then begin newState.smallJug := s.smallJug; newState.largeJug := large_jug_cap; solutionPath[pathP].st := newState; solutionPath[pathP].st_name := name; solutionPath[pathP].cost := solutionPath[pathP-1].cost + large_jug_cap - solutionPath[pathP-1].st.largeJug; inc(pathP); FAILURE := InPath(newState) or IsFound(s); end else begin dec(pathP); end; end;

EmptyLarge(s:state; var newState: state)

This primitive pours water to ground in the large jug, and it assigns "cost" and "move" variables.

Parameters:

s:state, current state to empty large operation is implemented

var:newState, final state after empty large operation


procedure EmptyLarge(s:state; var newState: state); var name:String = 'el'; begin if FORW then begin newState.smallJug := s.smallJug; newState.largeJug := 0; solutionPath[pathP].st := newState; solutionPath[pathP].st_name := name; solutionPath[pathP].cost := solutionPath[pathP-1].cost + solutionPath[pathP-1].st.largeJug; inc(pathP); FAILURE := InPath(newState) or IsFound(s); end else begin dec(pathP); end; end;

EmptySmall(s:state; var newState: state)

This primitive pours water to ground in the small jug, and it assigns "cost" and "move" variables.

Parameters:

s:state, current state to empty small operation is implemented

var:newState, final state after empty small operation


procedure EmptySmall(s:state; var newState: state); var name:String = 'es'; begin if FORW then begin newState.largeJug := s.largeJug; newState.smallJug := 0; solutionPath[pathP].st := newState; solutionPath[pathP].st_name := name; solutionPath[pathP].cost := solutionPath[pathP-1].cost + solutionPath[pathP-1].st.smallJug; inc(pathP); FAILURE := InPath(newState) or IsFound(s); end else begin dec(pathP); end; end;

PourSmallToLarge(s:state; var newState : state)

This primitive transfers water from small jug to large jug until large jug is full or small jug is empty.

Parameters:

s:state, current state to pour small to large operation is implemented

var:newState, final state after pour small to large operation


procedure PourSmallToLarge(s:state; var newState : state); var name:String = 'psl'; cost: integer; begin if FORW then begin if(s.smallJug <= (large_jug_cap-s.largeJug)) then {No Overflow} begin cost := s.smallJug; newState.largeJug := s.largeJug + s.smallJug; newState.smallJug := 0; end else{Overflow} begin cost := large_jug_cap- s.largeJug; newState.smallJug := s.smallJug - (large_jug_cap- s.largeJug); newState.largeJug := large_jug_cap; end; solutionPath[pathP].st := newState; solutionPath[pathP].st_name := name; solutionPath[pathP].cost := solutionPath[pathP-1].cost + cost; inc(pathP); FAILURE := InPath(newState) or IsFound(s); end else begin dec(pathP); end; end;

PourLargeToSmall(s : state; var newState:state)

This primitive transfers water from large jug to small jug until small jug is full or large jug is empty.

Parameters:

s:state, current state to pour large to small operation is implemented

var:newState, final state after pour large to small operation


procedure PourLargeToSmall(s : state; var newState:state); var name:String = 'pls'; cost: integer; begin if FORW then begin if( s.largeJug <= (small_jug_cap - s.smallJug)) then {No Overflow} begin cost := s.largeJug; newState.smallJug := s.largeJug + s.smallJug; newState.largeJug := 0; end else {Overflow} begin cost := small_jug_cap - s.smallJug; newState.largeJug := s.largeJug - ( small_jug_cap - s.smallJug); newState.smallJug := small_jug_cap; end; solutionPath[pathP].st := newState; solutionPath[pathP].st_name := name; solutionPath[pathP].cost := solutionPath[pathP-1].cost + cost; inc(pathP); FAILURE := InPath(newState) or IsFound(s); end else begin dec(pathP); end; end;

isFinal

Primitive checks if the current state is final state. If it is final state program returns to

main network and print the solution.

Otherwise and program continues to search.


procedure isFinal; begin if FORW then begin if(solutionPath[pathP-1].st.largeJug <> final_value) then begin FAILURE := true; end; end end;


OtherFunctions


InPath(st:state):boolean

This function checks if current state is in the solution path. If it is in the solution path it returns false.

Thus program try another arrow to find state that not exists in solution path.

Parameters:

st:state, state to be checked


function InPath(st:state):boolean; var i, b: integer; begin i := 0; b := pathP -2; for i := 0 to b do begin if((st.smallJug = solutionPath[i].st.smallJug) AND(st.largeJug = solutionPath[i].st.largeJug )) then begin exit(true); end end; exit(false); end;

isFound(st:state) : boolean

Function checks if the current state is final state.

Parameters:

st:state, state to be checked


function isFound(st:state) : boolean; begin if(st.largeJug = final_value) then begin exit(true); end; exit(false); end;

SpiderSolutions : integer

This function to count found solutions.


function SpiderSolutions : integer; { for CNP execution ! } begin SpiderSolutions :=-123 end;