Sudoku Bitmask Representation for Fast Solving

The idea behind a Sudoku bitmask representation

In a Sudoku bitmask representation, a set of digits is stored as a 9-bit integer instead of a list. Bit 0 stands for the digit 1, bit 1 for the digit 2, and so on up to bit 8 for the digit 9. A mask value of 1, written 0b000000001, means the digit 1 is present. A mask of 0b000000101 means digits 1 and 3 are present. This tiny idea replaces slow membership checks and array scans with single machine instructions, which is why it appears in almost every fast solver.

Track used digits per unit

Keep three small arrays: one bitmask per row, one per column, and one per box, each recording which digits are already used there. For a cell at row r, column c, in box b, the set of forbidden digits is simply rowMask[r] OR colMask[c] OR boxMask[b]. The set of legal candidates is the complement of that, limited to nine bits: NOT used AND 0x1FF, where 0x1FF is 511, the value with all nine low bits set. In one expression you have every digit that can legally go in that cell.

Fast operations you get for free

• Set a digit: mask = mask OR bit, where bit is 1 shifted left by digit minus one.
• Clear a digit: mask = mask AND NOT bit.
• Test a digit: (mask AND bit) is nonzero.
• Count candidates: use a population-count instruction on the mask.
• Isolate the lowest candidate: bit = mask AND minus mask.

Finding the most constrained cell

A strong solver always fills the cell with the fewest options next, the minimum-remaining-values heuristic. With a bitmask, that choice is almost free: compute each empty cell's candidate mask, take its population count, and pick the smallest. Because popcount is a single fast operation on modern processors, scanning the board for the most constrained cell costs very little. This pairing of bitmasks with MRV is a large part of why good solvers finish hard grids in milliseconds.

Iterating candidates one bit at a time

To try each candidate, loop over the set bits directly instead of testing 1 through 9. The expression bit = mask AND minus mask isolates the lowest set bit; the digit is one plus the number of trailing zeros in that bit; then mask = mask XOR bit removes it so the next iteration finds the following candidate. This walks only the digits that are actually possible, skipping the ones you already know are blocked.

Placing and undoing moves cheaply

Backtracking means constant placing and unplacing, and bitmasks make both trivial. To place a digit, OR its bit into the row, column, and box masks. To undo, XOR the same bit back out. There is no array shuffling and no reallocation, just three bit operations forward and three back. Cheap undo is what makes deep search affordable, because the solver may place and retract millions of digits on a stubborn puzzle.

A note on correctness and portability

Two details keep a Sudoku bitmask representation honest. Always mask results with 0x1FF so stray high bits never appear, and use your language's built-in popcount when it exists, since a hand-rolled loop undoes much of the speed benefit. With those in place, the same technique behaves identically across languages. It is exactly the kind of low-level optimization that powers the fast solver behind shapedoku.com, where nine shapes map to nine bits just as cleanly as nine digits do.