Water Jug problem solving
Think if you have been
provided 3L and 4L capacity jugs that have not marked the measurement. An unlimited water supply has been provided and no restriction to throw away water as
necessary from the filled jug.
All you need to do is, measure
exactly 2L of water from any one of the jugs at a time.
To solve this,
we have to assign start and goal states.
Start state –
(0,0)
Goal state –
(0,2) or (2,0)
Following
are the all possible methods of filling water into jugs
State Representation
(a,b)
a- a - Represent the amount of water in 4L
jug
b- b - Represent the amount of water in 3L
jug
0<a<4
0<b<3
Required Rules
a= 4L
b= 3L
Fill water
1. Filling 4L jug (4,b) condition a<4
2. Filling 3L jug (a,3) condition b<3
Emptying
3. Empty 4L jug (0,b) condition a>0
4. Empty 3L jug (a,0) condition b>0
Transfer some amount of water
5. Pour from 4L jug (a-p,b) condition a>0
6. Pour from 3L jug (a,b-p) condition
b>0
*p= some amount of water
Fill until other jug becomes full
7. Pour from 3L to 4L (4,b-(4-a)) condition a+b>=4 & b>0
8. Pour from 4L to 3L (a-(3-b),3) condition a+b>=3 & a>0
Pour all water to other jug
9. Pour all from 3L to 4L (a+b,0) condition
0<(a+b)<=4 & b>=0
10. Pour all from 4L to 3L (0,a+b) condition 0<(a+b)<=3 &
a>=0
Solution 01
|
4L jug |
3L jug |
Rule No |
Rule State |
|
0 |
0 |
|
(0,0) |
|
4 |
0 |
1. Fill 4L |
(4,b) |
|
1 |
3 |
8. Pour 4L to 3L |
(a-(3-b),3) |
|
1 |
0 |
4. Empty 3L |
(a,0) |
|
0 |
1 |
10. Pour all water to 3L |
(0,a+b) |
|
4 |
1 |
1. Fill 4L |
(4,b) |
|
2 |
3 |
8. Pour 4L to 3L |
(a-(3-b),3) |
|
2 |
0 |
4. Empty 3L |
(a,0) |
Solution 02
|
4L jug |
3L jug |
Rule No |
Rule state |
|
0 |
0 |
|
(0,0) |
|
0 |
3 |
2. Fill 3L |
(a,3) |
|
3 |
0 |
9. Pour 3L to 4L |
(a+b,0) |
|
3 |
3 |
2. Fill 3L |
(a,3) |
|
4 |
2 |
7. Pour from 3L to 4L |
(4,b-(4-a)) |
|
0 |
2 |
3. Empty 4L |
(0,b) |
