Skyscrapers

Skyscrapers turns a Latin square into an aerial photograph. Each cell of an $n \times n$ grid holds the height of a building, a digit between $1$ and $n$; each row and each column is a permutation of those heights. The puzzle’s twist, new to this book, is visibility. Numbers written outside the grid along each edge record how many of the buildings in the corresponding row or column would be visible to an observer standing at that edge, with a taller building hiding every shorter one behind it.

The puzzle is sometimes attributed to Nikoli and sometimes to the broader tradition of Japanese visibility puzzles; an early form circulated at the World Puzzle Championship in the $1990$s. The cleanest way to treat it is as a constraint-satisfaction problem built on three layers: a Latin square at the base, and then, for each edge clue, a counting constraint expressed through a running maximum over the corresponding row or column.

Rules and a small instance

A Skyscrapers puzzle is an $n \times n$ grid. Each cell holds a digit from $1$ to $n$. Along any of the four sides of the grid, a subset of row- or column-positions carry a visibility clue: a positive integer.

1. Each row and each column contains every digit from $1$ to $n$ exactly once.

2. For any visibility clue $k$ placed at the edge of a row (or column), exactly $k$ cells of that row (column), read from the clue edge inward, are visible: not blocked by a strictly taller cell closer to the edge.

Figure 3.1 gives a $6 \times 6$ Skyscrapers puzzle with ten edge clues. The two west-edge clues sit on rows $3$ and $6$; the two east-edge clues on rows $2$ and $5$; the north and south edges carry three and three clues respectively.

The programming model

Let $x_{r,c}$ denote the height in cell $(r, c)$. The Latin-square layer is the usual pair of all-different families: $$\begin{align*} \operatorname{alldifferent}\bigl(\{x_{r,c} : c = 1, \ldots, n\}\bigr) && \text{for each row } r, \\ \operatorname{alldifferent}\bigl(\{x_{r,c} : r = 1, \ldots, n\}\bigr) && \text{for each column } c. \end{align*}$$

The visibility layer needs one new idea. For a given line of cells $v_1, v_2, \ldots, v_n$ read from a clue edge inward, define running max $M_0 = 0$ and $M_i = \max(M_{i-1}, v_i)$. Cell $i$ is visible from the edge exactly when $v_i > M_{i-1}$. The visibility count is $$\operatorname{vis}(v) \;=\; \sum_{i=1}^{n} \mathbf{1}[v_i > M_{i-1}],$$ and the clue $k$ on that edge imposes $\operatorname{vis}(v) = k$.

In CP-SAT, $M_i$ enters the model as an auxiliary integer variable tied to the previous $M$ and the current cell by a max constraint; $\mathbf{1}[v_i > M_{i-1}]$ is a boolean reified against the strict inequality. Each clue therefore adds $n$ auxiliary integer variables, $n$ booleans, and a single linear sum equation.

A solver in thirty-five lines

from ortools.sat.python import cp_model

def solve_skyscrapers(n, clues):
    """Solve an n x n Skyscrapers puzzle.

    clues : iterable of (side, idx, count) with
            side in {'N','E','S','W'}, idx 1-based.
    """
    m = cp_model.CpModel()
    x = [[m.NewIntVar(1, n, f"x{r}{c}")
          for c in range(n)] for r in range(n)]
    for r in range(n):
        m.AddAllDifferent(x[r])
    for c in range(n):
        m.AddAllDifferent([x[r][c] for r in range(n)])

    def add_vis(line, count):
        running = m.NewIntVar(0, n, "")
        m.Add(running == 0)
        vis = []
        for v in line:
            is_vis = m.NewBoolVar("")
            m.Add(v > running).OnlyEnforceIf(is_vis)
            m.Add(v <= running).OnlyEnforceIf(is_vis.Not())
            vis.append(is_vis)
            nm = m.NewIntVar(0, n, "")
            m.AddMaxEquality(nm, [running, v])
            running = nm
        m.Add(sum(vis) == count)

    for side, idx, cnt in clues:
        row = x[idx-1]
        col = [x[r][idx-1] for r in range(n)]
        if   side == 'W': add_vis(row, cnt)
        elif side == 'E': add_vis(row[::-1], cnt)
        elif side == 'N': add_vis(col, cnt)
        elif side == 'S': add_vis(col[::-1], cnt)

    s = cp_model.CpSolver()
    ok = s.Solve(m)
    if ok not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError("no solution")
    return [[s.Value(x[r][c])
             for c in range(n)] for r in range(n)]

The $6 \times 6$ instance of Figure 3.1 solves in about $11$ milliseconds and admits a single completion; the solver returns Figure 3.2.

A hard instance

Figure 3.3 is Mikhail Khotiner’s Puzzle $24$ from the janko.at Wolkenkratzer archive, graded there as the single hardest puzzle in the collection. The grid is $8 \times 8$, with four edge clues missing, one interior given digit at $(3, 3) = 4$, and visibility counts that force long chains of deduction. CP-SAT returns the unique completion (Figure 3.4) in about $40$ milliseconds.

What the running-max trick buys

The visibility count is non-convex in the raw heights; a naive formulation would enumerate the $n!$ permutations of each row and column, filtering by the visibility count. For $n = 6$ that is $720$ permutations per line, tractable but ugly. The running-max reification swaps the enumeration for a chain of $n$ auxiliary variables per clue; the solver’s propagation then stays local. Crucially, the reification is tight: if $v_i > M_{i-1}$ is forced true by domain reasoning, the booleans update without any search; if the strict inequality is forced false, likewise. Most real Skyscrapers puzzles have their visibility counts determined by the outer clues well before the Latin square is fully nailed down, and CP-SAT exploits this directly.

Two corner cases tighten the model without changing its surface. A clue of $1$ on a given edge forces the $n$ in the cell adjacent to that edge: nothing can be hidden behind a peak of height $n$, so exactly the one building is visible. A clue of $n$ forces the line to be the strictly-increasing permutation $1, 2, \ldots, n$: every building must be taller than all its predecessors. Either fact, fed into the model as a direct equality, cuts search further. Neither is needed for correctness; both are present in the propagator by implication.

Sources. Skyscrapers puzzles circulated at the World Puzzle Championship in the $1990$s and were popularised by Japanese publishers and Web-based puzzle sites in the following decade. The running-max reification used in the model is standard CP practice; see Simonis, Sudoku as a constraint problem (CP-AI-OR $2005$) for a closely related treatment of the Latin square layer, and Mladenović et al., Solving Skyscrapers puzzles with constraint programming, Computers & Operations Research $45$ ($2014$), for the full machinery. The CP-SAT solver’s AddMaxEquality and reified-boolean mechanisms are documented at developers.google.com/optimization.