Gallery sweep

A camera sweeps its whole row, its whole column and both diagonals, and no two may end up in each other's sweep. Counting the layouts becomes tractable only once you notice how little freedom the rows have.

The problem

A museum gallery is size × size square tiles. A ceiling camera over a tile sweeps the full row it sits in, the full column, and both diagonals through it, out to the walls. Two cameras conflict if either lies in the other's sweep.

The curator wants size cameras installed with no conflict anywhere. Count the distinct layouts: two layouts differ when some tile holds a camera in one and not the other, and reflections count separately.

Input. size — an integer, the side of the gallery in tiles.

Output. The number of conflict-free layouts of size cameras.

Example.

size = 4   ->  2
size = 8   ->  92

On a 4 × 4 floor the only layouts put cameras in columns 2, 4, 1, 3 reading down the rows, and the mirror of that. Every other arrangement shares a column or a diagonal.

A second example, where the answer is zero:

size = 3   ->  0
size = 1   ->  1

Three cameras cannot avoid each other on a 3 × 3 floor, so the count is 0 — an answer, not a failure. A single tile is a layout of one camera.

Constraints.

• 1 <= size <= 12
• The answer fits in a 64-bit integer; at size = 12 it is 14,200.

Hints

Approach

Brute force

Choose size tiles out of size² and test every pair: on an 8 × 8 floor that is C(64, 8) = 4,426,165,368 layouts at 28 pair checks each. Even one column per row, tested at the end, is 8⁸ = 16,777,216 assignments.

The insight

size cameras across size rows with at most one per row forces exactly one per row, so the search is a choice of column for row 0, then row 1, and a conflict is three O(1) set lookups.

The pigeonhole step removes the row dimension from the decision entirely, taking the tree from C(size², size) leaves to at most size!. What is left is that a camera at (r, c) conflicts with an earlier one exactly when they share c, r - c, or r + c — and since rows fill top to bottom, the row never needs checking. Keep the three keys in three separate sets: r - c and r + c share a range, so one set would block legal columns.

Algorithm

1. Keep empty sets cols, down (r - c) and up (r + c).
2. place(r): if r == size, a layout is complete — return 1.
3. For each column c, skip it if c is in cols, r - c in down, or r + c in up.
4. Otherwise add all three keys, add place(r + 1) to a running total, then remove all three keys.
5. Return the total, starting from place(0).

Complexity

Time O(size!) as an upper bound — row r has at most size - r free columns and each node does O(1) work per column. Space O(size): the recursion depth, and one key per placed camera in each set.

Solution

"""Gallery sweep — backtracking one camera per row, with column and diagonal sets."""


def solve(size):
    cols = set()
    down = set()   # keys r - c: tiles on the same "\" diagonal share one
    up = set()     # keys r + c: tiles on the same "/" diagonal share one

    def place(row):
        # invariant: rows 0..row-1 each hold exactly one camera, and the three
        # sets hold exactly the keys of those cameras — so a column passes the
        # test here if and only if it conflicts with none of them.
        if row == size:
            return 1
        layouts = 0
        for col in range(size):
            if col in cols or (row - col) in down or (row + col) in up:
                continue
            cols.add(col)
            down.add(row - col)
            up.add(row + col)
            layouts += place(row + 1)
            cols.discard(col)
            down.discard(row - col)
            up.discard(row + col)
        return layouts

    return place(0)

TESTS = [
    ((4,), 2),
    ((8,), 92),
    ((3,), 0),
    ((1,), 1),
    ((2,), 0),
    ((6,), 4),
    ((9,), 352),
]

Pitfalls

• Using one set for both diagonal families. r - c = 2 and r + c = 2 collide, blocking legal columns: size = 4 reports 0 instead of 2, and size = 8 reports 12 instead of 92.
• Checking only the r - c diagonal. The mirrored conflicts survive, and size = 4 reports 7 instead of 2.
• Counting when the column loop ends instead of when r == size. Dead ends are counted as layouts, so size = 8 reports 644.
• Forgetting to remove the three keys after the recursive call. Every key ever placed stays blocked, the search dies in row 2 or 3, and every size above 3 returns 0.

Variants

• Greenhouse rotation — the same three-set conflict test, but the answer is a filled board rather than a count.
• Drill roster — one choice per level again, with the branch dying on length instead of on a conflict.