On the Exact Algorithmic Extraction of Finite Tesselations Through Prime Extraction of Minimal Representative Forms

This paper presents a hierarchical deterministic algorithm that extracts exact axis-aligned rectangular tessellations from finite planar grids by combining composite discovery, minimal representative form normalization, and prime extraction to address the limitations of existing symbolic pattern recognition methods.

The Gist

Imagine you are looking at a giant, colorful mosaic floor. To a human, it's easy to see: "Oh, that's just a small blue square repeated over and over." But to a computer, that floor is just a massive grid of numbers, and figuring out the repeating pattern is like trying to find a needle in a haystack made of other needles.

This paper presents a new, super-smart computer program designed to be a Pattern Detective. Its job is to look at a messy grid of data and answer three questions:

1. Where are the repeating patterns?
2. What is the smallest, simplest piece that makes up the pattern?
3. How can we rebuild the whole picture using just that tiny piece?

Here is how the paper's "detective" works, explained through everyday analogies:

1. The Problem: The "Fuzzy" vs. The "Exact"

Most computer vision today is like looking at a photo through a foggy window. It uses statistics to guess, "Hey, that looks like a brick wall." That's great for real-world photos, but terrible for puzzles or logic games where you need 100% certainty.

This paper says: "Let's stop guessing. Let's be exact." It treats the grid like a math puzzle where every piece must fit perfectly, with no fuzzy edges.

2. The Detective's Toolkit: Three Superpowers

The algorithm uses a three-step process to solve the puzzle:

Step A: The "Fold-and-Check" (Composite Discovery)

Imagine you have a large piece of fabric with a pattern. The detective first tries to fold the fabric in half.

• If the top half matches the bottom half perfectly, it knows, "Aha! This whole thing is just a smaller pattern repeated!"
• If the fabric has weird borders (like blank space around the edges), the detective trims them off first, just like a tailor cutting off the selvage.
• The Trick: Sometimes the fabric has an odd number of rows (like 5 rows). You can't fold 5 rows perfectly in half. So, the detective has a magic trick: it duplicates the middle row temporarily to make it even (6 rows), folds it, checks the match, and then forgets the duplicate. This ensures it never misses a pattern just because of an odd number.

Step B: The "Russian Nesting Doll" (Normalization)

Once the detective finds a repeating block, it asks: "Is this the smallest possible block?"

• Imagine a set of Russian nesting dolls. You open the big one, and there's a smaller one inside. You open that, and there's an even smaller one.
• The algorithm keeps "opening" the pattern (halving it) until it finds the smallest doll that cannot be opened any further. This smallest doll is called a "Prime."
• If the pattern is 1-2-1-2, the detective realizes it's just 1-2 repeated. It discards the big version and keeps the tiny 1-2.

Step C: The "Search and Skip" (Hierarchical Pruning)

This is where the algorithm gets really smart and saves time.

• Imagine you are searching a library for a specific book. If you find a book that is actually a collection of smaller stories, you don't need to search for those smaller stories individually later; you already know they are inside the big book.
• The algorithm builds a "tree" of possibilities. If it finds a big pattern, it marks all the smaller patterns inside it as "Already Found."
• The Result: It skips millions of unnecessary checks. In their tests, this "skipping" trick made the computer 5 times faster by ignoring work it had already done.

3. Two Ways to Solve the Puzzle

Once the detective has found all the "Primes" (the smallest building blocks), it tries to rebuild the original image in two different ways:

1. The "Cumulative" Strategy (The Master Builder): It tries to use a mix of big blocks and small blocks to build the image using the fewest total moves. This is like using a few large bricks and a few small ones to build a wall quickly.
2. The "Per-Level" Strategy (The Specialist): It looks at the problem level by level. "What if we only used the biggest blocks?" "What if we only used the smallest blocks?" This helps understand the trade-offs: big blocks are fewer but custom-made; small blocks are standard but require more pieces.

Why Does This Matter?

You might wonder, "Who cares about tiling grids?"

• Puzzle Solvers: This is the "brain" behind solving logic puzzles (like the famous ARC challenge) where AI usually fails.
• Manufacturing: Imagine a factory making tiles. If the machine knows the exact repeating pattern, it can cut fewer unique pieces and just repeat the same cut, saving money and time.
• Data Compression: If you know a huge file is just a small pattern repeated 1,000 times, you don't need to store the whole file. You just store the small pattern and a note saying "repeat 1,000 times."

The Bottom Line

This paper gives us a deterministic (guaranteed to be right) way to find the "DNA" of a pattern. It doesn't guess; it mathematically proves what the repeating unit is, handles messy odd-sized grids with a clever duplication trick, and skips redundant work to stay fast.

It's like giving a computer the ability to look at a complex quilt, instantly realize it's made of just three types of tiny squares, and tell you exactly how to sew it back together using the least amount of thread.

Technical Summary

1. Problem Statement

The paper addresses the challenge of deterministically identifying and extracting exact repeating patterns (tessellations) within finite, discrete planar grids. While statistical methods exist for recognizing patterns in noisy, real-world data (e.g., images), there is a significant gap in symbolic reasoning for exact extraction from structured grids.

Key characteristics of the problem include:

• Exactness: The solution must identify precise, axis-aligned rectangular tiles without approximation.
• Hierarchy: Multiple independent patterns may coexist, and a single tessellation may consist of hierarchical structures (tiles made of smaller tiles).
• Complexity: The problem involves corner cases such as odd-dimensional grids, irregular patterns, and the need to distinguish between a "composite" pattern and its "prime" (atomic) building blocks.
• Application: This is critical for tasks like the ARC-AGI challenge (Abstraction and Reasoning Corpus), routing matrix optimization, and path planning, where machine learning often fails due to a lack of large training datasets and the need for precise logical inference.

2. Methodology

The authors propose a three-phase hierarchical algorithm that combines composite discovery, normalization, and prime extraction. The approach relies on Breadth-First Search (BFS) pruning and specific handling of odd dimensions.

Phase 1: Composite Discovery

The algorithm scans the grid to find regions exhibiting internal overlap (repetition).

• Inspection: It first checks if the entire grid (or trimmed versions of it) can be split horizontally or vertically into two identical halves.
• Odd-Handling: For grids with odd dimensions, a selective duplication technique is used: the middle row or column is duplicated before splitting to enable overlap detection.
• BFS Pruning: If inspection fails, the algorithm performs a BFS on the trimmed grid, systematically removing edges (top, bottom, left, right) to explore all sub-rectangles.
• Branch Cutting: If a node in the BFS tree is identified as a composite, its descendants are skipped (pruned) to avoid redundant processing, as they are guaranteed to be contained within the larger composite.

Phase 2: Normalization

Once a composite is found, it is reduced to its Minimal Representative Form.

• Iterative Halving: The algorithm repeatedly attempts to split the composite row-wise and column-wise. If the halves are identical, the composite is replaced by the smaller half.
• Duplication: Similar to Phase 1, odd dimensions are handled by duplicating the middle row/column before splitting to ensure the pattern can be reduced to its atomic form.

Phase 3: Prime Extraction

The normalized composites are decomposed into Primes (atomic tiles that cannot be further reduced).

• BFS with Overlap Detection: The algorithm explores sub-rectangles. If a child node exhibits overlap, the overlapping part is normalized.
• Tessellation Verification: If the normalized prime perfectly tiles the child node, it is recorded with its repetition count (max uses).
• Hierarchical Filtering (Memoization): Composites are processed in descending order of size. If a smaller composite has already been discovered as a prime of a larger one, it is skipped. This drastically reduces the search space.

Dual-Strategy Solving

The paper introduces two strategies for assembling the final solution:

1. Cumulative Strategy: Incrementally combines primes from different BFS levels (Level 1, then 1–2, etc.) to find the global optimum with the minimum number of tile placements.
2. Per-Level Strategy: Solves the tiling puzzle independently for each BFS level, allowing for trade-off analysis between using fewer large custom tiles vs. more small standard units.

3. Key Contributions

1. Deterministic Algorithm for Exact Extraction: A novel algorithm that guarantees the identification of building-block tiles for 2D structures, filling a gap in symbolic grid analysis where ML approaches struggle.
2. Optimization Techniques:
   • Selective Duplication: A method to handle odd-dimensional grids during inspection/normalization without compromising efficiency in the BFS phase.
   • Hierarchical Filtering: A memoization technique that skips redundant processing of smaller composites, reducing computational overhead by up to 81% in tested scenarios.
3. Dual-Strategy Decomposition: A framework that provides both a globally optimal solution (minimum placements) and a granular analysis of decomposition alternatives (custom vs. modular tiles).
4. Open-Source Implementation: The authors provide a reference implementation and evaluate it on representative examples from the ARC-AGI challenge.

4. Experimental Results

The algorithm was evaluated on grids ranging from $2\times2$to$32\times32$ using three test cases:

• Band-in-blanks (6×6): A simple repeating pattern with blank borders.
• Mixed-noise (6×8): Irregular patterns with scattered noise.
• Simple-pattern (4×4): A perfect checkerboard symmetry.

Key Findings:

• Performance: Simple repeating tiles are detected in <1ms. Complex patterns requiring exhaustive search show exponential growth but remain tractable for the tested sizes.
• Efficiency: In the "Mixed-noise" case, hierarchical filtering allowed the algorithm to skip 81.25% (13 out of 16) of discovered composites, resulting in a 5.3× reduction in processing time for the most expensive phase.
• Scalability: Overlap detection (inspection) remains constant time, while pruning-based discovery grows exponentially, which is expected for exhaustive search problems.
• Solution Quality: The cumulative strategy successfully identified solutions with the minimum number of tile placements (e.g., 2 placements for complex noise patterns).

5. Significance and Limitations

Significance:

• ARC-AGI Relevance: Provides a robust, non-parametric module for solving ARC tasks that rely on identifying periodic structures, an area where current ML models underperform.
• Symbolic Reasoning: Offers a deterministic alternative to statistical pattern recognition, crucial for applications requiring exact logic (e.g., circuit routing, puzzle solving).
• Manufacturing & Assembly: The ability to decompose patterns into minimal primes and analyze trade-offs between custom and modular units has practical implications for material reuse and assembly planning.

Limitations:

• Scope Restriction: The algorithm is limited to exact equality, axis-aligned periodicity, and rectangular generators.
• Excluded Cases: It does not handle aperiodic tilings, rotated structures, or noisy/approximate patterns (though the authors suggest future work could address these via heuristic pruning or geometric pre-alignment).
• Complexity: The worst-case complexity for the puzzle solver remains exponential for highly irregular patterns.

In conclusion, this paper presents a rigorous, efficient, and deterministic framework for extracting exact tessellations from discrete grids, bridging the gap between mathematical tiling theory and practical algorithmic implementation for symbolic reasoning tasks.