A solver for A-Puzzle-A-Day from https://www.thingiverse.com/thing:4876979

a-puzzle-a-day-solver.py

# A solver for A-Puzzle-A-Day from https://www.thingiverse.com/thing:4876979
# Solutions are printed with terminal color escape sequences.

from typing import Dict, List, Tuple

import attrs
import numpy as np
import termcolor


def get_raw_board() -> List[List[str]]:
    raw_board = [
        ["Jan", "Feb", "Mar", "Apr", "May", "Jun", ""],
        ["Jul", "Aug", "Sep", "Oct", "Nov", "Dec", ""],
        list(map(str, range(1, 7 + 1))),
        list(map(str, range(8, 14 + 1))),
        list(map(str, range(15, 21 + 1))),
        list(map(str, range(22, 28 + 1))),
        ["29", "30", "31", "", "", "", ""],
    ]
    assert all(len(row) == 7 for row in raw_board)
    return raw_board


def get_board(*empty_cells: str) -> np.ndarray:
    assert len(empty_cells) == 2
    raw_board = get_raw_board()
    board = np.array(
        [[cell in {"", *empty_cells} for cell in row] for row in raw_board]
    )
    return board


def first_empty(arr: np.ndarray) -> Tuple[int, int]:
    assert arr.ndim == 2
    for i in range(arr.shape[0]):
        for j in range(arr.shape[1]):
            if not arr[i, j]:
                return (i, j)
    assert False


@attrs.frozen()
class Block:
    tiles: np.ndarray
    offset: Tuple[int, int] = (0, 0)

    @property
    def width(self) -> int:
        return self.tiles.shape[1]

    @property
    def height(self) -> int:
        return self.tiles.shape[0]


def get_blocks() -> List[List[Block]]:
    _blocks = {
        2: """
           X.X XXX XX. X... .X.. XX..
           XXX XXX XXX XXXX XXXX .XXX
           """,
        3: """
           X.. XX.
           X.. .X.
           XXX .XX
           """,
    }
    blocks = []
    for string in _blocks.values():
        parts = [line.split() for line in string.strip().splitlines()]
        for lines in zip(*parts):
            block = np.array([[ch == "X" for ch in line] for line in lines])
            variants = []
            for _ in range(2):
                for _ in range(4):
                    block = np.rot90(block)
                    if all(not np.array_equal(x, block) for x in variants):
                        variants.append(block)
                block = np.fliplr(block)
            blocks.append(
                [Block(tiles=block, offset=first_empty(~block)) for block in variants]
            )
    return blocks


@attrs.frozen()
class BlockPosition:
    x: int
    y: int
    variant: int


def repr_solution(
    blocks: List[List[Block]],
    block_positions: Dict[int, BlockPosition],
) -> str:
    assert set(block_positions.keys()) == set(range(len(blocks)))
    raw_board = get_raw_board()
    raw_board = [[cell[:2] if cell else "  " for cell in row] for row in raw_board]
    final_board = np.array(raw_board, dtype=np.object)
    for idx, pos in block_positions.items():
        block = blocks[idx][pos.variant]
        index = np.index_exp[
            pos.x : (pos.x + block.height), pos.y : (pos.y + block.width)
        ]
        label = termcolor.colored("  ", on_color=list(termcolor.HIGHLIGHTS)[idx])
        final_board[index] = np.where(block.tiles, label, final_board[index])
    lines = ["|" + "".join(row) + "|" for row in final_board]
    separator = "--" * (final_board.shape[1] + 1)
    return "\n".join([separator, *lines, separator])


def solve(cell1: str, cell2: str):
    board = get_board(cell1, cell2)  # false -> cell that can be placed
    height, width = board.shape
    blocks = get_blocks()

    solutions: List[Dict[int, BlockPosition]] = []
    block_positions: Dict[int, BlockPosition] = {}

    count = 0

    def dfs(depth: int) -> None:
        if depth >= len(blocks):
            assert set(block_positions.keys()) == set(range(len(blocks)))
            solutions.append(block_positions.copy())

            nonlocal count
            count += 1
            print(f"Solution {count}:")
            print(repr_solution(blocks, block_positions))
            return

        # Find first empty spot.
        first_x, first_y = first_empty(board)
        for block_id, block_variants in enumerate(blocks):
            if block_id in block_positions:
                continue
            for variant_id, block in enumerate(block_variants):
                x = first_x - block.offset[0]
                y = first_y - block.offset[1]
                if not (
                    0 <= x <= height - block.height and 0 <= y <= width - block.width
                ):
                    continue
                index = np.index_exp[x : (x + block.height), y : (y + block.width)]
                if np.any(board[index] & block.tiles):
                    continue
                board[index] |= block.tiles
                block_positions[block_id] = BlockPosition(x, y, variant_id)
                dfs(depth + 1)
                del block_positions[block_id]
                board[index] &= ~block.tiles

    dfs(0)
    print(f"{count} solutions")


if __name__ == "__main__":
    solve("Feb", "18")