Abstract
Researchers have successfully applied Boolean Satisfiability (SAT) solvers to the complex combinatorial problem of enumerating knot mosaics. By encoding topological constraints into logic formulas, they reduced the computational search space by factors of up to 6,600, turning previously intractable problems into tasks that finish in seconds.
Problem Definition: The Knot Mosaic Challenge
In topology, a knot is a circle embedded in 3D space. To study them systematically, mathematicians often use knot mosaics—a way to represent knots on a grid (or board) using a specific set of 11 tiles, including straight lines, arcs, and crossings.
The primary challenge lies in enumeration: determining how many distinct, "nontrivial" knots can fit on a board of a specific size. As board dimensions increase, the number of possible tile combinations explodes combinatorially. Previous methods relied on manual scripts or complex counting arguments that struggled with larger grids. Furthermore, most random tile arrangements result in "trivial" knots (simple loops like the "unknot") or disconnected segments. The goal of this research is to efficiently filter the search space to identify only valid, topologically interesting knots.
Methodology: SAT-Based Encoding
This study treats the knot mosaic problem as a Boolean Satisfiability (SAT) problem. In this framework, every possible tile at every grid location is represented by a variable. The rules of knot theory are then translated into logical constraints that the SAT solver must satisfy. The paper introduces three levels of increasingly restrictive constraints:
- Basic Encoding: Ensures the board is "suitably connected" (no loose ends) and that tiles at the edges and corners are valid.
- Crossing Requirements: To avoid simple circles, the formula requires at least three crossing tiles (the minimum needed for the simplest nontrivial knot, the Trefoil).
- Banning Trivial Substructures: This advanced constraint identifies and forbids specific $2 \times 2$ tile patterns (like "caps" or "flips") known to be topologically reducible to simpler forms based on Reidemeister moves.
Key Results and Insights
The transition to a SAT-based approach led to dramatic performance gains. For a $5 \times 6$ board, the "Ban Trivial" constraint reduced the search space by a factor of 6,690x compared to the basic encoding. On a $6 \times 5$ board, where basic encoding timed out after 48 hours, the advanced constraints allowed the SAT solver to find all solutions in just 6 seconds.
Two critical insights emerged from this work:
- SAT as a Pruning Tool: SAT solvers are exceptionally effective at "pruning" the search space for topological problems by encoding local and semi-local rules, allowing the system to ignore billions of invalid combinations.
- Asymmetric Performance: The solver's internal heuristics are sensitive to variable processing order. For example, a $4 \times 6$ board and a $6 \times 4$ board are topologically identical, yet the solver's running time differed by 40% based on orientation.
Limitations and Future Work
The primary limitation is the "Single Loop" problem. Currently, the SAT solver may return "links" (mosaics containing multiple separate closed loops) rather than single knots. Future work aims to implement "coloring" algorithms within the SAT formula to ensure all tiles belong to a single continuous loop and to utilize parallel SAT techniques to tackle boards larger than $6 \times 6$.
Summary updated