1205. How Many Seatings Avoid Every Forbidden Seat

There are n people and n seats, both numbered 1 to n. Row i of the board says which seats person i will accept: . for allowed and # for forbidden. Report how many ways there are to seat everybody, one person per seat.

Problem #1204 asks for the smallest such seating. This asks how many there are.

4 people, person 2 refusing seats 2 and 3 -> 12 4 people with nothing forbidden -> 24, which is 4! 4 people with only the diagonal forbidden -> 9, the derangements of 4

## What most people try first

Generate all n! orderings of the seats and count the ones that break no rule. That is O(n! * n) and it tests the rule only at the end, so an ordering whose first entry is already forbidden is still built in full. At n = 10 it is 3628800 orderings, which does finish, and it is still the wrong shape: the constraint can be tested the moment each person is seated, and then a forbidden first choice costs one node instead of 9!.

## The method

go(i, taken): if i == n: count += 1; return for s in 1 .. n: if s is forbidden for person i, or already taken: continue if some person after i has no allowed free seat: continue go(i + 1, taken + s)

This is #1204 with the early return removed, which is the same relationship #1203 has to #1202. The forward check in the middle line is the same one, and it is worth being careful about why it is still sound when counting: it skips only branches containing NO complete seating, so it removes nothing from the count. A prune that was merely unlikely to matter would be a different matter entirely, because an unsound prune when counting does not produce a wrong object, it produces a plausible number.

## What this number is

It is the permanent of the 0/1 matrix in which entry (i, j) is 1 when person i accepts seat j. The permanent looks like the determinant with all the signs made positive, and that small change makes it hard: there is no elimination method for it. Computing it faster than this search is possible, by Ryser's formula or by a subset dynamic programme over which seats are taken, both O(2^n * n) rather than O(n!), and at n = 10 that is the difference between a thousand states and three and a half million orderings. Those methods belong to the bitmask topic; the point here is that the backtracking count is the honest baseline they improve on, and that it is already much better than generating permutations.

## The closed forms that check the answer

With nothing forbidden every ordering counts, so the answer is n!. With exactly one cell forbidden the answer is n! - (n-1)!, because the seatings that use that one cell are counted by seating the other n-1 people freely. With exactly the diagonal forbidden the answer is the derangement number D(n), which satisfies D(n) = (n-1) * (D(n-1) + D(n-2)) with D(0) = 1 and D(1) = 0, giving 1, 0, 1, 2, 9, 44, 265 for n up to 6. Each of those is a test, and each is an independent fact rather than a second run of this program.

## Overflow

The largest value the constraints allow is 10! = 3628800, far below INT_MAX = 2147483647, so a 32-bit counter is correct. This is said explicitly because the counting problems in this block are where false overflow claims appear, and here there is genuinely nothing to claim.

## Cost

One node per legal prefix. The worst case is n! leaves, reached when nothing is forbidden, and the forward check cannot help there because no branch is dead. On a constrained board the saving is large and unbounded.

Constraints - `1 ≤ n ≤ 10` - every character is `.` or `#` - the answer is at most `10! = 3628800`, so it fits in a signed 32-bit integer