1203. How Many Ways 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. Report how many ways there are to fill the empty cells so that each row and each column holds every value from 1 to n exactly once.

Problem #1202 asks for one completion, the smallest. This asks how many there are, and the difference changes exactly one thing in the code and two things in how you have to think about it.

3 by 3, empty -> 12 4 by 4, empty -> 576 5 by 5, empty -> 161280 5 by 5 with the first row fixed to 1 2 3 4 5 -> 1344

## What most people try first

Enumerate all n^(number of empty cells) fillings and test each one. On an empty 5 by 5 that is 5^25, which is about 3 * 10^17, so it does not finish. The reason it is so bad is that it tests the constraint only at the end: a filling whose first row already repeats a value is still carried all the way down and all 5^20 extensions of it are generated.

The fix is the same one as #1202. Test the constraint as each cell is filled, so a repeat is caught at the cell that causes it and everything below is never built.

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

## The one change from #1202, and the two consequences

The search is identical except at the leaf: instead of returning true and unwinding, add one to a counter and carry on. So the early return disappears.

The first consequence is that the cost is now proportional to the number of completions rather than to the depth of the first success. #1202 finishes instantly on the empty 5 by 5 because it stops at the first leaf; this problem visits all 161280 of them. That is why the size limit here is 5 and not 6: an empty 6 by 6 has 812851200 completions, which is a different kind of problem.

The second consequence is that the UNMARK now matters at every leaf, not only on failure. In #1202 a missing unmark produced a wrong none. Here it produces a count that is too small, silently, with no error anywhere, which is harder to notice and is exactly why the closed forms below are in the tests.

## The closed forms that check the answer

For an empty grid the answer is the number of Latin squares of order n, which is 1, 2, 12, 576, 161280 for n from 1 to 5. Those are facts about the object rather than outputs of this program, so they are a real check on it.

For a grid whose first row is fixed to 1 2 ... n and is otherwise empty, the answer is that number divided by n!. The argument: the n! ways of renaming the values act on the set of all Latin squares without fixing any of them, and each orbit contains exactly one square whose first row is 1 2 ... n, so the squares with that first row number one n!-th of the total. At n = 5 that is 161280 / 120 = 1344, which is a test.

## Overflow

The largest value this problem can produce is 161280, far below INT_MAX = 2147483647, so a 32-bit counter is correct and nothing needs a wide type. The number for n = 6 would be 812851200, which also fits, and n = 7 is 61479419904000, which does not; the size limit of 5 keeps both of those out of reach, so the absence of a 64-bit type here is a decision and not an oversight.

## Cost

One node per legal prefix, and the count of leaves is the answer, so the work is at least the answer. 161280 leaves at n = 5 is the ceiling the constraints impose.

Constraints - `1 ≤ n ≤ 5` - each grid entry is between `0` and `n` - the answer is at most 161280, so it fits in a signed 32-bit integer