1202. The Smallest Way to Finish a Latin Square

An n by n grid is partly filled with values from 1 to n, and 0 marks an empty cell. Fill every empty cell so that each row holds every value from 1 to n exactly once and each column does too. Report the lexicographically smallest completion, reading the grid row by row and left to right within each row, or report that none exists.

4 by 4, only the top-left cell given as 1 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

## What most people try first

Fill each cell with the smallest value that does not clash with what is already in its row and column, and never look back. That is the greedy sweep, and it gets stuck. Consider a 3 by 3 grid where greedy fills the first row 1 2 3 and the second row 2 3 1; the third row is forced to 3 1 2 and happens to work. Now give the grid a single awkward value and greedy walks into a cell with no legal value at all, with no mechanism to undo the choice that caused it. Getting stuck is not rare here, it is the normal case once there are givens.

Undoing is the whole method: when a cell has no legal value, go back to the previous cell and try its next value.

## The constraint, stated once

A completed grid must have every value from 1 to n exactly once in each row and exactly once in each column. Equivalently, since each row holds n cells and n values, no value may appear TWICE in a row or twice in a column; being present everywhere follows from being absent nowhere. That equivalence is what makes the constraint cheap to test: a partial grid is extendable only if it has no repeat, and a repeat can be spotted the moment the second copy is placed.

So each row and each column carries a small set of the values already in it. With n at most 6 those sets fit in the low bits of one integer, and 1 << v tests and sets membership in a single operation. In JavaScript the bitwise operators truncate to 32 bits, which is harmless here because the highest bit used is bit 6.

## 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.

## Checking the givens before searching

The givens can already be contradictory, for instance two 1s in the same row. That must be detected, and the natural place is before the search starts: build the row and column sets from the givens, and if a value is being added to a set that already contains it, the answer is none immediately. Leaving it to the search would also work, but only by accident, because the search never reconsiders a given.

## The method

``` build the row and column sets from the givens; if any clash, answer none

go(p): # cells 0 .. p-1 are settled if p == n * n: return true r, c = p / n, p % n if cell (r, c) was given: return go(p + 1) for v in 1 .. n: if v is in row r or in column c: continue add v to both sets; write v if go(p + 1): return true erase v from both sets and from the cell return false ```

The pair of lines that add v and the pair that remove it are the mark and unmark that make the search a search. Forgetting the unmark is the classic defect, and it does not crash: it silently narrows every later branch, so the program reports none for grids that are perfectly completable.

## The settled boundaries

n = 1 has the single answer 1. A grid with every cell given is either already a Latin square, in which case it is its own completion, or contradictory, in which case the answer is none; both are tested. A grid with no givens always has a completion, and when n is a power of two the smallest one has a tidy description: cell (r, c) holds (r xor c) + 1. That is used in the tests as a closed-form check for n = 4, and it is worth noting that the cyclic square, whose rows rotate by one, is NOT the smallest: its second row is 2 3 4 1 and 2 1 4 3 beats it.

## Cost

One node per legal prefix. The number of Latin squares grows very fast, 576 at n = 4 and 161280 at n = 5, but the search here stops at the first leaf, so the cost is governed by how much backtracking the givens force rather than by the number of completions.

Constraints - `1 ≤ n ≤ 6` - each grid entry is between `0` and `n`