About Penned
In the spring of 2023, my son asked me, “Can you make a word game out of Sudoku?”
I never cared much for Sudoku, though I did have a heavy KenKen habit at the time. Still do.
Once he asked, the answer was obvious. Start with a square grid where every row and every column uses each letter exactly once, the same way Sudoku uses digits. Draw cages across the grid, just as KenKen does, but where a KenKen cage solves an equation, a Penned cage is a path that spells a word. I printed several pages of 5×5 grids, and after a surprisingly long time, I had my first puzzle.
Making more of them, and better ones, turned out to be the hard part. Take a list of real words. How do you know it could make a legal puzzle?
The constraints are easy to state. The grid is a Latin square: the familiar one-per-row, one-per-column rule, with letters instead of digits. The word paths have to cover the grid, one per word, with no overlaps. And the puzzle has to have exactly one solution.
One consequence is that on an N×N board the words use exactly N distinct letters, each appearing N times. Another is that no word can have a double letter, since neighboring cells never match: PENNED itself will never appear in Penned. I call it the Latin Square Disjoint-Path Cover Problem.
My LSD-PCP habit started with that first grid. I could quit for months at a stretch. Then I couldn’t.
Recently I stopped trying to construct puzzles and started searching for them instead. I ran several search methods at scale, and they turned up thousands of valid puzzles. Nearly all of them were better than my original. Very few of them were good. Longer words matter. So does the balance of difficulty, and the way the paths fit together. I built a control center to monitor the searches, score the candidates, and schedule the ones that made the cut.
There’s a new run every day: four puzzles, 5×5 through 8×8, each one unlocking the next. Play as far as you like. Some go quickly. Some don’t. If you get stuck, put it down and come back later. Me, I can’t seem to stop, but we’ve established that I have problems.
Enjoy a challenge or pass the time. And Jacob, I hope you like your game.