Set grid boundaries and piece quantities on the left,
then click "Solve & Compute Tiling Matrix".
Algorithmic Complexity & Optimization Strategy
Exact polyomino grid packing is a variant of the NP-complete Exact Cover problem. A naive brute-force permutation explorer would quickly stall with combinatorial explosion (O(4^N × N!)). This solver implements four algorithmic pruning strategies to guarantee sub-millisecond execution:
1. Top-Left Anchor Placement
Instead of testing all board permutations, the solver scans sequentially for the first empty cell (top-to-bottom, left-to-right) and anchors the piece's first block directly onto it, collapsing symmetrical search trees.
2. Island Gap Flood-Fill Pruning
After each piece placement, a fast BFS flood-fill scans disconnected empty regions. If any enclosed pocket has an area not divisible by 4, the branch is culled immediately without further recursion.
3. Checkerboard Parity Theorem
Because every tetromino except the T-piece occupies 2 black and 2 white squares on an alternating checkerboard, an odd number of T-pieces cannot tile a board with equal black and white cells. The engine rejects impossible sets in O(1).
4. Distinct Rotational Deduplication
Pieces with rotational symmetries (like O-Square with 1 state, or I/S/Z with 2 states) are deduplicated ahead of time, eliminating redundant isomorphic checks in the recursion stack.
Erlando Aubrey
8+ years architecting mission-critical transactional platforms, event-driven message brokers, and deterministic engines. Available for Senior / Staff IC opportunities globally.