How We Build Pentomino Levels with Dancing Links

Every Fit level in Pentolings is a promise: there is a way to fill this shape with these pieces. To keep that promise in 150 levels, and to give you a hint at any moment, the game contains a small solver based on Donald Knuth's Dancing Links. Here is how it works, using a tiny example anyone can follow. A pentomino puzzle is an exact cover problem Look at a level as a list of rules. Every piece must be used exactly once. Every square of the shape must be covered exactly once. Nothing may overlap and nothing may be left over. A problem made of rules like these is called an exact cover problem, and a lot of puzzles turn out to be exactly that, from Sudoku to scheduling. To get a computer to solve it, we write the problem as a table. Each column is one rule: a column for every piece, and a column for every square of the shape. Each row is one possible move: a specific piece, turned a specific way, placed at a specific spot. A row marks the columns it satisfies: the piece's own column, and the five squares it would cover. The puzzle is solved when you choose rows so that every column is marked exactly once. 63 positions: the rows of the table A pentomino can be turned and flipped, so first the game lists every different position of each of the twelve pieces. It rotates and mirrors the shape and keeps only the results that are really new. X gives 1 position, I gives 2, T, U, V, W and Z give 4 each, and F, L, N, P and Y give 8 each. That adds up to 63 positions for the whole set, a number the code checks. Then, for the level's shape, it slides each position to every spot where all five squares lie inside the shape. For a 3x20 rectangle with all twelve pieces, that makes 1236 candidate rows. For the biggest level, a 6x10 rectangle, there are 2056. The table has 72 columns: 12 pieces plus 60 squares. A tiny example Take a 3x5 rectangle and the pieces P, U and V. The table has 3 piece columns and 15 square columns, so 18 columns in all. The pieces have 40, 20 and 12 possible placements, which gives 72 rows. Choosing three rows that mark every column exactly once gives the answer: V on the left and bottom edges, U on the right, P in the middle. In text, the three rows of the board read VPPUU, VPPPU and VVVUU. Turning or mirroring the whole rectangle gives four versions of the same answer, so the solver finds four solutions that look the same to a person. Knuth's Dancing Links, in plain words The search is Algorithm X. Pick a column that is not yet covered. Try each row that marks it. Choosing a row means that its other columns are now taken, so every row that conflicts with it can be thrown away. Then repeat with the smaller table. If a column ever has no rows left, you made a wrong choice earlier, so you back up and try the next row. The clever part is how the table is stored. Donald Knuth observed that you can keep the marks in linked lists, where every mark points to its left, right, upper and lower neighbor. Removing a row is just re-pointing a few links, and the removed item keeps remembering where it was, so putting it back is a matter of reversing the steps. Because nodes seem to jump out and back in, he called the technique Dancing Links. In Pentolings, Dlx.kt is about eighty lines and works on plain integer arrays for speed. One more trick: at each step the solver picks the column with the fewest remaining rows. If a square can be covered in only two ways, the search quickly tests those two instead of wandering around the table. It is the computer version of what we said in the how-to guide: start with the tight spots. Locked pieces and levels that are fair Some Pentolings levels begin with a locked piece. Those pieces come from a real solution: the generator finds one answer, then freezes one or two of its pieces. The solver treats them as already chosen, removes their squares and columns from the table, and counts what is left. Making a level involves more than solving. A generator builds an outline by dropping the pieces next to each other at random, so a solution exists by construction. It then scores many outlines, rewarding solid shapes, penalizing holes and rewarding symmetry, and prefers shapes with more answers in early levels. Because outlines made this way usually have exactly one solution, the difficulty mostly comes from the number of pieces and the odd shape of the outline. Each of the 150 levels is solved again by the tests, checked for duplicates (a rotated or mirrored copy counts as the same), and the final level, a 6x10 rectangle, is the one place with a huge number of answers. A test also confirms the classic count for 3x20: eight, which is the two true answers times four ways to turn or mirror the rectangle. Why not just try everything? You could solve a puzzle by trying every piece in every position, one after another, and checking at the end. That does not work, even for a computer. With twelve pieces, 63 positions and dozens of spots, the number of combinations is astronomical, and almost all of them overlap or leave gaps in the first few moves. The trick is to stop a bad branch as soon as you can see it is bad. Algorithm X does exactly that. The moment one square has no piece that could still cover it, the search stops going deeper and backs up. Dancing Links makes each back-up cheap. This is why a 6x10 board, with 2056 candidate placements, is solved quickly even on a phone, and why the hint button does not need a server. What we learned The same solver logic exists twice: in Python, where the generator builds and checks the 150-level pack, and in Kotlin, which ships in the app. The Kotlin tests then solve every level of the pack again from scratch. Having two independent implementations means a mistake in one is unlikely to hide from the other. The biggest surprise was how rarely a random outline has more than one answer. We expected many puzzles to have several solutions and found the opposite. It turns out that this is fine: players care that a level is solvable and fair, not how many solutions exist, so the game accepts any valid fill. What the solver gives us is the promise that every level, and every hint, can be trusted. Hints come from the same solver The Hint button asks the solver a new question: given the pieces you have already placed, how does the rest fit? It treats your placed pieces as fixed, solves the remainder and highlights the next piece in the answer it finds. If you follow the hint, the next one can come from memory without solving again. The work runs in the background with a time limit so the screen never freezes. If your placed pieces make a solution impossible, the solver finds nothing and the game tells you so: no solution from here, take a piece back. That makes hints useful even when you are not stuck but just unsure. And the game accepts any valid way to fill the shape, not only the one the generator found, so you are never forced to guess the author's answer. FAQ What is an exact cover problem? A problem where you must choose some options so that every item is covered exactly once, with no overlaps and no leftovers. A pentomino puzzle is one. What are Dancing Links? A way, published by Donald Knuth, to store a search table in linked lists so that rows can be removed and restored very quickly during a backtracking search. Why do the pieces have 63 positions? Each of the 12 pieces can be rotated and flipped, and some of those positions look the same. Counting only distinct ones gives 63 across the whole set. Does the game have only one correct answer per level? No. The game accepts any valid way to fill the shape, even if it differs from the one the level was built from. If you want to see this in action, Pentolings is free on Google Play and needs no account. More notes like this one live on my site.