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.

Testing

Testing is almost universal in software development, yet it’s common to treat it like a chore, or an after thought. Sure, test-driven development (TDD) is a means to influence what the public interface should look like by having the developer pretend the class already exists, and then implementing it to make the tests pass… but how often is TDD applied? And how often is it applied consistently? What’s the magic test-coverage percentage that you (or your lead) are satisfied with, and why that number, in particular? What the heck is “shifting left”, and how religiously shoud you stick to the test pyramid? Can automated testing happen in production?