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 6×8. 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!