Consider the following puzzle, depicted in fig. 2, commonly referred to as the Towers of Hanoi: The generic Towers of Hanoi puzzle consists of n poles, P1 to Pn, and m disks with sizes D1 to Dm, and disks can be moved between poles. The object of the puzzle is to move all disks from the left-most pole to the right-most pole in as few moves as possible. For any two disks Di and Di+1, Di > Di+1 for all D. As such, D1 is the largest disk, and Dm is the smallest. All m disks start on the left-most pole P1, and must all be moved to the right-most pole Pn. No disk may be placed on top of a smaller disk at any time. Only one disk (the top-most) may be removed from a pole at any time, and must be placed back on a pole before any other disk is removed. Figure 2: Diagram showing the starting state for the 3-pole, 4-disk variant of the Towers of Hanoi problem.

(i) [10 marks] Define a problem representation for the generic n-pole, m-disk variant of the puzzle. Recall that a problem representation consists of a state representation, initial state, goal test, successor function, and path cost.

(ii) [2 marks] Which uninformed search algorithm is best for this problem? Why?

(iii) [3 marks] Suppose I decide to use A* search for this problem, define an admissible heuristic function that directly references some part of the problem representation (i.e. you cannot just specify h(n) = 0). Note that this does not need to be a good heuristic, just needs to be an admissible heuristic for the problem.

(iv) [5 marks] Show that your heuristic function is admissible.