Polyomino Calculator Final Project

CS 498TC: Computational Geometry at the University of Illinois Urbana-Champaign

I (very broadly) implemented the algorithms described in Counting Nonomino Tilings and Other Things of that Ilk as a final project. The implementation I have written has many low-hanging fruit optimizations, but this blog post is the start of a series where I make it faster and track “real-world” performance over time. The paper (as well as the latest version of my calculator at the time of writing) likes brute-force, so keep that in mind.

The paper defines four distinct problems:

1. Generate all valid “slice states”

2. Generate all valid relations between slice states

3. Generate all compositions of slice states (similar to a recurrence relation)

4. Generate a distinct tiling given a valid composition

The Basics

Slice States

A slice state is a layer in the recurrence relation. A slice state is defined by the following:

1. The length of each piece ID and the area beneath it in future slice states

2. The piece ID at each position in the slice sate

Here are some requirements that a slice state must satisfy:

1. Each position has a mapped piece ID

2. Each piece ID has a non-zero length

3. The sum of all volume under a piece ID (inclusive) must be divisible by the width of the board

4. Horizontal flips of the same piece are considered identical

5. Every position of a piece ID must be connect-able to every other position on the same slice through another slice

There are others, but these have the clearest goemetric interpretations (an example of a non-geometric requirement is a unique isomorphism of IDs).

Slice Relation

A slice relation is a mapping from one slice state to another slice state. A slice relation is defined by the following:

1. A source slice state and a destination slice state

2. A mapping from the source slice state piece IDs to the destination slice state piece IDs

3. Whether to flip the first slice state (the choice of first is arbitrary, continue to learn more)

The search space is much larger, but there are fewer constraints. Here are some requirements that a slice relation must satisfy:

1. There are no internal borders (i.e. the interiors of distinct pieces aren’t connected)

2. Either the volume of every piece increases by the number of occurrences in the new slice state or the piece does not exist in the next slice state

3. The mapping of pieces from the source to destination is valid

4. Every mapping of a piece has at least one point where the two connect at an edge

5. Only unique flips will generate a flip, non-unique flips must only be represented once

Recurrence Relation

The beginning and end of the tiling region is determined by the n-wide piece (it behaves in the same way as the outside). I can adjust the execution of the recurrence relation so it only generates the height with no excess on the left/right, but there is a 1-1 mapping between the two tilings so it does not matter at this time. Every function and it’s flip is checked, so we don’t consider flips of entire functions but do consider flips of only the source slice state (the choice of first is arbitrary, as the flip of the entire mapping is equivalent to only flipping the bottom).

Beyond the Basics

Generating a Tiling

Technically, the paper only “outlines” a method for generating an explicit tiling, so any generated result is beyond the original paper (granted, I haven’t ran to the 9x9 case, but computing some visual representation for any single tiling isn’t hard, the issues are storing the results and specifying which subset to run it on).

Reasonable Visualization

The basics are correct but the representation is pretty ugly. It looks like this:

I understand how to read this, but it’s very ugly and difficult to find bugs. I need a representation that looks like Tetris. Adjacency information is encoded on a slice-by-slice basis, and I can back-solve for mappings by composing piece maps together. Using these tools, I can:

1. Construct global graph piece IDs by reversing the piece maps of every slice relation above it

2. Construct a graph of global piece IDs by connecting all global piece IDs together by adjacent local slice state piece IDs

3. Color the graph (currently via brute-force, but the Four-Color Theorem gives us an upper complexity bound, which works well for us)

I did this and now have the following:

This looks much better, doesn’t it?

Future Steps

I’ll make it much faster, allow for rendering a specific tiling, and optimize for memory use. I’ll detail specific optimizations as I write them as individual blog posts in a series.