This project is an OCaml implementation of a solver for a complex "reverse" pentomino puzzle. The goal is not to tile a given shape, but rather to find the shape itself based on a set of interlocking constraints. The program determines which cells on a grid should be filled and which should be empty ("invisible blockers") to satisfy all rules.

The puzzle is defined on a square grid that is partitioned into concentric L-shaped "hooks" or "staircases". The solver finds a valid assignment of numeric labels to these hooks, a selection of cells that respects those labels, and a valid pentomino tiling of the resulting shape.

Imagine you have a big, flat Lego board, but instead of blueprints, you're given a strange set of magic rules to build a castle floor plan. This program's job is to figure out the one and only floor plan that follows all the rules.

The final goal is to create a shape on the board that can be perfectly covered by a set of 9 different Tetris-like pieces (called pentominoes).

The program needs to solve for everything at once, following a list of very strict rules. Using the Lego castle analogy, the rules are:

• The Rule of Numbers: The board is divided into 9 L-shaped color zones. The program must assign a unique number (1 through 9) to each zone. This number dictates exactly how many Lego studs of the castle's floor plan must be in that zone.
• The Rule of One: The final floor plan must be one single, connected shape. You can't have separate buildings.
• The Rule of the Perfect Fit: The final shape must be perfectly covered by the 9 different Tetris-like pieces, with no gaps or overlap.
• Weird Magic Rules: There are other strange rules, like the numbers in the zones covered by any single piece must add up to a number divisible by 5.

The puzzle is a "reverse" puzzle because you have to figure out the shape of the floor plan at the same time you figure out how the pieces fit on it.

A human could spend weeks trying to solve this and get nowhere. The number of possibilities is astronomical. This is why a computer program is needed.

The program works like a builder who is impossibly fast and patient, with a perfect memory. Its strategy is simple but powerful:

1. Guess Smartly: It starts by guessing an arrangement for the numbers in the color zones.
2. Build and Check: It begins laying down a floor plan, stud by stud, constantly checking if it's following the rules.
3. Fail Fast: The instant it breaks a rule (like the floor plan becoming two separate pieces), it immediately backtracks. It undoes its last move and tries a different one. It never wastes time continuing down a path that is already wrong.
4. Repeat Endlessly: If it builds a complete floor plan that follows the number rules, it then tries to cover it with the 9 special pieces. If they don't fit perfectly or break another rule, it scraps the entire floor plan and starts over with a new one.

The program does this millions of times per second, intelligently trying and discarding possibilities until it finds the one single solution that satisfies every single rule at once.

graph LR
    A["Start"] --> B["Parse Input File or Use Defaults"];
    B --> C["Step 1: Generate All Permutations of Region Labels"];
    C --> D{"Loop through each Label Permutation"};

    D -- "Next Permutation" --> E("Step 2: Backtrack Search to Select Cells");
    E -- "Forms a candidate shape" --> F{"Shape is Valid?<br/>(Connected, No 2x2s)"};
    
    F -- "Yes" --> G("Step 3: Backtrack Search to Tile Shape");
    F -- "No (Backtrack)" --> D;

    G -- "Finds a tiling" --> H{"Tiling is Valid?<br/>(Distinct Pentominoes)"};
    G -- "No Valid Tiling Found (Backtrack)" --> D;

    H -- "Yes" --> I{"Final Checks Pass?<br/>(Sum mod 5, Outside Clues)"};
    H -- "No (Backtrack)" --> G;

    I -- "Yes" --> J(("SOLUTION FOUND"));
    I -- "No (Backtrack)" --> G;

    J --> K["Print Solution & Exit"];
    D -- "All Permutations Tried" --> L["No Solution Found"];
    L --> M["End"];
    K --> M;

    style J fill:#9f9,stroke:#333,stroke-width:2px

A valid solution must satisfy the following conditions:

• Hook Partitioning: The N x N grid is partitioned into N concentric L-shaped regions, called hooks. Hook N is the center cell (or 2x2 block), hook N-1 surrounds it, and so on, up to hook 1 which is the outermost L-shape.
• Label Assignment: The integer labels from 1 to N must be assigned to the N hook regions, with each region receiving a unique label.
• Cell Selection: A set of cells on the grid is selected to be "filled". The number of filled cells within any hook region k must be exactly equal to the numeric label assigned to that region. *
• Connectivity: The entire set of filled cells must form a single, orthogonally connected shape.
• No 2x2 Blocks: The filled shape cannot contain any 2x2 blocks of cells.
• Pentomino Tiling: The filled shape must be perfectly tileable by a set of distinct pentominoes. For an N=9 grid, the total area is 1+2+...+9 = 45, which must be tiled by 45 / 5 = 9 distinct pentominoes.
• Sum Constraint: For each pentomino placed on the grid, the sum of the labels of the five hook regions it covers must be divisible by 5.
• Outside Clues: The solution must satisfy a given list of "outside" clues, which specify the first filled cell one would see looking from a particular edge of the board (e.g., "the first piece seen from the top in column 5 is a 'V' piece").

The final "answer" to the puzzle is typically the product of the areas of the contiguous empty regions (the "invisible blockers").

The solver uses a multi-level backtracking search algorithm to navigate the enormous search space.

• Level 1: Label Permutations: The top level of the search iterates through every possible permutation of assigning the labels (1..N) to the hook regions. This establishes the target size for each region.

• Level 2: Cell Selection Combinations: For a fixed label-to-region assignment, the solver enters a recursive backtracking search to select cells. It proceeds region by region, choosing a valid combination of cells within each hook to meet its target size.

  • Pruning: This stage is heavily pruned. The search backtracks immediately if a 2x2 block is formed or if a connectivity check determines that it's no longer possible for the final shape to be a single connected component.

• Level 3: Pentomino Tiling: Once a complete candidate shape of filled cells has been determined, the solver attempts to tile it. This is another backtracking search (place_pents) that tries to fit the required number of distinct pentominoes onto the shape.

• Final Validation: If a valid tiling is found, the solver performs the final checks: verifying the "sum divisible by 5" rule for each pentomino and ensuring all the "outside clues" are met.

If a candidate passes all checks, a unique solution has been found, and the program prints it and terminates.

The solver is written in OCaml and depends on the unix library for timing.

To compile the program, run:

ocamlc -o hooks unix.cma hooks.ml

Run the compiled executable from your terminal.

./hooks [options]

The following command-line options are available:

• --input <filename>: Specifies a path to an input file that defines the puzzle parameters. If omitted, the solver uses hardcoded defaults for a specific 9x9 puzzle.
• --minutes <int>: Sets a time limit for the search in minutes. Defaults to 5.
• --verbose: Enables verbose logging, printing status updates, and current search parameters.
• --promising: A debugging flag that prints a message each time the cell-selection search finds a partial assignment that looks promising.

Example:

./hooks --input my_puzzle.txt --minutes 10 --verbose

The input file is a plain text file that can define the grid size, outside clues, and pre-filled/empty cells. Lines starting with # are treated as comments and ignored.

• Sets the grid dimension. SIZE <N>
• Example: SIZE 9

Defines an outside clue. OUTSIDE <edge> <index> <value>

• <edge>: TOP, BOTTOM, LEFT, or RIGHT.

• <index>: The 1-based row or column index.

• <value>: The expected value. Can be a pentomino letter (e.g., F, I, X) or a number representing a hook's label

• Example: OUTSIDE RIGHT 2 U (The first piece seen from the right in row 2 is a U-pentomino)

• Example: OUTSIDE TOP 5 7 (The first piece seen from the top in column 5 has a label of 7)

Forces a cell to be a specific type. CELL <row> <col> <type> [value]

• <row>, <col>: 1-based coordinates of the cell.

• <type>: Can be DIGIT or EMPTY.

• [value]: If the type is DIGIT, this mandatory value specifies the hook label for that cell's region.

• Example: CELL 1 1 EMPTY (The cell at (1,1) must be empty)

• Example: CELL 5 5 DIGIT 9 (The cell at (5,5) must be filled and its region (hook 9) must have the label 9)

If a solution is found, the program prints the following:

• Region -> Label: The final mapping of hook regions to their assigned numeric labels.
• Filled Grid: A visual representation of the board, with . for empty cells and the assigned label number for filled cells.
• Pentomino Placements: A list of the pentominoes used in the tiling and their absolute 1-based cell coordinates.
• Empty-region areas: A sorted list of the sizes of each contiguous block of empty cells.
• Answer (product): The product of the empty-region areas.