Show problems as
Classic problem #51HardArrayBacktrackingAlgorithm X

N-Queens

Real-world version: Beacon Ridge Layouts
Tracked in this browser only
Read N-Queens on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBacktracking · Recursion, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def beacon_layouts(n: int) -> list[list[str]]:
Java
public List<List<String>> beaconLayouts(int n)

More on the same topics