Consider the Cats and Mice problem: Three cats and three mice wish to cross from the left side to the right side of the river using a single boat. The boat can only hold two animals and can be rowed by any animal in the group. The goal is to find a sequence of moves that transfers all six animals to the right hand side of the river. At no time can the cats outnumber the mice on either side of the river. Your task is to formulate this as a search problem.

(6 pts) List all the heuristics below that are admissible:

(1) h1(n) = number of animals on the left bank

(2) h2(n) = number of animals on the left bank 1

(3) h3(n) = h (n) (i.e., the true remaining path cost)

(4) h4(n) = 0

(5) h5(n) = 2

(6) h6(n) = ( 1 : boat on left 0 : boat on right

(7) h7(n) = min(2, h (n))

(8) h8(n) = max(2, h (n))

(9) h9(n) = maximum of any two admissible heuristics