Definition:
Some jugs are given which should have non-calibrated properties. At least any one of the jugs should have filled with water. Then the process through which we can divide the whole water into different jugs according to the question can be called as water jug problem.
Procedure:
Suppose that you are given 3 jugs A,B,C with capacities 8,5 and 3 liters respectively but are not calibrated (i.e. no measuring mark will be there). Jug A is filled with 8 liters of water. By a series of pouring back and forth among the 3 jugs, divide the 8 liters into 2 equal parts i.e. 4 liters in jug A and 4 liters in jug B. How?
In this problem, the start state is that the jug A will contain 8 liters water whereas jug B and jug C will be empty. The production rules involve filling a jug with some amount of water, taking from the jug A.
The search will be finding the sequence of production rules which transform the initial state to final state. The state space for this problem can be described by set of ordered pairs of three variables (A, B, C) where variable A represents the 8 liter jug, variable B represents the 5 liter and variable C represents the 3 liters jug respectively.
The production rules are formulated as follows:
Step 1:
In this step, the initial state will be (8, 0, 0) as the jug B and jug C will be empty. So the water of jug A can be poured like:
- (5, 0, 3) means 3 liters to jug C and 5 liters will remain in jug A.
- (3, 5, 0) means 5 liters to jug B and 3 liters will be in jug A.
- (0, 5, 3) means 5 liters to jug B and 3 liters to jug C and jug C and jug A will be empty.
Step2:
In this step, start with the first current state of step-1 i.e. (5, 0, 3). This state can only be implemented by pouring the 3 liters water of jug C into jug B. so the state will be (5, 3, 0).
Next, come to the second
current state of step-1 i.e. (3, 5, 0). This state can be implemented by only pouring the 5 liters water of jug B into jug C. So the remaining water in jug B will be 2 liters. So the state will be (3, 2, 3).
Finally come to the third current state of step-1 i.e. (0, 5, 3). But from this state no more state can be implemented because after implementing we may get (5, 0, 3) or (3, 5, 0) or (8, 0, 0) which are repeated state. Hence these states are not considerably again for going towards goal.
So the state will be like:
(5, 0, 3) --> (5, 3, 0)
(3, 5, 0) --> (3, 2, 3)
(0,5, 3) --> X
Step 3:
In this step, start with the first current state of step-2 i.e. (5, 3, 0) and proceed likewise the above steps.
(5,3, 0) --> (2, 3, 3)
(3, 2,3) --> (6, 2, 0)
Step 4:
In this step, start with the first current state of step-3 i.e. (2, 3, 3) and proceed.
_2,3, 3_ _ _2, 5, 1_ _6,2, 0_ _ _7,
0, 1_
Step 5:
_2, 5, 1_ _ _7, 0, 1_ _6, 0, 2_ _ _1,
5, 2_
Step 6:
_7, 0, 1_ _ _7, 1, 0_ _1, 4, 3_ _ _1,
4, 3_
Step 7:
_7, 1, 0_ _ _4, 1, 3_
_1, 4, 3_ _ _4, 4, 0_ _Goal_
So finally the state will be (4, 4, 0) that means jug A and jug B contains 4 liters of water each which is our goal state. One thing you have to very careful about the pouring of water from one jug to another that the capacity of jug must satisfy the condition to contain that much of water.
The tree of the water jug problem can be like:
This problem takes a lot of time to find the goal state. This process of searching in this problem is very lengthy.
At each step of the problem the user have to strictly follow the production rules. Otherwise the problem may go to infinity step.