1.py

#!/usr/bin/env python3

from shapely.geometry.polygon import Polygon
from shapely.geometry.multipolygon import MultiPolygon
from shapely.geometry.linestring import LineString
from shapely.affinity import rotate, translate
import shapely
import shapely.ops as ops
import matplotlib.pyplot as plt
import math
import numpy as np
import os
import sys
import time
import itertools


def draw_polygon(p, color):
    if type(p) is shapely.geometry.MultiPolygon:
        for x in p.geoms:
            draw_polygon(x, color)
        return
    xs = []
    ys = []
    for x, y in p.exterior.coords:
        xs.append(x)
        ys.append(y)
    plt.fill(xs, ys, color)


p1 = Polygon([(0, 0), (15, 0), (15, 15), (0, 15)])
p2 = Polygon([(0, 0), (29, 0), (29, 29)])
p3 = Polygon([(0, 0), (21, 0), (0, 21)])
p4 = Polygon([(0, 0), (20.5, 0), (31.1, 10.5), (20.5, 21), (0, 21)])
p5 = Polygon([(0, 0), (10.6, 10.6), (21.2, 0), (41.5, 21), (0, 21)])

p1 = translate(p1, 45, 5)
p2 = translate(p2, 0, 25)
p3 = translate(p3, 30, 25)
p4 = translate(p4, 38, 40)
p5 = translate(p5, 2, 2)


colors = ['red', 'orange', 'yellow', 'green', 'blue']
# Zip polygons with colors to have a consisten coloring.
polygons = list(zip([p1, p2, p3, p4, p5], colors))
dpi = 80
fig = plt.figure(dpi = dpi, figsize = (512 / dpi, 512 / dpi) )
plt.axis([0, 70, 0, 70])

for p, c in polygons:
    draw_polygon(p, c)

fig.savefig('initial-state.png')
plt.close()


def dfs(left: MultiPolygon, label: str, used: [], placed: [], polygons: [], side):
    eps = 0.05
    all = True
    for x in used:
        all = all and x
    if all:
        fig = plt.figure(dpi=dpi, figsize=(512 / dpi, 512 / dpi))
        plt.axis([0, side+1, 0, side+1])
        draw_polygon(left, 'black')
        for p in placed:
            draw_polygon(p[0], p[1])
        fig.savefig(f'{label}.png')
        plt.close()
        return True

    # (lines that slightly overlap the square, (dx, dy) of polygon to cover the square w/o thin
    # leftovers.
    checks = [(LineString([(-eps, eps), (side+eps, eps)]), (-3 * eps, -2 * eps)),
              (LineString([(side-eps, -eps), (side-eps, side + eps)]),
               (2 * eps, -3 * eps)),
              (LineString([(eps, -eps), (eps, side + eps)]),
               (-2 * eps, -3 * eps)),
              (LineString([(-eps, side-eps), (side + eps, side - eps)]), (-3 * eps, +2 * eps))]
    for p, u, i in zip(polygons, used, range(0, len(polygons))):  # which polygon
        if u:
            continue
        coords = list(p[0].exterior.coords)
        for xy, j in zip(coords, range(0, len(coords))):  # Vertice to place
            x, y = xy
            for a in range(0, 8):  # Rotations
                name = f'{label}{i}{j}{a}'
                for line, dxy in checks:
                    if not line.intersects(left):
                        continue
                    cross = line.intersection(left)
                    x0 = side
                    y0 = side
                    for cx, cy in cross.coords:
                        if (x0 > cx) or (np.isclose(x0, cx, atol=eps) and y0 > cy):
                            x0, y0 = cx, cy
                    x0 += dxy[0]
                    y0 += dxy[1]
                    t = translate(p[0], x0 - x, y0 - y)
                    t = rotate(t, a * 45, (x0, y0))
                    try:
                        intersection = left.intersection(t)
                        if not np.isclose(intersection.area, t.area, rtol=0.05):
                            continue
                        d = left.difference(t)
                        if type(d) is shapely.geometry.Polygon:
                            d = MultiPolygon([d])
                        if type(d) is shapely.geometry.MultiPolygon:
                            good = True
                            for g1 in d.geoms:
                                good = good and (len(g1.interiors) == 0)
                            if not good:
                                continue
                            used[i] = True
                            placed.append((t, p[1]))
                            try:
                                if dfs(d, f'{name}_', used, placed, polygons, side):
                                    return True
                            except KeyboardInterrupt:
                                sys.exit(1)
                            except Exception as e:
                                # print('exception', e)
                                pass
                            placed.pop()
                            used[i] = False
                    except KeyboardInterrupt:
                        sys.exit(1)
                    except Exception as e:
                        # print('exception', e)
                        pass
                    if len(placed) == 0:
                        # No reasons to check more intersection lines if it's a first polygon to place.
                        break
    return False
 

def solve(use: int):
    """ 
    fill a square using `use` polygons.
    """
    for j in range(1 << 5):
        t = 0
        # set position means that we marked this polygon as used already and it will not be placed again.
        used = [True] * 5
        sum = 0
        for i in range(5):
            used[i] = (j & (1 << i)) != 0
            if not used[i]:
                sum += polygons[i][0].area
                t += 1
        if t != use:
            continue
        print(used)
        side = math.sqrt(sum)
        square = Polygon([(0, 0), (side, 0), (side, side), (0, side)])
        if dfs(MultiPolygon([square]), '', used, [], polygons, side):
            return True
    return False


start = time.time()
if solve(4):
    print('found solution for 4')
    print(time.time() - start, 's')
start = time.time()
if solve(5):
    print('found solution for 5')
    print(time.time() - start, 's')

[True, False, False, False, False]
found solution for 4
15.22560167312622 s

[False, False, False, False, False]
found solution for 5
53.712339639663696 s