Add a new heuristic function h1(state) that takes a Stateobject called state, and that computes and returns an estimate of how many additional moves are needed to get from state to the goal state. Its estimate should simply be the number of misplaced tiles in the Board object associated with state. Take advantage of the appropriate Board method to determine this value.

Make sure that h1 is a function, not a method. Use the existing h0 function as a model, and make sure that h1s header is notindented.

Once you have added this function, you can perform the following tests:

>>> s1 = State(Board('142358607'), None, 'init') >>> s2 = State(Board('142358670'), None, 'init') >>> h1(s1) # the board in s1 has 5 misplaced tiles 5 >>> h1(s2) # the board in s2 has 4 misplaced tiles 4 >>> g1 = GreedySearcher(h0) >>> g1 GreedySearcher: 0 untested, 0 tested, heuristic h0 >>> g2 = GreedySearcher(h1) >>> g2 GreedySearcher: 0 untested, 0 tested, heuristic h1 >>> g1.heuristic(s1) # g1 uses h0, so its heuristic always returns 0 0 >>> g2.heuristic(s1) # g2 uses h1, so its heuristic returns h1's estimate 5 >>> g2.priority(s1) # the priority is -1 times the heuristic value -5