Gallery Ceiling Sensors
An art gallery is fitting motion sensors to a square ceiling made of n × n panels. Each sensor sends beams along its row of panels, its column, and both diagonals, all the way to the walls. If a beam reaches another sensor, the two set each other off, so no two sensors may share a row, a column or a diagonal.
Some panels are glass skylights. Nothing can be mounted on glass, but beams pass straight through it. The gallery needs exactly n sensors and wants to know how many different layouts are possible before choosing one.
Your task
Write countLayouts(ceiling). ceiling is a list of n strings of length n; ceiling[r][c] is '.' for a normal panel and '#' for a skylight. Return the number of ways to place n sensors on normal panels so that no two share a row, a column or a diagonal.
Two layouts are different if some panel has a sensor in one and not in the other. Skylights do not block beams. If no layout exists, return 0.
countLayouts(ceiling: string[]) → int
Examples
ceiling = ["....", "....", "....", "...."]
2
There are exactly two layouts on an open 4 × 4 ceiling. Writing the sensor's column for each row, they are 1, 3, 0, 2 and its mirror image 2, 0, 3, 1. Every other try puts two sensors on a shared column or diagonal.
ceiling = [".#..", "....", "....", "...."]
1
The skylight is at row 0, column 1. The layout 1, 3, 0, 2 needs a sensor exactly there, so it is gone. The mirror layout 2, 0, 3, 1 does not touch the skylight, so 1 layout is left.
ceiling = ["#"]
0
A 1 × 1 ceiling needs one sensor, and its only panel is glass. No layout.
Constraints
- 1 ≤ n ≤ 10
- Every row of ceiling has length n.
- Each character is '.' or '#'.
Start with brute force
Choose any n of the n² panels and check whether the sensors clash. On a 10 × 10 ceiling that is about 17 trillion ways to choose 10 panels out of 100, far too many.
Even the smarter brute force, one sensor per row and per column (every ordering of the columns), is 10! = 3,628,800 full layouts, each checked at the end. Most of them clash in the first two or three rows, so building the rest of the layout is wasted work.
Hints
0 of 4 shown- Hint 1
On a 4 × 4 ceiling with 4 sensors, how many sensors can a single row hold? So how many does each row end up with?
- Hint 2
Exactly one sensor per row. That turns the problem into a sequence of choices: pick a column for row 0, then a column for row 1, and so on. A choice is allowed only if the panel is not glass and no sensor placed so far watches it.
- Hint 3
A sensor at (r, c) watches column c, the diagonal where every panel has row − col = r − c, and the diagonal where row + col = r + c. Keep three lists of booleans (columns, row − col, row + col) so each check is instant. Shift row − col by n − 1 so it is never negative.
- Hint 4
Write
count(row): ifrow == n, all sensors are placed, so return 1. Otherwise add upcount(row + 1)for every allowed column, marking the column and both diagonals before the call and clearing them after. A row with no allowed panel returns 0 straight away and the search backs up.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Two observations make this manageable. First, each row holds exactly one sensor, so you only choose a column per row. Second, a panel's diagonals are identified by row − col and row + col, so "is this panel watched?" is three lookups.
Trace the open 4 × 4 ceiling, writing a layout as the chosen columns so far:
- Row 0 at column 0. Row 1 can use column 2 or 3. With
0, 2, every panel in row 2 is watched: dead end. With0, 3, row 2 takes column 1, then every panel in row 3 is watched: dead end. So column 0 in row 0 gives 0 layouts. - Row 0 at column 1. Row 1 can only use column 3, row 2 only column 0, row 3 only column 2. All rows filled: count 1.
- Row 0 at column 2 is the mirror image of column 1: count 1. Column 3 is the mirror of column 0: count 0.
Total 2. The most common bug is checking only one diagonal direction; on the open 4 × 4 ceiling it would also count 3, 2, 1, 0, where all four sensors sit on one diagonal. The second is forgetting to clear the three marks after the recursive call, which makes later branches see sensors that are no longer there.
function countLayouts(ceiling) {
const n = ceiling.length;
const colUsed = new Array(n).fill(false);
const downUsed = new Array(2 * n - 1).fill(false); // same row - col
const upUsed = new Array(2 * n - 1).fill(false); // same row + col
function count(row) {
if (row === n) return 1; // one sensor in every row
let total = 0;
for (let col = 0; col < n; col++) {
const d = row - col + n - 1, u = row + col;
if (ceiling[row][col] === '#' || colUsed[col] || downUsed[d] || upUsed[u]) continue;
colUsed[col] = downUsed[d] = upUsed[u] = true;
total += count(row + 1);
colUsed[col] = downUsed[d] = upUsed[u] = false;
}
return total;
}
return count(0);
}def count_layouts(ceiling):
n = len(ceiling)
col_used = [False] * n
down_used = [False] * (2 * n - 1) # diagonals with the same row - col
up_used = [False] * (2 * n - 1) # diagonals with the same row + col
def count(row):
if row == n:
return 1 # one sensor in every row
total = 0
for col in range(n):
d, u = row - col + n - 1, row + col
if ceiling[row][col] == '#' or col_used[col] or down_used[d] or up_used[u]:
continue
col_used[col] = down_used[d] = up_used[u] = True
total += count(row + 1)
col_used[col] = down_used[d] = up_used[u] = False
return total
return count(0)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.