"""Reproduce Figure 1 and the search counts in Table 1. Run with Python 3.10+.""" from collections import Counter GRID = """ .......L....... .......L....... ......MLL...... .....MMLNN..... ....SMMDDNO.... ...SSIIDNNOJ... ..SSFFIIOOOJP.. KKKKFHHEEEEJPPP ..AKFHHGTTBJP.. ...CCCRGGTBJ... ....RRRGUTT.... .....RQUUU..... ......QQU...... .......Q....... .......Q....... """.split() BOARD = {(x - 7, y - 7) for y, line in enumerate(GRID) for x, token in enumerate(line) if token != "."} STEPS = ((1, 0), (0, 1), (-1, 0), (0, -1)) WEIGHT = {p: sum((p[0] + a, p[1] + b) not in BOARD for a, b in STEPS) for p in BOARD} RIM = {p for p in BOARD if WEIGHT[p]} ORBITS = [(7, 0), (6, 0), (5, 1), (4, 2), (3, 3)] EXPECTED = [(1176, 944160), (1168, 15893), (1148, 118978), (1130, 60023), (1127, 26437)] def normalize(points): xmin = min(x for x, y in points) ymin = min(y for x, y in points) return tuple(sorted((x - xmin, y - ymin) for x, y in points)) def orientations(points): return {normalize([(a * y, b * x) if flip else (a * x, b * y) for x, y in points]) for a in (-1, 1) for b in (-1, 1) for flip in (False, True)} def generate(): tiles = {} for y, row in enumerate(GRID): for x, label in enumerate(row): if label != ".": tiles.setdefault(label, set()).add((x - 7, y - 7)) assert Counter(map(len, tiles.values())) == {1: 1, 2: 1, 3: 2, 4: 5, 5: 12} free = {((0, 0),)} for order in range(1, 6): picture_shapes = {min(orientations(s)) for s in tiles.values() if len(s) == order} assert len(picture_shapes) == sum(len(s) == order for s in tiles.values()) assert picture_shapes == free if order < 5: grown = set() for s in free: for x, y in s: for dx, dy in STEPS: p = (x + dx, y + dy) if p not in s: grown.add(min(orientations(s + (p,)))) free = grown assert sum(WEIGHT[p] for s in tiles.values() if len(s) < 5 for p in s) == 4 assert len(RIM) == 28 and sum(WEIGHT.values()) == 60 assert Counter(WEIGHT[p] for p in RIM) == {2: 24, 3: 4} assert {tuple(sorted(map(abs, p), reverse=True)) for p in RIM} == set(ORBITS) rows = [] for label, tile in sorted(tiles.items()): if len(tile) < 5: continue for orientation in orientations(tile): for dx in range(-7, 8): for dy in range(-7, 8): placement = frozenset((x + dx, y + dy) for x, y in orientation) if placement <= BOARD and placement & RIM: rows.append((label, placement)) assert len(rows) == len(set(rows)) == 1176 return rows def cover(rows, hole): # Column for each constrained square and each piece. Primary columns # are all rim cells except the permitted defect. The rest are optional. points = sorted(BOARD) primary = sorted(RIM - {hole}) labels = sorted({label for label, part in rows}) offset = len(points) ci = {p: i for i, p in enumerate(points)} li = {label: offset + i for i, label in enumerate(labels)} usable = [(li[label], tuple(ci[p] for p in sorted(placement))) for label, placement in rows if placement & (RIM - {hole})] columns = [0] * (len(points) + len(labels)) occupied = [] for j, (label, squares) in enumerate(usable): col_ids = squares + (label,) occupied.append(col_ids) for i in col_ids: columns[i] |= 1 << j prim_index = {ci[p]: i for i, p in enumerate(primary)} covered, conflicts = [], [] for col_ids in occupied: covered.append(sum(1 << prim_index[i] for i in col_ids if i in prim_index)) conflict = 0 for i in col_ids: conflict |= columns[i] conflicts.append(conflict) prim_cols = [columns[ci[p]] for p in primary] nodes = 0 def search(need, candidates): nonlocal nodes nodes += 1 if not need: return 1 cells = need choices = 0 best = len(rows) + 1 while cells: bit = cells & -cells cells ^= bit choices_here = candidates & prim_cols[bit.bit_length() - 1] count = choices_here.bit_count() if not count: return 0 if count < best: best, choices = count, choices_here total = 0 while choices: bit = choices & -choices choices ^= bit j = bit.bit_length() - 1 total += search(need & ~covered[j], candidates & ~conflicts[j]) return total solutions = search((1 << len(primary)) - 1, (1 << len(usable)) - 1) return len(usable), nodes, solutions if __name__ == "__main__": rows = generate() print("Permitted hole / placements / nodes / solutions") for p, (placements, nodes) in zip(ORBITS, EXPECTED): result = cover(rows, p) assert result == (placements, nodes, 0) print(p, *result, flush=True)