1207. Finishing a Sudoku, Smallest First

A Sudoku grid is n by n with n either 4 or 9, divided into n square boxes of side 2 or 3. Each cell holds a digit from 1 to n, and 0 marks an empty cell. A completed grid must have every digit from 1 to n exactly once in each row, exactly once in each column, and exactly once in each box. Given a partly filled grid, report the lexicographically smallest completion, reading the grid row by row, or report that none exists.

Problem #1202 is this without the box constraint. One extra constraint changes the difficulty out of proportion to the code it adds, and the reason is worth knowing: the boxes overlap the rows and columns, so a digit placed anywhere restricts three sets rather than two, and the restriction propagates much further.

4 by 4, box side 2, nothing given 1234 3412 2143 4321

## What most people try first

The obvious thing is to check each candidate digit by scanning its row, its column and its box, which is 3n comparisons per candidate and 3n^2 per cell. That is correct and it is the slow part of an otherwise fine program. The second obvious thing is to forget the box entirely and solve it as a Latin square, which produces a grid passing two of the three constraints; the 9 by 9 tests catch it immediately.

The thing that actually goes wrong, though, is neither of those. It is the UNMARK. Clearing the cell but forgetting to clear one of the three masks leaves a digit permanently claimed in a row, column or box it is not in, so the search reports none for grids that have a completion. With three masks instead of two there are three chances to get it wrong, and the symptom is the same in each case.

## Candidate sets as bits

Each row, column and box carries the set of digits already in it. With n at most 9 those sets live in bits 1 to 9 of one integer, so 1 << v tests and sets membership in one operation and the three tests together are three ANDs instead of 3n comparisons.

In JavaScript the bitwise operators truncate to 32 bits. The highest bit used here is bit 9, so that is harmless, and it is worth saying rather than assuming: a 16 by 16 Sudoku would use bit 16 and still be fine, while anything needing bit 32 would not be.

## Why the answer is the SMALLEST one and not just any one

There are usually many solutions, and a list of them has no order anyone can guess, so the answer is pinned to a single object: read the assignment as one sequence in the stated reading order and return the one that is smallest compared position by position. That makes the answer unique, which means a program is either right or wrong rather than differently right.

It also makes the search simpler, not harder. Fill the positions in reading order, and at each position try the values in increasing order. The FIRST complete solution the search reaches is then the smallest one, because any other solution differs from it at some position where it chose a larger value, and a larger value at the earliest difference is exactly what larger means. There is no comparison step and nothing is kept to compare against.

## Box indexing, which is where the off-by-one lives

With box side s, the cell at row r and column c is in box

(r / s) * s + c / s using integer division

Reading that as r / s + c / s or as (r / s) * n + c / s are the two mistakes people make, and both produce a program that solves the 4 by 4 and fails the 9 by 9, because at n = 4 with s = 2 several wrong formulas happen to agree with the right one on enough cells. The 9 tests are the ones that matter here.

## Checking the givens first

The givens can already be contradictory: two 5s in a box, say. Building the three mask sets from the givens before searching detects that, and the answer is none. One of the tests is a valid puzzle with a single given changed so that a column repeats, and it must report none rather than quietly solving around it, which a program that only looks at empty cells would do.

## The method

``` side = 2 if n == 4 else 3 build rowm, colm, boxm from the givens; if any clash, answer none

go(p): if p == n * n: return true r, c = p / n, p % n if (r, c) was given: return go(p + 1) bx = (r / side) * side + c / side for v in 1 .. n: if v is in rowm[r], colm[c] or boxm[bx]: continue add v to all three; write v if go(p + 1): return true remove v from all three; erase the cell return false ```

## The ordering this problem deliberately does not use

The standard speed-up for Sudoku is to fill the cell with the FEWEST candidates next rather than the next cell in reading order. It is a large win and it is not available here, because it would find some completion rather than the smallest one: the lexicographic order is a statement about reading order, so the search has to commit to the earliest unsettled cell before any later one. That is a real cost of pinning the answer, and it is the honest reason the answer is pinned anyway: without pinning it, five reference solutions would return five different valid grids and the problem would be unanswerable.

## Cost

One node per prefix the three masks admit. The constraints make the admitted set small, which is exactly why Sudoku is solvable by search at all: an empty 9 by 9 grid has about 6.7 * 10^21 completions, and the search still reaches the first one quickly because it never has to look at the others.

Constraints - `n` is 4 or 9 - every character is a digit from `0` to `n` - the box side is 2 when `n` is 4 and 3 when `n` is 9