Counting Knot Mosaics with ALLSAT (Student Abstract)

Hannah MillerAAAI 2023 · DOI

Introduction

Knot mosaics are $m \times n$ grid-based models used to represent quantum knot systems. Each cell in the grid is occupied by a specific tile—such as an arc, a straight line, or an empty space—which must connect to its neighbors to form closed loops. A fundamental challenge in this field is counting the total number of valid mosaics for a given grid size. While mathematical recurrence relations exist, they lack the flexibility needed to filter for specific knot types, such as the trefoil or figure-eight. This research explores using Boolean Satisfiability (SAT) and ALLSAT solvers to create a more adaptable counting toolkit.

Methodology

To count knot mosaics using logic solvers, the physical rules of the grid must be translated into propositional logic. The encoding involves three primary components:

  1. Variables: Each grid cell $(i, j)$ is assigned a variable representing one of the 11 possible tile types (T0 through T10).
  2. Connectivity and Boundary Constraints: Rules ensure that connection points on tile edges match their adjacent neighbors and that no "loose ends" exist at the grid boundaries.
  3. Exactly One (EO) Constraint: Each cell must contain exactly one tile. This is split into "At Least One" and "At Most One" (AMO) constraints.
The 11 basic tile types (T0-T10) used to construct knot mosaics.

The study compared two AMO encoding methods: the Pairwise Method, which explicitly forbids every possible pair of tiles in a cell, and the Sinz SEQ (Sequential Counter) method, which uses auxiliary variables to count tiles. These encodings were tested against two solver types: Blocking Clause (BC) solvers, which iteratively block found solutions, and Binary Decision Diagram (BDD) solvers, which represent the entire solution space as a graph.

Results and Analysis

The experiments demonstrated that BDD-based solvers are significantly more efficient for counting tasks than BC-based solvers. For instance, on a $5 \times 5$ board, the BDD solver finished in less than a second, whereas the BC solver required over 25 hours.

Performance comparison and solution counts for various grid sizes and encoding methods.

Counter-intuitively, the "naive" Pairwise encoding outperformed the more sophisticated Sinz SEQ method when used with BDD solvers. The Sinz method often exceeded the 16 GB RAM limit, likely because its auxiliary variables increased the complexity of the BDD graph. The power of this approach was highlighted by successfully counting over 47 quintillion ($47 \times 10^{18}$) valid configurations on an $8 \times 7$ grid in approximately 2.4 hours.

Conclusion and Future Work

This research proves that SAT-based methods, particularly BDD solvers with Pairwise encoding, provide a powerful alternative to traditional mathematical counting for knot mosaics. While the exponential growth of configurations remains a challenge—reaching a 24-hour timeout at the $7 \times 8$ grid size—the flexibility of SAT encoding opens the door for future work. The next phase of research will focus on refining these logic constraints to identify and count specific classes of knots, requiring more complex path-tracing logic to ensure all tiles belong to a single, continuous loop.

Summary updated

BibTeX
@inproceedings{miller2023counting,
  author = {Hannah Miller},
  title = {{Counting Knot Mosaics with ALLSAT (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.27002},
}

Loading related content...

Figure