fillits

Fillits is a programming puzzle and packing challenge in which a set of tetromino-shaped pieces must be arranged into the smallest possible square without overlaps. Each piece is a connected group of four unit squares, typically encoded in a 4x4 grid where filled cells are marked with a character (often a letter identifying the piece) and empty cells with a dot or similar symbol.

Input and representation: In classic Fillit problems, each piece is provided as a 4x4 block containing exactly four filled cells. Pieces are usually separated by blank lines, and each piece is labeled with a unique letter. Although tetromino shapes in general include seven Tetris shapes (I, O, T, S, Z, L, J), the exact encoding focuses on the four-cell footprint and its placement on the board.

Objective and process: With N pieces, the total area is 4N. The goal is to place all pieces on an s by s board, where s is as small as possible and s^2 >= 4N. Pieces may be rotated and sometimes reflected, depending on the specific rules of the implementation. The standard solving method is backtracking: place pieces one by one, try all legal positions and orientations, and backtrack when a dead end is reached. Pruning and ordering heuristics (such as placing larger or more constraining pieces first) are common to improve performance.

Algorithms and variants: While simple backtracking suffices for modest numbers of pieces, more advanced solutions use exact cover formulations (Knuth’s Algorithm X with Dancing Links) to model the problem as a constraint-satisfaction task and search efficiently.

Origins and usage: Fillits has become a common educational exercise in algorithm design and constraint solving, notably in programming curricula and challenge communities. It serves as a practical example of tiling, packing, and backtracking techniques, often illustrating how to minimize search space while ensuring correctness.