import numpy as np
from collections import defaultdict
from typing import List, Tuple, Set, Optional
class EfficientRectangleSolver:
def __init__(self, board: List[str], pieces: List[List[int]]):
self.board = board
self.pieces = pieces
self.n, self.m = len(board), len(board[0])
# Convert board to efficient representation
self.free_cells = set()
self.occupied_mask = np.zeros((self.n, self.m), dtype=bool)
for i in range(self.n):
for j in range(self.m):
if board[i][j] == '0':
self.free_cells.add((i, j))
else:
self.occupied_mask[i, j] = True
self.total_free_area = len(self.free_cells)
self.total_piece_area = sum(h * w for h, w in pieces)
# Precompute valid placements for each piece
self.valid_placements = self._precompute_placements()
# Sort pieces by area (largest first) for better pruning
self.piece_order = sorted(range(len(pieces)),
key=lambda i: pieces[i][0] * pieces[i][1],
reverse=True)
def _precompute_placements(self) -> dict:
"""Precompute all valid placements for each piece"""
placements = defaultdict(list)
for piece_idx, (h, w) in enumerate(self.pieces):
# Try both orientations
for orientation, (ph, pw) in enumerate([(h, w), (w, h)]):
# Skip if same as original orientation for square pieces
if orientation == 1 and h == w:
continue
# Try all positions
for start_row in range(self.n - ph + 1):
for start_col in range(self.m - pw + 1):
# Check if placement is valid
cells = []
valid = True
for r in range(start_row, start_row + ph):
for c in range(start_col, start_col + pw):
if (r, c) not in self.free_cells:
valid = False
break
cells.append((r, c))
if not valid:
break
if valid:
placements[piece_idx].append((cells, orientation))
return placements
def solve(self) -> Optional[List[Tuple[int, int, int, int]]]:
"""
Solve using backtracking with optimizations
Returns list of (piece_idx, row, col, orientation) or None
"""
if self.total_free_area != self.total_piece_area:
return None
used_pieces = set()
occupied_cells = set()
solution = []
def backtrack() -> bool:
if len(used_pieces) == len(self.pieces):
return True
# Find the free cell with minimum remaining options (MRV heuristic)
best_cell = None
min_options = float('inf')
for cell in self.free_cells:
if cell in occupied_cells:
continue
options = 0
for piece_idx in self.piece_order:
if piece_idx in used_pieces:
continue
for cells, orientation in self.valid_placements[piece_idx]:
if cell in cells and all(c not in occupied_cells for c in cells):
options += 1
if options < min_options:
min_options = options
best_cell = cell
if options == 0:
return False # Dead end
if best_cell is None:
return len(used_pieces) == len(self.pieces)
# Try placing pieces that can cover best_cell
for piece_idx in self.piece_order:
if piece_idx in used_pieces:
continue
for cells, orientation in self.valid_placements[piece_idx]:
if best_cell not in cells:
continue
# Check if all cells are free
if any(cell in occupied_cells for cell in cells):
continue
# Pruning: check if remaining area matches remaining pieces
remaining_pieces = [i for i in range(len(self.pieces)) if i not in used_pieces and i != piece_idx]
remaining_area = sum(self.pieces[i][0] * self.pieces[i][1] for i in remaining_pieces)
available_area = len(self.free_cells) - len(occupied_cells) - len(cells)
if remaining_area != available_area:
continue
# Place piece
used_pieces.add(piece_idx)
occupied_cells.update(cells)
# Calculate placement info
min_row = min(r for r, c in cells)
min_col = min(c for r, c in cells if r == min_row)
solution.append((piece_idx, min_row, min_col, orientation))
if backtrack():
return True
# Backtrack
solution.pop()
occupied_cells.difference_update(cells)
used_pieces.remove(piece_idx)
return False
if backtrack():
return solution
return None
def visualize_solution(self, solution: List[Tuple[int, int, int, int]]) -> str:
"""Visualize the solution"""
if not solution:
return "No solution found"
# Create visualization grid
vis_grid = [list(row) for row in self.board]
for i, (piece_idx, row, col, orientation) in enumerate(solution):
h, w = self.pieces[piece_idx]
if orientation == 1:
h, w = w, h
# Mark the piece with its index
for r in range(row, row + h):
for c in range(col, col + w):
vis_grid[r][c] = str(piece_idx % 10)
result = "\n".join("".join(row) for row in vis_grid)
result += f"\n\nSolution uses {len(solution)} pieces:"
for i, (piece_idx, row, col, orientation) in enumerate(solution):
h, w = self.pieces[piece_idx]
if orientation == 1:
h, w = w, h
result += f"\nPiece {piece_idx} ({self.pieces[piece_idx][0]}x{self.pieces[piece_idx][1]}): position ({row},{col}), size {h}x{w}"
return result
sample_tests = [
[
[
' ',
' 00 0 ',
' 00 00 ',
' 0 00 ',
' 00 ',
' 00 0 ',
' 00 0 ',
' '],
[[1,1],[1,2],[1,2],[1,3],[1,3],[1,3],[2,2]]],
[
[
' ',
' 00000 ',
' 00000 ',
' 00000 00 ',
' 000 ',
' 00 000 ',
' 0000 00 ',
' 0000 00 ',
' 00 000 0 ',
' 0 000 0 ',
' 000 0 ',
' '],
[[1,1],[1,1],[1,2],[1,2],[1,2],[1,3],[1,3],[1,4],[1,4],[2,2],[2,2],[2,3],[2,3],[2,5]]],
[
[
' ',
' ',
' 00 00 ',
' 00 00 ',
' ',
' 0 00 0 ',
' 00 00 ',
' 000000 ',
' 000000 ',
' '],
[[1,1],[1,1],[1,2],[1,2],[1,2],[1,2],[1,3],[1,3],[1,4],[2,2],[2,2]]]
]
for board, pieces in sample_tests:
print("Board:")
for row in board:
print(row)
print(f"\nPieces: {pieces}")
print(f"Total free area: {sum(row.count('0') for row in board)}")
print(f"Total piece area: {sum(h*w for h, w in pieces)}")
solver = EfficientRectangleSolver(board, pieces)
print(f"\nSolving...")
solution = solver.solve()
print(solver.visualize_solution(solution))
To embed this program on your website, copy the following code and paste it into your website's HTML: