0125HardArrayBacktrackingAlgorithm X

Beacon Ridge Layouts

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A survey team is siting n radio beacons on a ridge that has been divided into an n by n lattice of pads. Every pad is either empty or carries exactly one beacon.

Two beacons jam each other when they sit on the same lattice row, on the same lattice column, or on a common 45-degree line running either way through the lattice. A siting is clean when all n beacons are placed and no two of them jam each other.

Return every clean siting. Draw each one as a list of n strings of length n, one string per row from the top row down, using "B" for a pad carrying a beacon and "." for an empty pad. The sitings may come back in any order. When no clean siting exists, return an empty list.

Examples

Example 1

Input: n = 2
Output: []

On a two by two lattice the two beacons always share a row, a column or a 45-degree line, so nothing is clean and the list comes back empty.

Example 2

Input: n = 6
Output: [[".B....", "...B..", ".....B", "B.....", "..B...", "....B."], ["..B...", ".....B", ".B....", "....B.", "B.....", "...B.."], ["...B..", "B.....", "....B.", ".B....", ".....B", "..B..."], ["....B.", "..B...", "B.....", ".....B", "...B..", ".B...."]]

Four clean sitings fit on a six by six lattice. In the first one the top beacon sits on pad 1 of its row, the next on pad 3, and so on down the ridge.

Example 3

Input: n = 5
Output: [["B....", "..B..", "....B", ".B...", "...B."], ["B....", "...B.", ".B...", "....B", "..B.."], [".B...", "...B.", "B....", "..B..", "....B"], [".B...", "....B", "..B..", "B....", "...B."], ["..B..", "B....", "...B.", ".B...", "....B"], ["..B..", "....B", ".B...", "...B.", "B...."], ["...B.", "B....", "..B..", "....B", ".B..."], ["...B.", ".B...", "....B", "..B..", "B...."], ["....B", ".B...", "...B.", "B....", "..B.."], ["....B", "..B..", "B....", "...B.", ".B..."]]

Ten clean sitings fit on a five by five lattice, and they may be listed in any order.

Constraints

1 <= n <= 9

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def beacon_layouts(n: int) -> list[list[str]]:

Java

public List<List<String>> beaconLayouts(int n)

The intended approach

Time O(n!) in the worst case, with O(1) work to test a padSpace O(n) for the recursion and the three key sets, excluding the returned sitings

Exactly one beacon lands on each row, so decide rows top to bottom and only choose a column for the current row. A column is blocked when it is already taken, or when the difference of row and column, or their sum, has been seen before: those two keys identify the two 45-degree lines through a pad. Keep the three keys in sets, recurse to the next row, and undo the three insertions on the way back out. Once all rows are filled, render the chosen columns as strings.

Pythonentry point: beacon_layouts

def beacon_layouts(n):
    layouts = []
    used_cols = set()
    used_down = set()
    used_up = set()
    picked = []

    def place(row):
        if row == n:
            layouts.append(["." * c + "B" + "." * (n - c - 1) for c in picked])
            return
        for col in range(n):
            if col in used_cols or (row - col) in used_down or (row + col) in used_up:
                continue
            used_cols.add(col)
            used_down.add(row - col)
            used_up.add(row + col)
            picked.append(col)
            place(row + 1)
            picked.pop()
            used_cols.discard(col)
            used_down.discard(row - col)
            used_up.discard(row + col)

    place(0)
    return layouts

The obvious version

Every clean siting is a permutation of columns, one per row, so generate all n! permutations and keep the ones where no pair of rows has a column gap equal to its row gap. Checks all pairs outright with no pruning and no incremental bookkeeping.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_beacon_layouts(n):
    from itertools import permutations
    found = []
    for order in permutations(range(n)):
        clash = False
        for r1 in range(n):
            for r2 in range(r1 + 1, n):
                if abs(order[r1] - order[r2]) == r2 - r1:
                    clash = True
                    break
            if clash:
                break
        if not clash:
            found.append(["".join("B" if order[r] == c else "." for c in range(n))
                          for r in range(n)])
    return found

How this problem was checked

Reference solution executed against 6 test cases — 6 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in