3.2.5 my heuristic(current board, goal board) Write a function that takes current board and goal board as arguments and returns an estimate of how many moves it will take to reach the goal board. Your heuristic must be admissible (never overestimate the cost to the goal), but it does not have to be consistent (never overestimate step costs). It should always return a value 0, be a more accurate estimate than (be greater than on average) the Manhattan Distance heuristic, and function competently for A* searches. It may not correlate linearly with the Manhattan Distance.

################################# # Problem 5 - Your Own Heuristic ################################# # Objectives: # (1) Write a function that takes current_board and goal_board as arguments and # returns an estimate of how many moves it will take to reach the goal board. # Your heuristic must be admissible (never overestimate cost to goal), but # it does not have to be consistent (never overestimate step costs). # # Notes: # (1) This heuristic should be admissible, but greater than (closer to the real # value than) the manhattan distance heuristic on average. That makes it a # better heuristic.

def my_heuristic(current_board, goal_board): raise NotImplementedError

################################## # Board Class ##################################

class Board: """ This class represents the actual Board of the game matrix - a double sub-scripted list containing the description of the current game State with 0 indicating the blank blankPos - a tuple containing the (row, column) position of the blank (which is denoted as 0) """

# The 15-puzzle board representation def __init__(self, matrix): self.matrix = matrix for r, row in enumerate(matrix): if 0 in row: self.blankPos = (r, row.index(0)) break else: raise ValueError("Invalid Matrix!")

# A function to provide a string description of the board def __str__(self): largestDigitNumInColumns = [1, 1, 1, 1] for column in range(len(self.matrix[0])): for row in range(len(self.matrix)): if self.matrix[row][column] >= 10: largestDigitNumInColumns[column] = 2 s = "" for row in range(len(self.matrix)): s += "[" for column in range(len(self.matrix[0])): if largestDigitNumInColumns[column] == 2 and self.matrix[row][column] < 10: s += " " + str(self.matrix[row][column]) else: s += str(self.matrix[row][column]) if (column != len(self.matrix[0]) - 1): s += ", " s += "] " return s + ' '

# A function to explain how to make the board def __repr__(self): return f'Board({self.matrix})'

# A function to checks if two Boards are equal def __eq__(self, other): if not isinstance(other, Board): return False return self.matrix == other.matrix

# A function to create a copy of the Board object itself def duplicate(self): new_matrix = [row.copy() for row in self.matrix] return Board(new_matrix)

# A function that returns a tuple containing the (row, col) position of the given element in the board def find_element(self, elem): for r, row in enumerate(self.matrix): for c, val in enumerate(row): if val == elem: return (r, c) return None

# A function that puts the four sliding functions together, and takes direction as input # move is a tuple representing (delta Y, delta X) def slide_blank(self, move): if move not in [(0, 1), (0, -1), (-1, 0), (1, 0)]: raise ValueError("Invalid move") cur_r, cur_c = self.blankPos delta_r, delta_c = move new_r, new_c = cur_r + delta_r, cur_c + delta_c if new_r < 0 or new_r > len(self.matrix) - 1: return None elif new_c < 0 or new_c > len(self.matrix[0]) - 1: return None else: new_board = self.duplicate() new_board.matrix[cur_r][cur_c] = new_board.matrix[new_r][new_c] new_board.matrix[new_r][new_c] = 0 new_board.blankPos = (new_r, new_c) return new_board

def __hash__(self): s = 0 for row in self.matrix: for val in row: s *= 16 # this must be equal to w*h s += val return s

################################## # State Class ##################################

class State: """ This class represents the state of each board in the game board - the actual board that belongs to this state (See Board Class) parent_state - the State that the current State came from after applying a legal move depth - the depth in the move tree from the original board that this board can be found in (the # of moves the puzzle has undergone) f-value - the priority order of the state; some evaluation function of the state """

# The representation of the current game state def __init__(self, board, parent_state, depth, fvalue=0): self.board = board self.parent_state = parent_state self.depth = depth self.fvalue = fvalue

# checks if the f-value of this board is less than the f-value of another board def __lt__(self, other): return self.fvalue < other.fvalue

# converts this State into a string def __str__(self): return f"{self.board} f-value: {self.fvalue} steps: {self.depth} "

# a function to explain how the state is made def __repr__(self): if self.parent_state is self: return f'State({self.board!r}, "is own parent", {self.depth!r}, {self.fvalue!r})' try: return f'State({self.board!r}, {self.parent_state!r}, {self.depth!r}, {self.fvalue!r})' except RecursionError: return 'State("could not be represented due to RecursionError")'

# checks if two States are the same. This only compares the boards. def __eq__(self, other): if type(other) is not State: return False return self.board == other.board

# Function to print a completed path from the initial state to the solution state # def printPath(self): print(self.board) if self.parent_state is not None: self.parent_state.printPath()