Building Codeword: The Solver

After building Anarchy Chess, I wanted a daily word game to pair with it and landed on Codeword. A codeword starts with an open 13x13 crossword grid (around 120 white squares) with all of the clues removed. Instead, every white square carries a number from #1 to #26. Those numbers form a 1-to-1 substitution cipher for the alphabet: each number stands for one distinct letter from A to Z, all 26 letters appear somewhere on the grid, and typing L onto #2 fills every #2 square across the board.

Only two to four starter letters are revealed at the start, so cracking the rest is all about spotting word patterns and crossing letters. Under the hood, the Go CSP solver builds each day’s grids, checks that a human can deduce all 26 letters step by step without guessing, proves no second solution exists, and powers hints.

Building Anarchy Chess: The Solver

Way back in my first post on the solver, I used N-queens as a warm-up problem: place N queens on an NxN chessboard so none of them attack each other. Recently I turned a generalized version of that puzzle into a daily game called Anarchy Chess.

Instead of eight queens, each puzzle hands you a mixed tray of queens, rooks, bishops, and knights. In Anarchy mode, the board also comes with five immovable blocks: sliding pieces (queens, rooks, and bishops) stop at blocks, while knights jump right over them. Unlike the sudoku or crossword apps where you watch the solver show off, here you do the solving yourself while the Go CSP engine works backstage: verifying boards, cooking up balanced daily puzzles, and rescuing stuck players with hints.

Faster Search: Bitmask Constraint Propagation

In the previous post, I replaced map-backed live domains with []uint64 bitsets. That makes checking and flipping individual domain values cheap, which is great, except the original propagation loop was still polling Supported() on every single remaining value one at a time.

When a word has 15,000 candidates, calling Supported() 15,000 times just to cross off a single candidate is a lot of wasted work. In this post I’ll flip that around: letting constraints push prunings directly in bulk, and using precomputed bitmasks (bit patterns stored in uint64 slices) to filter thousands of candidates at once.

Faster Search: Live Domains as Bitsets

For a long time my CSP solver was “fast enough”, mostly because I threw 9x9 Sudokus and relatively tame crosswords at it. Recently I started pushing the crossword builder harder: larger word lists, full arc consistency, and searching for higher-scoring word fills instead of stopping at the first valid grid. My poor free-tier GCE VM was not thrilled.

Profiling made the bottleneck obvious. The solver was spending more time hashing Go maps, allocating temporary state, and checking words one by one than actually exploring the search tree. Over a series of posts, I’ll walk through the recent changes that fixed that:

  1. Packing live domains into bitsets (this post).
  2. Bitmask constraint propagation instead of checking values one by one.
  3. Flattening search state from Go maps into dense slices, and speeding up backjumping along the way.