1. Introduction#

Skyscraper is a logic puzzle described as follows: given an $n×n$ grid representing a city block seen from above, the player needs to fill each cell with the height of a building, from $1$ to $n$, satisfying the following conditions:

• Each row and each column contains every height from $1$ to $n$, each value appearing exactly once.
• Numbers placed outside the grid indicate how many buildings can be seen when looking into the grid from that side, where a building is considered visible if it is taller than all other buildings standing between it and the viewer.

Source: Conceptis Puzzles

To picture this, take a look at the example below.

Looking from the left, the building of height $3$ is visible (nothing stands in front of it), the building of height $1$ is hidden behind it, the building of height $5$ breaks through and is visible, and the remaining two buildings ($2$ and $4$) are both shorter than $5$ so they stay hidden - so exactly $2$ buildings are visible.

Below is an example of a 5×5 Skyscraper puzzle and its solution.

2. Modeling the puzzle#

Some symbols used in this problem

• $n$ is the size of the grid
• $F$ is the set of pairs $(i, j)$ representing the coordinates of the pre-filled cells in the grid
• $V(i, j)$ is the height filled in cell $(i, j) \in F$
• $\mathcal{L}$ is the set of sight lines: reading each row left-to-right and right-to-left, and each column top-to-bottom and bottom-to-top, gives $4n$ sight lines in total. For a sight line $L \in \mathcal{L}$, $L_p = (r_p, c_p)$ ($0 \leq p < n$) is the cell standing at position $p$ counting from the viewer, so $L_0$ is the cell closest to the viewer
• $v(L)$ is the number of buildings visible for sight line $L$

2.1. Decision variables#

For each cell $(i, j)$ in the grid and a height $k$, we build a variable $x(i, j, k)$ such that

$$x(i, j, k) = \begin{cases} 1 & \text{if cell } (i, j) \text{ has height } k \\ 0 & \text{otherwise} \end{cases}$$

2.2. Constraints#

• Each cell has exactly one height

$$\sum\limits_{k = 1}^{n}{x(i, j, k)} = 1, \\ \forall 0 \leq i, j < n$$

• Each row contains every height from $1$ to $n$, each value exactly once

$$\sum\limits_{j = 0}^{n - 1}{x(i, j, k)} = 1, \\ \forall 0 \leq i < n, 1 \leq k \leq n$$

• Each column contains every height from $1$ to $n$, each value exactly once

$$\sum\limits_{i = 0}^{n - 1}{x(i, j, k)} = 1, \\ \forall 0 \leq j < n, 1 \leq k \leq n$$

• Pre-filled cells

$$x(i, j, V(i, j)) = 1, \\ \forall (i, j) \in F$$

• The number of buildings visible on each sight line must match the requirement.

  Looking along a sight line $L$ from the viewer's side, a building is considered visible if it is taller than every building standing between it and the viewer. For each sight line $L \in \mathcal{L}$, position $0 \leq p < n$ and height $1 \leq k \leq n$, we build an additional intermediate variable $z_L(p, k)$ such that

$$z_L(p, k) = \begin{cases} 1 & \text{if the building at } L_p \text{ has height } k \text{ and no building at } L_0, \ldots, L_{p - 1} \text{ is taller than } k \\ 0 & \text{otherwise} \end{cases}$$

Let

$$T_L(p, k) = \sum\limits_{q = 0}^{p - 1}{\sum\limits_{k' = k + 1}^{n}{x(r_q, c_q, k')}}$$

be the number of buildings standing between the viewer and position $p$ on sight line $L$ that are taller than $k$ (this sum is simply $0$ when $p = 0$, since no building stands before the first one). Using the geometric method we can represent the variable $z_L(p, k)$ through the variables $x$ and $T_L(p, k)$ with the following conditions

$$\begin{cases} T_L(p, k) + p \cdot z_L(p, k) \leq p \\ x(r_p, c_p, k) - z_L(p, k) \geq 0 \\ x(r_p, c_p, k) - T_L(p, k) - z_L(p, k) \leq 0 \end{cases} \\ \forall L \in \mathcal{L}, 0 \leq p < n, 1 \leq k \leq n$$

Notice that we don't need to treat the closest building or the tallest building as special cases. When $p = 0$, $T_L(0, k) = 0$ for every $k$, so the conditions above reduce to $z_L(0, k) = x(r_0, c_0, k)$: the closest building is always visible, no matter its height. Likewise, when $k = n$, $T_L(p, n) = 0$ for every $p$, since no building is taller than $n$, so $z_L(p, n) = x(r_p, c_p, n)$: the tallest building is always visible, wherever it stands. Both edge cases hold automatically under the general formula, we don't need to add anything extra.

Finally, the requirement on the number of buildings that must be visible on sight line $L$ is satisfied by the condition

$$\sum\limits_{p = 0}^{n - 1}{\sum\limits_{k = 1}^{n}{z_L(p, k)}} = v(L), \\ \forall L \in \mathcal{L}$$

2.3. Objective function#

This problem does not have an objective function, as we are not aiming to minimize or maximize anything, all we need is to find a feasible solution. Technically, when programming, we can set the objective function to a constant (I often choose 0).

3. Conclusion#

The highlight of this puzzle lies in modeling the condition on the number of buildings visible along a sight line. It looks fairly simple at a glance, but turns out quite intricate once we have to build an entire system of intermediate variables and constraints to handle it.

For more Skyscraper puzzles and variations, please refer to Krazydad. The Python code for Skyscraper modeling is available at Tung-hehe.

Happy modeling!