Oatmeal - Constraint propagation for fun

5 min read Original article ↗

Constraint propagation for fun

I’ve been playing the very good Squeakross this weekend. It is adorable and the aesthetics are absolutely immaculate, but I’ve found the actual picross puzzles to be a point of frustrating friction in the game when compared to the picross-style puzzles in my bicross game.

Picross puzzles, aka nonograms, can relatively easily have ambiguous solutions. Because the hints only tell you how many consecutive blocks are in a row/column, they don’t tell you where they are. If the crossing hints (the perpendicular rows/columns) don’t provide enough information to nail down the blocks, they can float or swap positions while satisfying the clues.

Option A (Diagonal \ ):

[X] [ ] < 1
[ ] [X] < 1
 ^   ^
 1   1

Option B (Diagonal / ):

[ ] [X] < 1
[X] [ ] < 1
 ^   ^
 1   1

This, I learned to write this blog post, is called an “Elementary Switch.” Which is a 2 by 2 corner where the hints for both rows are 1 and the hints for both columns are 1. There are two valid ways to solve this, and the clues cannot distinguish between them.

The puzzles in Squeakross have this same problem, and the game accounts for this ambiguity by having a few different states that the hints can be in. I like this approach and find it compelling, but I kinda like the approach I took in bicross more.

A major difference in bicross from other picross-style games that I’ve seen is that the levels in bicross are procedurally generated and don’t correspond to some pixel-based image. In classic picross-style puzzles based on images, it is easy to have ambiguities like the elementary switch.

In games like Squeakross you can kinda guess your way around a situation like this because there’s no negative repercussion in a miss, but in bicross — especially the RPG and daily flavors — you can’t because of the HP system that punishes you for missing. For bicross, I needed provable solvability because I wanted to ensure that no matter the seed, the resulting level would never ask the player to make a random guess.

To fix this, I used a 3 step pipeline that generates a solution first, then tests it.

Step 1, generate a level

It starts with randomness. Using a seeded RNG, I generate a boolean grid. I immediately run a simple filter to make sure the game is in the “fun-zone,” a kind of arbitrary density measurement I came up with while play testing. The fun-zone checks to see if the grid’s density ks between 20% and 70%? If not, it’s trash and I throw it out. If yes, it moves on to the next step.

Step 2, constraint propagation

I calculate the hints (the numbers on the side, like 2 . 1 or 5) from the grid, and then throw the grid away. I ask a function called hasUniqueSolution:

Can you reconstruct the grid using ONLY these hints?

This function is kind of the “perfect logical player,” using iterative constraint propagation:

  • Permutation Generation: For every row and column, the solver calculates the complete search space—every possible valid arrangement of blocks that satisfies the hints.
  • Intersection: It stacks all those valid permutations on top of each other. If index 3 is filled in every single valid permutation for row 0, then (0,3) must be filled.
  • Pruning: If row 0 forces (0,3) to be filled, the solver zoots to the permutation list for column 3 and deletes any possibilities that don’t have a filled block at row 0.

Step 3, acceptance criteria

This pruning loop repeats, rows restricting columns, columns restricting rows, until it either solves the puzzle or gets stuck. Mathematically, a puzzle can have a unique solution that requires advanced look-ahead or backtracking, where if you place a block here, ten moves later you break the game, but that is some seriously big-brain-chess-playing-shit. Bicross’ solver verifies line solvability, so if it cannot force a solution using simple intersection logic it returns false. If it gets stuck, or if it finds ambiguity, like more than one valid permutation remaining, that level doesn’t get served up to the player. We burn it down and generate a new one.

A downside of this is that it uses CPU cycles. If you peek at the browser’s console, you can see that for every level played, the game usually generates and rejects 5-10 candidates in the background…which is also one of the reasons (the other one being mobile-friendliness) why I don’t generate levels larger than 10 by 10 grids. But I was honestly shocked that this pretty profoundly naive, action-heroically-brutish generate-and-solve loop is fast enough to run in the milliseconds during a level transition.

Proof in the pudding?

const propagate = (rows, cols, iteration) => {
    // Safety break for infinite loops
    if (iteration >= maxIterations) return { rows, cols };

    // 1. Filter rows based on current column possibilities
    const newRows = constrainRows(rows, cols);
    const rowsChanged = hasChanged(rows, newRows);
    
    // 2. Filter columns based on the new row possibilities  
    const newCols = constrainCols(newRows, cols);
    const colsChanged = hasChanged(cols, newCols);

    // Case A: Contradiction found (0 valid permutations left)
    if (isUnsolvable(newRows, newCols)) return null; 

    // Case B: Converged! No more changes possible (Solved or Stuck)
    if (!rowsChanged && !colsChanged) return { rows: newRows, cols: newCols }; 

    // Case C: Keep optimizing
    return propagate(newRows, newCols, iteration + 1);
};

Published

Tags