import datetime
def solve(height, width, pieces):
 sorted_pieces = sort_pieces_by_length(pieces) # this makes it faster as it sort also coords of piece
 board = [['' for _ in range(width)] for _ in range(height)]
 result = []
 counter = 0
 def is_valid_placement(piece, x, y):
 first_coord = piece[0]
 if not (0 <= x < width and 0 <= y < height) or board[y][x] != '':
 return False
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 if not (0 <= nx < width and 0 <= ny < height) or board[ny][nx] != '':
 return False
 return True
 def place_piece(piece, x, y, char):
 first_coord = piece[0]
 board[y][x] = char
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 board[ny][nx] = char
 def remove_piece(piece, x, y):
 first_coord = piece[0]
 board[y][x] = ''
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 board[ny][nx] = ''
 def find_smallest_area():
 visited = set()
 smallest_area = height * width
 occupied_tiles = 0
 for y in range(height):
 for x in range(width):
 if board[y][x] != '':
 occupied_tiles += 1
 def bfs(start_x, start_y):
 nonlocal smallest_area
 queue = [(start_x, start_y)]
 area = 0
 while queue:
 curr_x, curr_y = queue.pop(0)
 if (curr_x, curr_y) in visited or not (0 <= curr_x < width and 0 <= curr_y < height) or board[curr_y][curr_x] != '':
 continue
 visited.add((curr_x, curr_y))
 area += 1
 for dir_x, dir_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
 new_x, new_y = curr_x + dir_x, curr_y + dir_y
 queue.append((new_x, new_y))
 smallest_area = min(smallest_area, area)
 for y in range(height):
 for x in range(width):
 if occupied_tiles + len(visited) == height * width:
 return smallest_area
 if (x, y) not in visited and board[y][x] == '':
 bfs(x, y)
 return smallest_area
 def rotateR(piece_coords):
 return sorted([[y, -x] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
 def rotateH(piece_coords):
 return sorted([[-x, y] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
 def backtrack(piece_index):
 nonlocal result,counter
 counter+=1
 if piece_index == len(sorted_pieces):
 result.append([row[:] for row in board])
 return True
 piece_name, piece_coords = list(sorted_pieces.items())[piece_index]
 reset_coords = piece_coords
 def try_place(x, y, piece_coords, placed_pieces, piece_index):
 if not piece_already_placed(piece_coords, placed_pieces):
 place_piece(piece_coords, x, y, piece_name)
 placed_pieces.append(piece_coords)
 if find_smallest_area() >= 5 and backtrack(piece_index + 1):
 return True
 remove_piece(piece_coords, x, y)
 return False
 for y in range(height):
 for x in range(width):
 if board[y][x] != '':
 continue
 placed_pieces = []
 piece_coords = reset_coords
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 for _ in range (3):
 piece_coords = rotateR(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 piece_coords = reset_coords
 piece_coords = rotateH(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 for _ in range (3):
 piece_coords = rotateR(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 return False
 start_time = datetime.datetime.now()
 backtrack(0)
 print("TOTAL BACKTRACKS",counter)
 print("Time to find: ",(datetime.datetime.now() - start_time).total_seconds(), "sec")
 return result[0]
def sort_pieces_by_length(piece_dict):
 sorted_pieces = dict(sorted(piece_dict.items(), key=lambda item: len(item[1]),reverse=True))
 for piece_name, piece_coords in sorted_pieces.items():
 sorted_pieces[piece_name] = sorted(piece_coords, key=lambda coord: (coord[0], coord[1]))
 return sorted_pieces
def piece_already_placed(new_piece, pieces):
 for piece in pieces:
 if are_pieces_same(new_piece, piece):
 return True
 return False
def are_pieces_same(piece1, piece2):
 # Calculate the biases on x and y axes
 piece1 = [coord.copy() for coord in piece1]
 piece2 = [coord.copy() for coord in piece2]
 for coord1, coord2 in zip(piece1, piece2): # move to the positive quadrant
 coord1[0] += 10
 coord1[1] += 10
 coord2[0] += 10
 coord2[1] += 10
 piece1 = sorted(piece1, key=lambda coord: (coord[0], coord[1]))
 piece2 = sorted(piece2, key=lambda coord: (coord[0], coord[1]))
 bias_x = piece2[0][0] - piece1[0][0]
 bias_y = piece2[0][1] - piece1[0][1]
 # Check if all corresponding coordinates are the same with the calculated biases
 for coord1, coord2 in zip(piece1, piece2):
 if coord1[0] + bias_x != coord2[0] or coord1[1] + bias_y != coord2[1]:
 return False
 return True
print(solve(5, 12, {'F': [[0, 0], [1, 0], [1, -1], [1, 1], [2, 1]], 'W': [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2]], 'V': [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]], 'X': [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]], 'N': [[0, 0], [0, 1], [1, 1], [1, 2], [1, 3]], 'P': [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2]], 'U': [[0, 0], [0, 1], [1, 0], [2, 0], [2, 1]], 'Z': [[0, 0], [1, 0], [1, -1], [1, -2], [2, -2]], 'I': [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], 'Y': [[0, 0], [1, 0], [2, 0], [2, 1], [3, 0]], 'T': [[0, 0], [0, 1], [0, 2], [-1, 2], [1, 2]], 'L': [[0, 0], [0, 1], [1, 0], [0, 2], [0, 3]]}))

It finds the correct solution, but I wanted to get all the solutions (or at least few more in reasonable time). I tried to do some optimization, but I think it 100% it is still falling into unnecessary recursive branches.
It finds one solution in ~22 seconds on my PC. I added print for counter of backtracks called and 23k seems too high.
The ×ばつ12 box has 1010 solutions (Wikipedia).
For sure there are some complex techniques to speed this up, but are there some trivial that could be added to my code?

Thanks for any help

import datetime
def solve(height, width, pieces):
 sorted_pieces = sort_pieces_by_length(pieces) # this makes it faster as it sort also coords of piece
 board = [['' for _ in range(width)] for _ in range(height)]
 result = []
 counter = 0
 def is_valid_placement(piece, x, y):
 first_coord = piece[0]
 if not (0 <= x < width and 0 <= y < height) or board[y][x] != '':
 return False
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 if not (0 <= nx < width and 0 <= ny < height) or board[ny][nx] != '':
 return False
 return True
 def place_piece(piece, x, y, char):
 first_coord = piece[0]
 board[y][x] = char
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 board[ny][nx] = char
 def remove_piece(piece, x, y):
 first_coord = piece[0]
 board[y][x] = ''
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 board[ny][nx] = ''
 def find_smallest_area():
 visited = set()
 smallest_area = height * width
 occupied_tiles = 0
 for y in range(height):
 for x in range(width):
 if board[y][x] != '':
 occupied_tiles += 1
 def bfs(start_x, start_y):
 nonlocal smallest_area
 queue = [(start_x, start_y)]
 area = 0
 while queue:
 curr_x, curr_y = queue.pop(0)
 if (curr_x, curr_y) in visited or not (0 <= curr_x < width and 0 <= curr_y < height) or board[curr_y][curr_x] != '':
 continue
 visited.add((curr_x, curr_y))
 area += 1
 for dir_x, dir_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
 new_x, new_y = curr_x + dir_x, curr_y + dir_y
 queue.append((new_x, new_y))
 smallest_area = min(smallest_area, area)
 for y in range(height):
 for x in range(width):
 if occupied_tiles + len(visited) == height * width:
 return smallest_area
 if (x, y) not in visited and board[y][x] == '':
 bfs(x, y)
 return smallest_area
 def rotateR(piece_coords):
 return sorted([[y, -x] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
 def rotateH(piece_coords):
 return sorted([[-x, y] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
 def backtrack(piece_index):
 nonlocal result,counter
 counter+=1
 if piece_index == len(sorted_pieces):
 result.append([row[:] for row in board])
 return True
 piece_name, piece_coords = list(sorted_pieces.items())[piece_index]
 reset_coords = piece_coords
 def try_place(x, y, piece_coords, placed_pieces, piece_index):
 if not piece_already_placed(piece_coords, placed_pieces):
 place_piece(piece_coords, x, y, piece_name)
 placed_pieces.append(piece_coords)
 if find_smallest_area() >= 5 and backtrack(piece_index + 1):
 return True
 remove_piece(piece_coords, x, y)
 return False
 for y in range(height):
 for x in range(width):
 if board[y][x] != '':
 continue
 placed_pieces = []
 piece_coords = reset_coords
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 for _ in range (3):
 piece_coords = rotateR(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 piece_coords = reset_coords
 piece_coords = rotateH(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 for _ in range (3):
 piece_coords = rotateR(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 return False
 start_time = datetime.datetime.now()
 backtrack(0)
 print("TOTAL BACKTRACKS",counter)
 print("Time to find: ",(datetime.datetime.now() - start_time).total_seconds(), "sec")
 return result[0]
def sort_pieces_by_length(piece_dict):
 sorted_pieces = dict(sorted(piece_dict.items(), key=lambda item: len(item[1]),reverse=True))
 for piece_name, piece_coords in sorted_pieces.items():
 sorted_pieces[piece_name] = sorted(piece_coords, key=lambda coord: (coord[0], coord[1]))
 return sorted_pieces
def piece_already_placed(new_piece, pieces):
 for piece in pieces:
 if are_pieces_same(new_piece, piece):
 return True
 return False
def are_pieces_same(piece1, piece2):
 # Calculate the biases on x and y axes
 piece1 = [coord.copy() for coord in piece1]
 piece2 = [coord.copy() for coord in piece2]
 for coord1, coord2 in zip(piece1, piece2): # move to the positive quadrant
 coord1[0] += 10
 coord1[1] += 10
 coord2[0] += 10
 coord2[1] += 10
 piece1 = sorted(piece1, key=lambda coord: (coord[0], coord[1]))
 piece2 = sorted(piece2, key=lambda coord: (coord[0], coord[1]))
 bias_x = piece2[0][0] - piece1[0][0]
 bias_y = piece2[0][1] - piece1[0][1]
 # Check if all corresponding coordinates are the same with the calculated biases
 for coord1, coord2 in zip(piece1, piece2):
 if coord1[0] + bias_x != coord2[0] or coord1[1] + bias_y != coord2[1]:
 return False
 return True
print(solve(5, 12, {'F': [[0, 0], [1, 0], [1, -1], [1, 1], [2, 1]], 'W': [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2]], 'V': [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]], 'X': [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]], 'N': [[0, 0], [0, 1], [1, 1], [1, 2], [1, 3]], 'P': [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2]], 'U': [[0, 0], [0, 1], [1, 0], [2, 0], [2, 1]], 'Z': [[0, 0], [1, 0], [1, -1], [1, -2], [2, -2]], 'I': [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], 'Y': [[0, 0], [1, 0], [2, 0], [2, 1], [3, 0]], 'T': [[0, 0], [0, 1], [0, 2], [-1, 2], [1, 2]], 'L': [[0, 0], [0, 1], [1, 0], [0, 2], [0, 3]]}))

It finds the correct solution, but I wanted to get all the solutions (or at least few more in a reasonable time). I tried to do some optimization, but I think it 100% it is still falling into unnecessary recursive branches.
It finds one solution in ~22 seconds on my PC. I added print for counter of backtracks called and 23k seems too high.
The ×ばつ12 box has 1010 solutions (Wikipedia).
For sure there are some complex techniques to speed this up, but are there some trivial that could be added to my code?

Thanks for any help.