AUS Solving Tile 8 Puzzle Using a Star Search Algorithm & Uniform Cost Search Code

I am writing an algorithm to solve the 8 puzzle. https://en.wikipedia.org/wiki/15_puzzle

I have a sample code, but don’t know how to elaborate on to make it work.

It should solve it using Uniform Cost Search, A* with the misplaced tiles heuristic, and A* with the total Manhattan distance heuristic. I need to create initial states of varying difficulty: either take a solution and add a certain number of random moves to it, or take a random state and make sure to get the difficulty level from one the optimal solution. The implementation should also solve the general N x N tile problem.

Code:

class PuzzleState:    def __init__(self, matrix=None, goal=False, init=False, size=3):        ## ** add code that generates puzzle states of varying difficulty        self.size = size        if not matrix is None: ## 0 represents empty spot            self.matrix = matrix        else: ## defining init or goal state            ## this is too hard for the benchmark, change this!            ## *** Your code here ***            permutation = np.array(range(size*size))            if init:                random.shuffle(permutation)             self.matrix = permutation.reshape((size, size))    def successors(self):        pass        ## *** Your code here ***        ## return a list of successors        ## each successor is a tuple of         ## 1. a string, describing the action,         ## 2. action cost (here 1),         ## 3. and the new state    def __hash__(self):        pass        ## return a hash code, if you have a matrix, you can uncomment this:        #return hash(tuple(self.matrix.flatten()))    def __eq__(self, other):        pass        ## this function defines equality between objects, if you have a matrix, you can uncomment this:        ##return np.alltrue(other.matrix == self.matrix)class PuzzleProblem:    def __init__(self, size=3): #size 3 means 3x3 field        self.size = size                self.initial = PuzzleState(init=True, size=size)  ## init state is shuffled         self.goal = PuzzleState(goal=True, size=size)  ## goal state is unshuffled     def successors(self, state):        return state.successors()        ## Successors can be "outsourced", you can also calculate successor states here    def goal_test(self, state):        # *** your code here ***        return False ## change this as appropriate!!class Node:    def __init__(self, state=None, parent=None, action=None, path_cost=0):        self.state = state        self.parent = parent        self.action = action        self.path_cost = path_cost            def getPath(self):        """getting the path of parents up to the root"""        currentNode = self        path = [self]        while currentNode.parent: ## stops when parent is None, ie root            path.append(currentNode.parent)            currentNode = currentNode.parent        path.reverse() #from root to this node        return path    def expand(self, problem):        successors = problem.successors(self.state)        return [Node(newState, self, action, self.path_cost+cost) for (action, cost, newState) in successors]    def __gt__(self, other): ## needed for tie breaks in priority queues        return True    def __repr__(self):        return (self.state, self.action, self.path_cost)    class FIFO:    def __init__(self):        self.list = []    def push(self, item):        self.list.insert(0, item)      def pop(self):        return self.list.pop()class LIFO:  ## fill out yourself!     def __init__(self):        pass    def push(self, item):        pass    def pop(self):        passclass PriorityQueue:    def __init__(self, f):        self.list = []        self.f = f    def push(self, item):        priority = self.f(item)        bisect.insort(self.list, (priority, random.random(), item))    def pop(self):        return self.list.pop(0)[-1]        def graph_search(problem, frontier):    """Search through the successors of a problem to find a goal.    The argument frontier should be an empty queue."""    closed = set() ## sets can store hashable objects, thats why we need to define a hash code for states    frontier.push(Node(problem.initial))    explorationHistory = []    while frontier:        node = frontier.pop()        explorationHistory.append(node)        if problem.goal_test(node.state):             return node, explorationHistory        if node.state not in closed:            closed.add(node.state)            successors = node.expand(problem)            for snode in successors:                frontier.push(snode)def tree_search(problem, frontier):    frontier.push(Node(problem.initial))    while frontier:        node = frontier.pop()        if problem.goal_test(node.state):            return node        successors = node.expand(problem)        for snode in successors:            frontier.push(snode)    def breadth_first_graph_search(problem):    return graph_search(problem, FIFO())def depth_first_graph_search(problem):    return graph_search(problem, LIFO())def astar_graph_search(problem, f):    return graph_search(problem, PriorityQueue(f))

Some of this code is already used to solve graph search for Map of Romania problem. The code for Romania problem is complete and works fine. I can provide the full .py file which contain both problems for you to see how it works on the other problem.