This question is asking us to solve the 8-puzzle using a different method other than the h0 and h1 heuristic functions. I've provided the code for all the files needed for this project below. I just need one more heuristic function. I've researched using the manhattan method and the Eucledian method. But, I don't know how to write it. Please help.

Board File:

class Board: """ A class for objects that represent an Eight Puzzle board. """ def __init__(self, digitstr): """ a constructor for a Board object whose configuration is specified by the input digitstr input: digitstr is a permutation of the digits 0-9 """ # check that digitstr is 9-character string # containing all digits from 0-9 assert(len(digitstr) == 9) for x in range(9): assert(str(x) in digitstr)

self.tiles = [[0] * 3 for x in range(3)] self.blank_r = -1 self.blank_c = -1

# Put your code for the rest of __init__ below. # Do *NOT* remove our code above.

for r in range(3): for c in range(3): self.tiles[r][c] = int(digitstr[3*r + c]) if self.tiles[r][c] == 0: self.blank_r=r self.blank_c=c ### Add your other method definitions below. ### def __repr__(self): """, each numeric tile should be represented by the appropriate single-character string, followed by a single space. """ x='' for r in range(3): for c in range(3): if self.tiles[r][c] != 0: x+=str(self.tiles[r][c])+' ' else: x+='_ ' x+=' ' return x def move_blank(self, direction): """takes as input a string direction that specifies the direction in which the blank should move, and that attempts to modify the contents of the called Board object accordingly. """ blank_c = self.blank_c blank_r = self.blank_r if direction == 'up': blank_r = self.blank_r - 1 elif direction == 'down': blank_r = self.blank_r + 1 elif direction == 'left': blank_c = self.blank_c - 1 elif direction == 'right': blank_c = self.blank_c + 1 else: print("unknown direction:", direction) return False if blank_r >= 3 or blank_c >= 3 or blank_r

def digit_string(self): """creates and returns a string of digits that corresponds to the current contents of the called Board objects tiles attribute. """ digitstring = '' for r in range(3): for c in range(3): if self.tiles[r][c]=='_': digitstring+='0' else: digitstring+=str(self.tiles[r][c]) return digitstring

def copy(self): """returns a newly-constructed Board object that is a deep copy of the called object """ new_board = Board(self.digit_string()) return new_board

def num_misplaced(self): """counts and returns the number of tiles in the called Board object that are not where they should be in the goal state. """ count = 0 goal_board = '012345678' current_board = self.digit_string() for i in range(8): if current_board[i] == 0 or current_board[i] == goal_board[i]: count else: count += 1 return count

def __eq__(self, other): """overloads the == operator creating a version of the operator that works for Board objects. The method should return True if the called object (self) and the argument (other) have the same values for the tiles attribute, and False otherwise. """ if self.tiles == other.tiles: return True else: return False

State File:

from board import *

# a 2-D list that corresponds to the tiles in the goal state GOAL_TILES = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]

# the list of possible moves, each of which corresponds to # moving the blank cell in the specified direction MOVES = ['up', 'down', 'left', 'right']

class State: """ A class for objects that represent a state in the state-space search tree of an Eight Puzzle. """ ### Add your method definitions here. ### def __init__(self, board, predecessor, move): """constructs a new State object by initializing the following four attributes: """ self.board = board self.move = move self.predecessor= predecessor if predecessor == None: self.num_moves = 0 else: self.num_moves = predecessor.num_moves + 1

def is_goal(self): """returns True if the called State object is a goal state, and False otherwise. """ if self.board.tiles == GOAL_TILES: return True else: return False def generate_successors(self): """creates and returns a list of State objects for all successor states of the called State object. """ successors = [] for m in MOVES: b = self.board.copy() if b.move_blank(m) == True: s = State(b, self, m) successors+=[s] return successors

def __repr__(self): """ returns a string representation of the State object referred to by self. """ # You should *NOT* change this method. s = self.board.digit_string() + '-' s += self.move + '-' s += str(self.num_moves) return s def creates_cycle(self): """ returns True if this State object (the one referred to by self) would create a cycle in the current sequence of moves, and False otherwise. """ # You should *NOT* change this method. state = self.predecessor while state != None: if state.board == self.board: return True state = state.predecessor return False

def __gt__(self, other): """ implements a > operator for State objects that always returns True. This will be needed to break ties when we use max() on a list of [priority, state] pairs. If we don't have a > operator for State objects, max() will fail with an error when it tries to compare two [priority, state] pairs with the same priority. """ # You should *NOT* change this method. return True def print_moves_to(self): if self.predecessor==None: print('initial state:') print(self.board) else: self.predecessor.print_moves_to() print('move the blank', self.move) print(self.board)

Searcher:

import random from state import *

class Searcher: """ A class for objects that perform random state-space search on an Eight Puzzle. This will also be used as a superclass of classes for other state-space search algorithms. """ ### Add your Searcher method definitions here. ### def __init__(self, depth_limit): """constructs a new Searcher object """ self.states = [] self.num_tested = 0 self.depth_limit = depth_limit

def add_state(self, new_state): """that adds takes a single State object called new_state and adds it to the Searchers list of untested states """ self.states+=[new_state]

def should_add(self, state): """that takes a State object called state and returns True if the called Searcher should add state to its list of untested states, and False otherwise """

if self.depth_limit != -1 and state.num_moves > self.depth_limit: return False elif state.creates_cycle()==True: return False else: return True

def add_states(self, new_states): """that takes a list State objects called new_states, and that processes the elements of new_states one at a time """ for i in new_states: if self.should_add(i): self.add_state(i)

def __repr__(self): """ returns a string representation of the Searcher object referred to by self. """ # You should *NOT* change this method. s = type(self).__name__ + ': ' s += str(len(self.states)) + ' untested, ' s += str(self.num_tested) + ' tested, ' if self.depth_limit == -1: s += 'no depth limit' else: s += 'depth limit = ' + str(self.depth_limit) return s def next_state(self): """ chooses the next state to be tested from the list of untested states, removing it from the list and returning it """ s = random.choice(self.states) self.states.remove(s) return s

def find_solution(self, init_state): """that performs a full random state-space search, stopping when the goal state is found or when the Searcher runs out of untested states """ self.add_state(init_state) while self.states != []: s = self.next_state() self.num_tested += 1 if s.is_goal(): return s else: self.add_states(s.generate_successors()) return None

### Add your BFSeacher and DFSearcher class definitions below. ### class BFSearcher(Searcher):

def next_state(self): """that overrides (i.e., replaces) the next_state method that is inherited from Searcher. Rather than choosing at random from the list of untested states, this version of next_state should follow FIFO (first-in first-out) ordering choosing the state that has been in the list the longest"""

s = self.states[0] self.states.remove(s) return s class DFSearcher(Searcher): def next_state(self): """that overrides (i.e., replaces) the next_state method that is inherited from Searcher. Rather than choosing at random from the list of untested states, this version of next_state should should follow LIFO (last-in first-out) ordering choosing the state that was most recently added to the list"""

s = self.states[-1] self.states.remove(s) return s

def h0(state): """ a heuristic function that always returns 0 """ return 0 def h1(state): """computes and returns an estimate of how many additional moves are needed to get from state to the goal state""" count=state.board.num_misplaced() return count

### Add your other heuristic functions here. ### def digit_string(self): """creates and returns a string of digits that corresponds to the current contents of the called Board objects tiles attribute. """ digitstring = '' for r in range(3): for c in range(3): if self.tiles[r][c]=='_': digitstring+='0' else: digitstring+=str(self.tiles[r][c]) return digitstring class GreedySearcher(Searcher): """ A class for objects that perform an informed greedy state-space search on an Eight Puzzle. """ ### Add your GreedySearcher method definitions here. ### def __init__(self, heuristic): """ constructor for a GreedySearcher object inputs """ super().__init__(-1) self.heuristic = heuristic def priority(self, state): """ computes and returns the priority of the specified state, based on the heuristic function used by the searcher """ return -1 * self.heuristic(state) def add_state(self, state): """that overrides (i.e., replaces) the add_state method that is inherited from Searcher. Rather than simply adding the specified state to the list of untested states, the method should add a sublist that is a [priority, state] pair, where priority is the priority of state, as determined by calling the priority method"""

self.states+=[[self.priority(state), state]] def next_state(self): """that overrides (i.e., replaces) the next_state method that is inherited from Searcher. This version of next_state should choose one of the states with the highest priority.""" s=max(self.states) self.states.remove(s) return s[1]

def __repr__(self): """ returns a string representation of the GreedySearcher object referred to by self. """ # You should *NOT* change this method. s = type(self).__name__ + ': ' s += str(len(self.states)) + ' untested, ' s += str(self.num_tested) + ' tested, ' s += 'heuristic ' + self.heuristic.__name__ return s

### Add your AStarSeacher class definition below. ### class AStarSearcher(GreedySearcher): def priority(self, state): """that takes a State object called state, and that computes and returns the priority of that state """ priority= -1 *(self.heuristic(state) + state.num_moves) return priority

Eight_puzzle:

from searcher import * from timer import *

def create_searcher(algorithm, param): """ a function that creates and returns an appropriate searcher object, based on the specified inputs. inputs: * algorithm - a string specifying which algorithm the searcher should implement * param - a parameter that can be used to specify either a depth limit or the name of a heuristic function Note: If an unknown value is passed in for the algorithm parameter, the function returns None. """ searcher = None if algorithm == 'random': searcher = Searcher(param) elif algorithm == 'BFS': searcher = BFSearcher(param) elif algorithm == 'DFS': searcher = DFSearcher(param) elif algorithm == 'Greedy': searcher = GreedySearcher(param) elif algorithm == 'A*': searcher = AStarSearcher(param) else: print('unknown algorithm:', algorithm) return searcher

def eight_puzzle(init_boardstr, algorithm, param): """ a driver function for solving Eight Puzzles using state-space search inputs: * init_boardstr - a string of digits specifying the configuration of the board in the initial state * algorithm - a string specifying which algorithm you want to use * param - a parameter that is used to specify either a depth limit or the name of a heuristic function """ init_board = Board(init_boardstr) init_state = State(init_board, None, 'init') searcher = create_searcher(algorithm, param) if searcher == None: return

soln = None timer = Timer(algorithm) timer.start() try: soln = searcher.find_solution(init_state) except KeyboardInterrupt: print('Search terminated.')

timer.end() print(str(timer) + ', ', end='') print(searcher.num_tested, 'states')

if soln == None: print('Failed to find a solution.') else: print('Found a solution requiring', soln.num_moves, 'moves.') show_steps = input('Show the moves (y)? ') if show_steps == 'y': soln.print_moves_to() def process_file(filename, algorithm, param): """ Processes a .txt file of different combinations """

file = open(filename, 'r') puzzles = 0 moves = 0 tested_states = 0 for line in file: string = line[:-1] init_board = Board(string) init_state = State(init_board, None, 'init') searcher = create_searcher(algorithm, param) if searcher == None: return soln = None try: soln = searcher.find_solution(init_state) if soln == None: print(string + ':','no solution') else: print(string + ':', soln.num_moves, 'moves,', searcher.num_tested, 'states tested') puzzles += 1 moves += soln.num_moves tested_states += searcher.num_tested except KeyboardInterrupt: print('search terminated, ', end='') print() print('solved', puzzles, 'puzzles') if puzzles != 0: print('average:', moves/puzzles, 'moves,', tested_states/puzzles, 'states tested')

timer:

import time

class Timer: """A class whose instances store the difference between two moments in time. To time something, an instance's start() method must be called, followed by a call to its end() method. Each instance also has a name that is included when the object's __repr__() is called. """ def __init__(self, name=''): self.name = name self.start_time = None self.end_time = None

def start(self): self.start_time = time.time() self.end_time = None

def end(self): self.end_time = time.time()

def get_diff(self): if self.start_time != None and self.end_time != None: return abs(self.end_time - self.start_time) else: return None

def __repr__(self): return '{}: {:.5} seconds'.format(self.name, self.get_diff())

4. Even informed search algorithms like Greedy Search and A* can be slow on problems that require a large number of moves. This is especially true if the heuristic function used by the algorithm doesn't do a good enough job of estimating the remaining cost to the goal Our h1 heuristic function-which uses the number of misplaced tiles as the estimate of the remaining cost-is one example of a less than ideal heuristic. For example, consider the following two puzzles 3 2 415 67 8 3 45 Both of them have 4 misplaced tiles (the ones displayed in red), but the puzzle on the left can be solved in 4 moves, whereas the puzzle on the right requires 24 moves! Clearly, it would be better if our heuristic could do a better job of distinguishing between these two puzzles Come up with at least one alternate heuristic, and implement it as part of your classes for informed searchers (GreedySearcher and AStarSearcher). To do so, you should take the following steps a. As needed, add one or more methods to the Board class that will be used by your new heuristic function. (Adding a new method to the Board class is not required, but it can be helpful to add one so that the heuristic function can obtain the information needed for its estimate.) b. Add your new heuristic function(s) to searcher.py, and follow these guidelines Continue the numbering scheme that we established for the earlier heuristic functions. Call your first alternate heuristic function h2, your next heuristic function (if any) h3, etc Make sure that each heuristic function is a regular function, not a method. In addition, make sure that it takes a single State object and returns an integer C. When conducting tests using a new heuristic function, use its name in the same ways that you would use h or h1. For example >gGreedySearcher(h2) >>> eight_puzzle('142358607", "Greedy', h2) >>> process_file('15_moves.txt', 'A*', h2) 4. Even informed search algorithms like Greedy Search and A* can be slow on problems that require a large number of moves. This is especially true if the heuristic function used by the algorithm doesn't do a good enough job of estimating the remaining cost to the goal Our h1 heuristic function-which uses the number of misplaced tiles as the estimate of the remaining cost-is one example of a less than ideal heuristic. For example, consider the following two puzzles 3 2 415 67 8 3 45 Both of them have 4 misplaced tiles (the ones displayed in red), but the puzzle on the left can be solved in 4 moves, whereas the puzzle on the right requires 24 moves! Clearly, it would be better if our heuristic could do a better job of distinguishing between these two puzzles Come up with at least one alternate heuristic, and implement it as part of your classes for informed searchers (GreedySearcher and AStarSearcher). To do so, you should take the following steps a. As needed, add one or more methods to the Board class that will be used by your new heuristic function. (Adding a new method to the Board class is not required, but it can be helpful to add one so that the heuristic function can obtain the information needed for its estimate.) b. Add your new heuristic function(s) to searcher.py, and follow these guidelines Continue the numbering scheme that we established for the earlier heuristic functions. Call your first alternate heuristic function h2, your next heuristic function (if any) h3, etc Make sure that each heuristic function is a regular function, not a method. In addition, make sure that it takes a single State object and returns an integer C. When conducting tests using a new heuristic function, use its name in the same ways that you would use h or h1. For example >gGreedySearcher(h2) >>> eight_puzzle('142358607", "Greedy', h2) >>> process_file('15_moves.txt', 'A*', h2)