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

Var HA,HB,HC,HD,HE,HF,HG,HH : real; function SpiderSolutions : integer; { for CNP execution ! }


Subnets




Subnet: MapTraversal
Parameters:
Variables: var First:char;HFirst:real
----------------------------------

Subnet: FindSol
Parameters: S:charHS:real
Variables: var NewS : char;HNewS:real
----------------------------------



Primitives


Init(var First:char)


procedure Init(var First:char); begin if FORW then begin write('First = '); readln(First); write('Final = '); readln(Final); PathP:=1; Path[PathP]:=First; HA:=AirDist['A', Final]; HB:=AirDist['B', Final]; HC:=AirDist['C', Final]; HD:=AirDist['D', Final]; HE:=AirDist['E', Final]; HF:=AirDist['F', Final]; HG:=AirDist['G', Final]; HH:=AirDist['H', Final]; end end;

Heuristic (State:char; var HState:real)


procedure Heuristic (State:char; var HState:real) ; {heuristic function} begin if FORW then begin HState:=AirDist[State, Final]; end; end;

IsFinal(City:char)


procedure IsFinal(City:char) ; begin if FORW then FAILURE := City<>Final; end;

Print


procedure Print; var i:byte; begin if FORW then begin write('Found path = '); for i:=1 to PathP do write(Path[i],' '); writeln(' '); readln; end end;

Connection(City, NextCity:char; var NewCity: char)


procedure Connection(City, NextCity:char; var NewCity: char); function InPath(c:char):boolean; var i:byte; begin i:=1; while (i<=PathP) and (c<>Path[i]) do inc(i); InPath:= i<=PathP; end;

Add(City:char)


procedure Add(City:char); begin if FORW then begin inc(PathP); Path[PathP]:=City; end else dec(PathP); end;


OtherFunctions


SpiderSolutions : integer


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