Description

You are given an 8-litre jar full of water and two empty jars of 5- and 3-litre
capacity. You have to get exactly 4 litres of water in one of the jars. You can
completely empty a jar into another jar with space or completely fill up a jar from
another jar.
1. Formulate the problem: Identify states, actions, initial state, goal state(s).
Represent the state by a 3-tuple. For example, the intial state state is (8,0,0).
(4,1,3) is a goal state (there may be other goal states also).
2. Use a suitable data structure to keep track of the parent of every state. Write
a function to print the sequence of states and actions from the initial state to the
goal state.
3. Write a function next states(s) that returns a list of successor states of a given
state s.
4. Implement Breadth-First-Search algorithm to search the state space graph for
a goal state that produces the required sequence of pouring’s. Use a Queue as
frontier that stores the discovered states yet be explored. Use a dictionary for
explored that is used to store the explored states.
5. Modify your program to trace the contents of the Queue in your algorithm.
How many states are explored by your algorithm?