Glare-free floodlights

Two floodlights on the same line of a dockyard gantry shine into each other and blind the crane operator between them. Every arrangement that avoids it has to be listed, not just counted.

The problem

The gantry is an n × n grid of posts, rows and columns numbered 0 to n - 1. A floodlight throws four flat beams — along its row, its column, and both diagonals — so two lights glare at each other when they share a row, a column or a diagonal.

Lighting the yard takes n lights, which forces one per row. List every arrangement of n lights in which no two glare.

Input. n — the side of the grid.

Output. A sorted list of layouts, each drawn row by row with # for a post carrying a light and . for a bare post, rows joined with /.

Example.

n = 4  ->  [".#../...#/#.../..#.",
            "..#./#.../...#/.#.."]

The first puts lights at column 1 of row 0, column 3 of row 1, column 0 of row 2 and column 2 of row 3. No column repeats, and no pair is diagonal: rows 0 and 1 sit one row apart but two columns apart.

A second example, since the count does not simply grow with n:

n = 2  ->  []

On a 2 × 2 grid any two posts share a row, a column or a diagonal, so nothing is legal, and n = 3 is empty too. Then n = 5 has 10 layouts and n = 6 has 4.

Constraints.

• 1 <= n <= 9
• Return the layouts sorted as strings.

Hints

Approach

Brute force

Choose n posts from n² and test every pair: 260,887,834,350 choices at n = 9. One light per row cuts that to n^n, still 387,420,489 column tuples, each O(n²) to verify.

The insight

A light in row r, column c reaches the rows below through exactly three numbers — c, r - c and r + c — so extending a partial layout means picking a column whose three numbers are all still free.

Each diagonal family is constant along one expression: a down-diagonal holds a fixed row - col, an up-diagonal a fixed row + col. A set for each, plus one for columns, makes the legality test O(1) instead of O(n). The prune is sound because glare never repairs itself — two lights that clash still clash after more go up — so a conflicted partial layout dies whole. At n = 8 the search visits 2,057 nodes to find all 92 layouts, against 16,777,216 brute-force tuples.

Algorithm

1. Keep columns, the column chosen per filled row, and three sets: used_col, used_down for row - col, used_up for row + col.
2. place(row): when row == n, render columns and record the layout.
3. Otherwise, for each column c in 0 to n - 1, skip it if c, row - c or row + c is in its set.
4. Push c, add the three keys, call place(row + 1), then pop c and remove all three keys.
5. Sort the layouts and return them.

Complexity

Time O(n!) as a bound — row 0 has n columns, row 1 at most n - 1, and so on, plus O(n) per finished layout to render it; the sets prune far below that in practice. Space O(n) for the buffer, the sets and the stack, plus the output.

Solution

"""Glare-free floodlights — row-by-row backtracking with three conflict sets."""


def render(columns, n):
    """One layout as rows of '.' and '#', joined by '/'."""
    return "/".join("." * c + "#" + "." * (n - c - 1) for c in columns)


def solve(n):
    layouts = []
    columns = []
    used_col, used_down, used_up = set(), set(), set()

    def place(row):
        # Invariant: rows 0..row-1 hold exactly one light each, no two of them
        # share a column or a diagonal, and the three sets list precisely the
        # column, the down-diagonal (row - col) and the up-diagonal (row + col)
        # that those lights occupy.
        if row == n:
            layouts.append(render(columns, n))
            return
        for col in range(n):
            if col in used_col or row - col in used_down or row + col in used_up:
                continue
            columns.append(col)
            used_col.add(col)
            used_down.add(row - col)
            used_up.add(row + col)
            place(row + 1)
            columns.pop()                 # un-choose: one shared buffer
            used_col.discard(col)
            used_down.discard(row - col)
            used_up.discard(row + col)

    place(0)
    return sorted(layouts)

TESTS = [
    ((1,), ["#"]),
    ((2,), []),
    ((3,), []),
    ((4,), [".#../...#/#.../..#.",
            "..#./#.../...#/.#.."]),
    ((6,), [".#..../...#../.....#/#...../..#.../....#.",
            "..#.../.....#/.#..../....#./#...../...#..",
            "...#../#...../....#./.#..../.....#/..#...",
            "....#./..#.../#...../.....#/...#../.#...."]),
]

Pitfalls

• Removing only some of the three keys on the way back up. Drop the row + c removal and the up-diagonals stay marked forever, so later branches see phantom glare: n = 4 returns an empty list instead of two layouts, n = 6 nothing instead of four.
• Keeping both diagonal families in one set. A difference and a sum can be equal without any conflict — row 1 column 0 gives 1, row 0 column 1 also gives 1 — so legal layouts are rejected: n = 8 yields 12 layouts instead of 92.
• Recording the live columns list instead of a rendered string or a copy. Every entry points at the same list, which the un-choose steps empty on the way out, so the result is a run of identical empty layouts.

Variants

• Whole-turn gearing — the same shared-buffer recursion, but the constraint binds an item to its slot rather than one placed item to another, and it returns a count.
• Backtracking — the lesson on the choose, recurse, un-choose loop both problems run on.