In the water-jug puzzle, we are given a 3-liter jug, named Three and a 4-liter jug named Four. Initially, Three and Four are empty. Either jug can be filled with water from a tap, T, and we can discard water from either jug down a drain, D. Water may be poured from one jug into the other. There is no additional measuring device. We want to find a set of operations that will leave precisely two liters of water in Four.
(a) fill Three from the tap,
(b) pour Three into Four
(c) fill Three from the tap,
(d) pour as much from Three into Four as will fill it.
(e) discard Four,
(f) pour Three into Four.]
1. Set up a state-space search formulation of the water-jug puzzle:
(a) Give the initial iconic state description as a data structure.
(b) Give a goal condition on states as some test on data structures.
(c) Name the operators on states and give precise descriptions of what each operator does to a state description.
2. Draw a graph of all of the distinct state-space nodes that are within three moves of the start node, label each node by its state description, and show at least one path to each node in the graph-labeling each arc by the name of the appropriate operator. In addition to these nodes, show also all of the nodes and arcs (properly labeled) on a path to the solution.