I am trying to find the optimal solution for a given 15-puzzle. So far as I can tell, the algorithm works (on simple instances of 8-puzzle), but is extremely slow for complex starting states (order of 100 seconds), and practically unsolvable with 15 tiles.I know finding the optimal solution is hard but I think I may be using the language in an efficient way here.IDAStarSolver.solve() contains the starting point for computing the solution, although most of the operations are done in the Board class.This is the class containing the solver:import sysfrom heapq import heappop, heappushfrom src.State import Stateclass IDAStarSolver:    def __init__(self, board, heuristic='manhattan'):        self.solution = []        self.initial = board        self.heuristic = heuristic    def solve(self):        bound = getattr(self.initial, self.heuristic)        while True:            t = self.search(self.initial, 0, bound)            if t == 'FOUND':                return bound            if t == sys.maxsize:                return 'NOT_FOUND'            bound = t    def search(self, node, g, bound):        f = g + getattr(node, self.heuristic)        if f > bound:            return f        if getattr(node, self.heuristic) == 0:            return 'FOUND'        minimum = sys.maxsize        for neighbour in node.neighbours():            t = self.search(neighbour, g + 1, bound)            if t == 'FOUND':                self.solution.append(node)                return 'FOUND'            if t < minimum:                minimum = t        return minimum    def moves(self):        return len(self.solution)And the Board is represented as follows:from copy import copyimport numpy as npclass Board:     A nxn board for with n^2 - 1 tiles     def __init__(self, tiles=None, size=3):        if tiles is None:            self.dim = size            self.tiles = self.generate_board(size)            while not self.is_solvable():                self.tiles = self.generate_board(size)        else:            self.dim = len(tiles)            self.tiles = tiles        self.zero_row = np.where(self.tiles == 0)[0][0]        self.zero_column = np.where(self.tiles == 0)[1][0]        self.manhattan = self._manhattan()    def __copy__(self):        cls = self.__class__        new_copy = cls.__new__(cls)        new_copy.tiles = np.copy(self.tiles)        new_copy.manhattan = self.manhattan        new_copy.dim = self.dim        new_copy.zero_row = self.zero_row        new_copy.zero_column = self.zero_column        return new_copy    def _manhattan(self):        manhattan = 0        for i in range(self.dim):            for j in range(self.dim):                if self.tiles[i][j] != 0:                    row = (self.tiles[i][j] - 1) // self.dim                    column = (self.tiles[i][j] - 1) % self.dim                    manhattan += abs(i - row) + abs(j - column)        return manhattan    def equals(self, board):                :param Board board: Test board                return np.array_equal(board.tiles, self.tiles)    def swap_zero(self, i0, j0):                Swaps tile at i0, j0 with the zero tile                # Recalculate manhattan distance        row = (self.tiles[i0][j0] - 1) // self.dim        column = (self.tiles[i0][j0] - 1) % self.dim        self.manhattan -= abs(i0 - row) + abs(j0 - column)        self.manhattan += abs(self.zero_row - row) + abs(self.zero_column - column)        # Swap tiles        self.tiles[i0][j0], self.tiles[self.zero_row, self.zero_column] = \                self.tiles[self.zero_row, self.zero_column], self.tiles[i0, j0]        # Update zero row and column        self.zero_row = i0        self.zero_column = j0    def neighbours(self):        neighbours = []        # The zero tile can be swapped with tile above        if self.zero_row > 0:            neighbour = copy(self)            neighbour.swap_zero(self.zero_row - 1, self.zero_column)            neighbours.append(neighbour)        # The zero tile can be swapped with tile below        if self.zero_row < self.dim - 1:            neighbour = copy(self)            neighbour.swap_zero(self.zero_row + 1, self.zero_column)            neighbours.append(neighbour)        # The zero tile can be swapped with the tile to its left        if self.zero_column > 0:            neighbour = copy(self)            neighbour.swap_zero(self.zero_row, self.zero_column - 1)            neighbours.append(neighbour)        # The zero tile can be swapped with the tile to its right        if self.zero_column < self.dim - 1:            neighbour = copy(self)            neighbour.swap_zero(self.zero_row, self.zero_column + 1)            neighbours.append(neighbour)        return neighbours    def is_solved(self):                Checks if the board is the goal position                return self.manhattan() == 0    def is_solvable(self):                Checks if the board is solvable                tiles = np.ndarray.flatten(self.tiles)        dim = self.dim * self.dim        inversions = 0        for i in range(dim):            for j in range(i, dim):                if tiles[i] != 0 and tiles[j] != 0 and tiles[i] > tiles[j]:                    inversions += 1        return inversions % 2 == 0    @staticmethod    def generate_board(size):        arr = np.arange(size ** 2)        np.random.shuffle(arr)        arr = arr.reshape(size, size)        return arr    def __str__(self):        return np.array_str(self.tiles)And the State:import functools@functools.total_orderingclass State:    def __init__(self, current, previous, moves):                :param current: The current board position        :param previous: The previous board position        :param moves: The number of moves made to get to the current board position                self.current = current        self.moves = moves        self.previous = previous        self.score = self._score()    def _score(self):        return self.current.manhattan + self.moves    def __lt__(self, other):        return self.score < other.score    def __eq__(self, other):        return self.score == other.score
Slow 8/15-puzzle IDA*
python;performance;sliding tile puzzle;a star