Question 3 (Problem Formulation) d C b A B C The Towers of Hanoi is a famous problem for studying recursion in computer science and recurrence equations in discrete mathematics. We

start with N discs of varying sizes on a peg (stacked in order according to size), and two empty pegs. We are allowed to move a dise from one peg to another, but we are never allowed to move a larger dise on top of a smaller dise. The goal is to move all the dises to the right most peg (see the figure above). In this problem, we will formulate the Towers of Hanoi as a search problem. Assume there are only 4 discs on the le peg to start with labeled a, b, c, and d and 3 pegs are labeled A, B, and C (as shown in the diagram) (a) Propose a data structure most suitable for state representation for this problem. (b) What is the state space (size of the state space and describe each state) for this problem? (c) What is the start space for this problem? (d) From a given state, what actions are legal for this problem? (e) What is the goal test for this problem? (f) Describe the transition model for this problem. (g) Assume an action cost for each move as $1, provide a solution. What is the minimum cost to solve this problem? (h) Explain if it is possible to represent this problem with a directed graph. If yes, draw its graphical representation with states and actions (states as circles and actions as directed arrows with action costs)