Skyscraper puzzle with constraint module in python

Question

I have an assignment where I'm supposed to solve a skyscraper puzzle, this specific problem. It is a puzzle made in a grid 4x4 in which every field of the grid has a different value in rows and columns (sudoku like). The values inside the fields show us the height of the skyskcaper built on that field (1-4, 4 being the highest building). The numbers outside the grid are the number of skyscrapers visible from that direction. (eg. from this direction you can only see one skyscraper because the tallest (4 building) covers the view of the others -> 4312 <- from this direction you can see three buildings (only building with height 1 is covered)). Only the numbers on the outside are given, and you have to fill in the grid. More details about the rules of the game: here

This is the start state and this is one of the possible outputs.

I was trying, but i can't think of good constraints for the order of the buildings. I have just enter constraints for different values in rows and columns.

problem = Problem()

variables = range(16)
domains = range(1, 5)
problem.addVariables(variables, domains)

for row in range(4):
    problem.addConstraint(AllDifferentConstraint(), [row * 4 + i for i in range(4)])

for col in range(4):
    problem.addConstraint(AllDifferentConstraint(), [col + 4 * i for i in range(4)])


solution = problem.getSolution()
print(solution)

Answer 1

Here is a solution using MiniZinc (sorry for not providing a Python solution):

include "globals.mzn";

int: N = 4;
set of int: POS = 1..N;
set of int: SEEN = 1..N;
set of int: HEIGHT = 1..N;

array[POS] of SEEN: top = [2, 1, 2, 2];
array[POS] of SEEN: bottom = [2, 4, 3, 1];
array[POS] of SEEN: left = [2, 3, 1, 2];
array[POS] of SEEN: right = [2, 2, 3, 1];    

array[POS, POS] of var HEIGHT: height;

constraint forall(p in POS)
    (all_different(row(height, p)) /\
     all_different(col(height, p)));

predicate sum_seen(array[POS] of var HEIGHT: values, int: seen) = 
    (sum(i in 2..N)(values[i] > max([values[j] | j in 1..i-1])) = seen - 1);

constraint forall(p in POS)
    (sum_seen(row(height, p), left[p]) /\
     sum_seen(reverse(row(height, p)), right[p]) /\
     sum_seen(col(height, p), top[p]) /\
     sum_seen(reverse(col(height, p)), bottom[p]));

solve satisfy;

output ["height = "] ++ [show2d(height)];

The key observation is that, for each row, the number of times the maximum building height in the row increases should equal the number of buildings that are seen in that row (the given values). Corresponding holds for columns and reverse for rows and columns.