You need exactly one liter of water. You have only a 17-liter jug and a 7-liter jug. You can 1. fill either jug from a well, 2. empty the contents of a jug, or 3. pour water from one jug to the other jug. Unfortunately, you are hopeless at guessing quantities. Given only these three operations, how can you get one liter of water in a jug? The solution to this problem can be reduced to a state space graph searching algorithm. We will use a state representation consisting of the pair (i,j)where i is the amount, in liters, in the 17-liter jug and j is the amount in the 7-litter jug. Define the neighbors of an arbitrary node associated with state (i,j)? That is, you have three operations that can be applied to either jug. For each of the six possible operations applied to (i,j), what is the resulting state. Note: there are a finite number of states as i and j are integers with 0 i 17 and 0 j 7. 1. Implement a program to conduct a depth-first search of this space. The search should use (0,0) as the start state. The states (1,?)and (?,1)are the goal states (that is, one want one liter in a jug, and you dont care what is in the other jug. Use graph search. That is, dont repeatedly expand the same state. Remember the states that have been seen. Output the list of states in order of expansion. Mention how your code ordered the operations for pushing new states onto the stack. Output the sequence of state, operation that creates a path from the initial state to a goal state. You can use an abbreviation or number for the operation. Such as the number 1-6 for the operations, or abbreviations such as 1i, 1j, 2i, 2j, 3i, and 3j for the rule and jug. So the start of the sequence could look like (0,0), 1i , (17,0), 3i, (10,7), ...

2. Implement a program to conduct iterative deepening search of the same space. For each depth level, output the level and the list of states in order of expansion. Output the sequence of state, operation that creates a path from the initial state to a goal state.