Solving Skyscrapers by projecting permutations: a line has n! futures, not n^n

Skyscrapers (ビルディング) in the browser with an exact
line-projection solver inside. Fill an n×n grid with building heights so
every row and column holds 1..n exactly once, while every edge
clue counts the buildings visible from that side — taller buildings
hide everything shorter, so the visible ones are exactly the running
maxima. Humans open with a staircase rule (clue c caps the cell k
steps in at n−c+1+k); the solver's star is stronger: a line of a Latin
square is a permutation, so it has at most n! completions, not
n^n. Enumerate the permutations consistent with the current masks, keep
those matching both end clues, and intersect each cell with the
union of the survivors — the tightest line-local conclusion possible,
quietly subsuming hidden singles, naked pairs, and the staircase itself.
Solver-backed puzzle #16.

🌐 Live demo: https://sen.ltd/portfolio/skyscrapers/
📦 GitHub: https://github.com/sen-ltd/skyscrapers

The rules: visible = running maxima

A finished board satisfies:

1. Every row and every column holds each height 1..n exactly once (a Latin square).
2. Every edge clue equals the number of buildings visible from its side.

"Visible" has a one-line definition:

/** Buildings a viewer sees looking down the line: the running maxima. */
export function visible(heights: number[]): number {
  let seen = 0, max = 0;
  for (const h of heights) {
    if (h > max) { max = h; seen++; }
  }
  return seen;
}

In [2, 4, 1, 3] you see two buildings — 2, then 4; the 1 and the 3 hide in
the 4's shadow. The tallest building n is visible from everywhere. As in
Futoshiki, the unknown is a value in 1..n, so each cell is a candidate
bitmask.

The opening: a staircase of ceilings

The pencil-and-paper classic. Put height v in the cell k steps (0-based)
from a clue c, and every building taller than v must stand behind it —
work out how many "steps" that leaves in front and you get the ceiling
v ≤ n − c + 1 + k:

// initialState: a clue c carves staircase ceilings into its first c−1 cells
if (clue === 1) state[ordered[0]] &= 1 << (n - 1); // c=1: nearest cell IS n
for (let k = 0; k < clue - 1; k++) {
  state[ordered[k]] &= fullMask(n - clue + 1 + k);
}

c = 1 means one building visible: the nearest cell is the tower n itself.
c = n staircases the whole line into ascending 1, 2, …, n. Cheap and
satisfying — but strictly an opening. It sees nothing of the midgame.

The star: a line is a permutation, so project it

Here is the observation this puzzle rewards. When you want stronger
propagation you usually add named patterns one by one (hidden pairs, X-wing,
…). But a Skyscrapers line has decisive structure: a line of a Latin
square is a permutation of 1..n. A row doesn't have n^n possible
completions — it has at most n!. Even at n = 7 that's 5040. You can just
enumerate them.

export function projectLine(state: Uint16Array, view: View, n: number) {
  const union = new Array<number>(n).fill(0);
  // DFS over permutations consistent with the current masks.
  // The front clue prunes as we go: too many maxima already — cut;
  // not enough "headroom" left (remaining cells, remaining heights) — cut.
  // The back clue is checked at each leaf by a reverse scan.
  // Surviving permutations OR their values into union[i]…
  for (let i = 0; i < n; i++) {
    if (union[i] === 0) return false;   // no permutation survives: contradiction
    state[cells[i]] = union[i];         // intersect with the survivors' union
  }
}

Intersecting each cell with the union of surviving permutations is,
mathematically, the projection of the line constraint onto that cell —
the tightest conclusion any line-local reasoning can reach. Which means:

• hidden singles, naked pairs, and the staircase itself are all subsumed, silently;
• every line-local pattern that doesn't have a name yet gets "used" anyway.

Contradiction detection falls out for free. Opposite clues on one line can
sum to at most n + 1 (the tallest building is counted from both sides).
Put 3 + 3 on a 4-line: the staircase leaves every mask non-empty, yet
projection instantly reports zero surviving permutations:

it('detects a line with no surviving permutation', () => {
  const bad = puz([...], { left: ring('3...'), right: ring('3...') });
  expect(propagate(initialState(bad)!, geom(4), bad)).toBe(false);
});

What projection cannot do

Projection is complete per line, not per board. Rows constrain columns
and columns constrain rows back, so the projections are iterated to a
fixpoint; when even that stalls, a fewest-candidates backtracking
search branches, re-propagates, and counts. solveAll(p, 2) is a complete
enumeration that stops at two solutions, so length === 1 is a proof of
uniqueness.

Boards are authored by deletion

The generator works answer-first: build a random Latin square, read all
4n view clues off its edges (the board is trivially unique at that point),
then greedily delete clues in random order — givens first — keeping a
deletion only while the engine still proves exactly one solution. What
survives is locally minimal: removing any single remaining clue breaks
uniqueness, and the test suite checks that on every board:

it('is minimal: dropping the first view clue breaks uniqueness', () => {
  expect(hasUniqueSolution(dropped)).toBe(false);
});

Six boards, 4×4 through 7×7. The 4×4 pins a unique skyline with just
four view clues.

Takeaways

A Skyscrapers clue is a non-local aggregate — a count of running maxima
— that refuses to decompose into per-edge clamps the way Futoshiki's signs
did. What worked instead was a domain-structure observation: a line is a
permutation, so its futures number n!, not n^n, and enumerate → filter →
project (intersect with the survivors' union) becomes the strongest
line-local inference at a practical cost. The staircase opening is subsumed
by it; the cross-line remainder falls to fixpoint iteration and a
fewest-candidates search that proves all six boards unique. 56 tests.
Solver-backed puzzle #16.