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.

In classic N-queens, every column holds at most one queen, so you get a neat modeling shortcut: create one variable per column and only search over which row it occupies. That shortcut falls apart immediately here. Two knights or two bishops can happily share a column, and two rooks can stare right at each other on the same file as long as a block sits between them.

Going back to one variable per piece with all 64 squares (0..63) as its domain sounds much heavier, until you notice the board size. An 8x8 chessboard has 64 squares, which means an entire piece domain, a block layout, and an attack pattern each fit inside a single uint64. All of the bitset domain and bitmask propagation machinery I built for 15,000-word crossword domains drops down to single-register instructions here.

There is one catch when precomputing those masks: once you mix piece types, attacks stop being symmetric. Suppose search places a knight on d4, we still have an unplaced queen waiting in the tray, and d6 and f4 have blocks:

Asymmetric conflict bitmask with blocked squares Asymmetric conflict bitmask with blocked squares

Crossing off the eight squares the knight attacks (left board) isn’t enough. The knight doesn’t attack d1 or a7, yet dropping a queen on either square would immediately skewer the knight on d4. For any pair of pieces, the forbidden mask for the second piece has to combine both directions: squares the placed piece attacks and squares from which the second piece’s rays would reach back to hit it (middle board).

Look at the green squares (d7, d8, g4, h4) on that middle board, though. On an open chessboard, a queen on d8 or h4 would snipe d4 straight down the file or rank. With blocks on d6 and f4, those rays stop cold, leaving all four squares behind them completely legal for the queen - even as the knight’s own L-jumps hop right past d6 and f4 to threaten c6, e6, f5, and f3.

Precomputing one uint64 forbidMask for every (piece A, square, piece B) combination bakes all of that geometry in once up front:

forbidMask := blocked | knightSquare | attacksFromKnight
for sq := range 64 {
	if (queenAttacks[sq] & knightSquare) != 0 {
		forbidMask |= uint64(1) << sq
	}
}

Better yet, when I added the 5-block Anarchy mode later on, the solver itself needed zero new constraints or search logic. Blocks just swap in a fresh lookup table for that board’s five blocked bits and clear those five bits from each piece’s starting domain.

If a tray only had one of each piece, those conflict masks would be the whole story. Real puzzles have duplicates, though, and identical pieces are a classic trap for backtracking search.

Say a puzzle gives you four knights. If placing them on c3, d4, b6, and g7 leads to a dead end later on, swapping which knight variable sits on which of those four squares gives 4! = 24 “different” assignments that all produce the exact same board (with six knights, that jumps to 720). Left to its own devices, search will dutifully explore all 24 copies of every dead end before moving on.

Eliminating identical-piece permutations inside the same bitmask Eliminating identical-piece permutations inside the same bitmask

The standard fix is to force identical pieces to land in strictly increasing square order (sq(N0) < sq(N1) < sq(N2) < sq(N3)), keeping only the green ordering above. Normally you’d enforce that by adding ordering constraints between adjacent knights, giving the propagation loop extra work on every move.

Instead, because every pair of pieces already has its own 64-element forbidMask table, we can fold the ordering rule straight into that mask when building the problem. In the board on the right above, once N0 lands on square 18 (c3), N1’s mask for 18 has both N0’s red L-jump attacks and every lower-numbered square 0..17 (slate) set to 1. One bitwise pass clears both illegal attacks and duplicate permutations at zero extra cost during search.

Propagation between any two pieces then comes down to two fast cases:

  • When one piece is placed on a square, its precomputed uint64 mask clears every forbidden square from the other piece’s domain in one instruction.
  • Under arc consistency when neither piece is placed yet, the constraint bitwise-ANDs the forbid masks of every remaining live square of the first piece; any bit still set to 1 is ruled out by every surviving choice for the first piece, so it can be pruned from the second piece immediately.

Checking whether a tray of pieces fits on a board takes microseconds. Generating four daily puzzles (Easy, Medium, Hard, and Anarchy) that are actually enjoyable to play took a bit more trial and error.

The first surprise was that raw solution count is a terrible predictor of human difficulty. A tight puzzle with only four distinct solutions can feel breezy if bad openings run out of safe squares right away, while a puzzle with forty solutions can feel miserable if every natural-looking opening walks into a subtle dead end ten pieces deep.

The second surprise was what happened when I rewarded puzzles for leaving 0 unattacked empty squares without putting guardrails on the piece mix. Left unsupervised, the generator immediately fell in love with trays like “1 queen, 1 bishop, and 13 knights”. Knights have short, local attack patterns that pack into leftover pockets effortlessly, hitting 0 unattacked squares every time - and turning a chess puzzle into a repetitive clicking chore.

To keep puzzles varied and fair, each candidate mix now goes through a small pipeline:

Scoring and classifying candidate daily puzzles Scoring and classifying candidate daily puzzles

First, the generator shuffles combinations of queens, rooks, and bishops (Q, R, B) and binary-searches for the largest number of knights that still fits, subject to a hard balance cap: at most 6 knights, never more knights than sliding pieces (Q + R + B), and at most 5 bishops, plus a scoring penalty whenever any single piece type takes up more than 45% of the tray. Stepping down from that tightest knight count by 0..4 naturally yields Hard, Medium, and Easy candidates from the same base mix.

Each candidate then runs through three quick probes:

  1. Solver sample (25ms cap) collects up to 120 valid solutions, checking how few unattacked empty squares remain and making sure the solutions aren’t all just rotated or reflected copies of one layout.
  2. 2,500 random trials simulate a naive player by picking a random legal square for each piece in turn using pure uint64 bitmask ops. The fraction of trials that successfully place the whole tray gives a surprisingly good feel for how forgiving the board is: at least 6% lands in Easy, 1.2% to 6% lands in Medium, and below 1.2% lands in Hard.
  3. 5 forward-checking probes run short randomized forward-checking searches with a 500-step cap. If random play almost never wins and search consistently burns hundreds of backtracks, the board is a needle-in-a-haystack trap and gets tossed out.

Anarchy mode runs the same pipeline on five spread-out interior blocks (rows and columns 2..7, spanning at least four rows and four columns so they aren’t wasted in corners), aiming for Easy-comparable win rates. Candidates earn bonus points when sample solutions actively use blocks to shield sliding pieces from each other, and an extra boost when that exact tray of pieces would have zero solutions on an open board.

To keep my tiny E2 micro VM out of trouble, the solver server pre-generates a rolling 7-day horizon in the background and saves each day’s JSON to disk, so live traffic just reads ready-made puzzles from memory.

Hints are the one place where the solver runs live on every click. At first glance a hint sounds trivial: we already solved the puzzle during generation, so why not store one solution and reveal a piece from it?

Because players don’t read the solver’s mind. Most boards have several distinct solutions, and if you’ve already placed five pieces of your own, a hint that ignores your board isn’t much of a hint. Worse, it is very easy to place five pieces with zero red attack lines between them and still be walking dead because the remaining pieces in your tray can no longer coexist in the leftover space. Saying “no valid move” there is technically accurate and completely unhelpful; the player needs to know which piece to pick back up.

So every hint request hands the player’s current board straight to the solver:

Constructive vs. corrective hint pipeline Constructive vs. corrective hint pipeline

When none of the placed pieces attack each other, the solver locks them in as single-square domains and searches for a completion using a randomized value order. If one exists, we take the constructive path and reveal one unplaced piece from that completion, always preferring the most constraining piece left in the tray (Queen -> Rook -> Bishop -> Knight), since showing where a queen fits unlocks far more of the board than dropping a knight into a corner.

When the board already has a conflict or no completion exists, the hint flips to corrective mode and hunts for a culprit piece to remove in three quick stages:

  1. Drop 1 piece tests removing one placed piece at a time (checking pieces involved in direct attacks and the player’s most recent moves first) with a 20ms cap per check. As soon as the remaining board becomes solvable, it flags that piece for removal.
  2. Drop 2 pieces kicks in if no single removal saves the board, testing pairs in the same priority order within a 60ms total budget and flagging one of the two so the player makes progress right away.
  3. Closest solve is the safety net if a player has painted themselves three or four moves deep into a corner: it solves the empty board from scratch using a custom value heuristic that tries the player’s currently occupied squares first, preserving as much of their setup as possible, and flags one placed piece that doesn’t belong.

Because a single 8x8 solve usually finishes in well under a millisecond, even a multi-stage corrective hint comes back instantaneously.

My favorite part of building Anarchy Chess was how little custom solver code it actually needed. Once the 64-square board, block-aware conflict rays, and identical-piece ordering were packed into uint64 bitmasks, the exact same small CSP core handled solving, difficulty calibration, Anarchy board generation, and live hints.

I skipped over the frontend, daily archive, and timer/leaderboard setup here to keep this post focused on the solver side, so I may write those up separately later. In the meantime, if you want to give today’s boards a spin, they’re live at dawnofthe.dad/anarchy-chess, and thanks for reading!