Optimizing backtracking algorithm for non-jigsaw puzzle

Question

As my previous post outlined, I am making a puzzle solver, however, my puzzles don't contain jigsaw pieces but normal rectangles instead. My initial post was asking about an algorithm that I can use to solve such puzzle. Despite not getting any great ideas, I came up with an algorithm all on my own which uses backtracking.

A quick explanation of my algorithm so far:

• I represent the final configuration of the puzzle by a 1D array
• Each piece contains an array with fitness values given to every other piece (these dictate how easy it is for them to fit together)
• Threshold dictates how different the pieces can be to still be considered fitting by the algorithm

def solve_image(self, col: int, state: list[Candidate], used_pieces: list[int]) -> list:

        threshold = 10
        print(f'Used pieces: {used_pieces}')
        self.counter = self.counter + 1

        # finishing condition
        if col > self.cols * self.rows - 1:
            print(f'Went over {self.counter} pieces')
            return state

        if col == 0:
            # randomly choose the first piece from all the pieces
            for piece in self.image_pieces:
                # first convert the piece to a candidate to be able to use it in the algorithm
                piece_to_candidate = Candidate(piece, fitness_value=0)
                result = self.solve_image(col=col + 1, state=[piece_to_candidate],
                                          used_pieces=[piece_to_candidate.piece.index])
                if len(result) > 0:
                    return result

            return []
        else:
            if col % self.cols == 0:
                # the piece is in the beginning of the row and therefore there is no piece before it in the row
                # take the first piece of the row before and go through the bottom candidates
                # the piece from which the candidates will be taken for the next piece
                candidate_piece = state[col - self.cols]
                sorted_candidates = candidate_piece.piece.get_sorted_candidates(Edge.BOTTOM)
                possible_candidates = list(filter(lambda x: x.fitness_value < threshold, sorted_candidates))
                for candidate in possible_candidates:
                    if candidate.piece.index not in set(used_pieces):
                        new_state = state + [candidate]
                        new_used = used_pieces + [candidate.piece.index]
                        result = self.solve_image(col=col + 1, state=new_state, used_pieces=new_used)
                        if len(result) > 0:
                            return result
                return []
            else:
                # the piece is somewhere in the image where it always has a piece before it
                # the piece from which the candidates will be taken for the next piece
                candidate_piece = state[col - 1]
                sorted_candidates = candidate_piece.piece.get_sorted_candidates(Edge.RIGHT)
                possible_candidates = list(filter(lambda x: x.fitness_value < threshold, sorted_candidates))
                for candidate in possible_candidates:
                    if candidate.piece.index not in set(used_pieces):
                        # check if the piece is in a different row than the first one, if yes, compare more edges
                        passes_top_edge = True
                        if col > self.cols:
                            top_edge = state[col - self.cols]
                            for edge_candidate in top_edge.piece.get_sorted_candidates(Edge.BOTTOM):
                                if edge_candidate.fitness_value > threshold:
                                    passes_top_edge = False
                                    break
                                if edge_candidate.piece.index == candidate.piece.index:
                                    break
                                passes_top_edge = False

                        if passes_top_edge:
                            new_state = state + [candidate]
                            new_used = used_pieces + [candidate.piece.index]
                            result = self.solve_image(col=col + 1, state=new_state, used_pieces=new_used)
                            if len(result) > 0:
                                return result
                return []

The actual code I provided is just looking through all the pieces that it can pick based on the criteria and then putting them one by one into the image until the whole image passes the criteria and can be solved.

The main if statements are just for checking where the pieces are in the image and therefore which edges need to be considered.

Basically, it is just trying to fit in images into an array while using their fitness value to make sure they fit in with pieces around it.

The algorithm seems to work quite well on smaller puzzles, such as 6x8. However, the moment I put anything bigger it starts to take forever. Any ideas on how to optimize this algorithm? Feel free to ask any more questions!