The Skyscraper puzzle has the goal of positioning Skyscrapers of $n$ different heights on an $n \times n$-Field so that the following requirements are met:
Every field contains a skyscraper.
All skyscrapers in a row/column have different heights. The field may have partially pre-set skyscrapers.
Numbers on the side of the field set the additional requirement that the row/column that the number belongs to have exactly that amount of skyscrapers visible from that position (See picture for better visualization). A skyscraper is considered visible from a position if all the skyscrapers inbetween the position and that skyscraper are smaller than it. If there is no number, then there is no such requirement for the row/column.
I have to formulate this into a CSP now. So far I have the following:
Variables: $X = \{x_{ij}\} \text{ with } i,j = \{1,...,n\}$
Domains: $D = \{D_{ij} = \{1,...,n\}\} \text{ with } i,j = \{1,...,n\}$
Now I am struggling with the constraints. Demanding all skyscrapers in a row/column to be different seems easy.
$\forall x_{ij}: x_{ij} \neq x_{i,l} (l \neq j) \land x_{ij} \neq x_{k,j}(k \neq i)$
I am struggling on the last two constraints though. Some of the fields may already have a pre-set skyscraper in them and I do not know how I can express that mathematically. Furthermore, the numbers which add further constraints to the rows and columns seem to be very hard to formulate elegantly. My only approach is something I haven't even managed to figure out how to write down exactly and it would entail constructing a set of sets which all contain fields. Those sets of fields represent a row/column. Then that set of sets is what represents the collection of rows/columns of which our field is made. Then I'd have to somehow double this list, associating each of these rows/columns with a direction in which it is read and then associate all of these elements with all possible constraint values. And then, a subset containing at most one of these elements per row/column + direction is what forms our constraints.
How can I formulate these two constraints in a more elegant form? Especially the second one, how can I represent that some rows may have such a constraint? How can I represent mathematically how many skyscrapers are visible in a row/column without having to chain many logical operations together?
Thanks for reading!
For each row or column, you can use an alldiff constraint: \begin{align} \operatorname{alldiff}(x_{i,1},\dots,x_{i,n}) &&\text{for $i\in\{1,\dots,n\}$} \\ \operatorname{alldiff}(x_{1,j},\dots,x_{n,j}) &&\text{for $j\in\{1,\dots,n\}$} \\ \end{align}
For fixed values $x_{i,j}=c_{i,j}$, you can limit the domain: $D_{i,j}=\{c_{i,j}\}$
The other constraints can be modeled via reification. Let binary decision variable $\ell_{i,j}$ indicate whether $x_{i,j}$ is taller than all cells to its left and impose \begin{align} \ell_{i,1} = 1 &&\\ \operatorname{reify}\left(\ell_{i,j}, \bigwedge_{k=1}^{j-1} (x_{i,j} > x_{i,k})\right) &&\text{for $j > 1$}\\ \end{align} The three "left" clues are then \begin{align} \sum_{j=1}^n \ell_{1,j} &= 3\\ \sum_{j=1}^n \ell_{2,j} &= 3\\ \sum_{j=1}^n \ell_{3,j} &= 4\\ \end{align} Similarly, introduce binary variables $r_{i,j}$, $t_{i,j}$, and $b_{i,j}$, for right, top, and bottom, respectively, along with the associated constraints.