reset password
Author Message
Kasutiryo
Posts: 6
Posted 19:35 Nov 06, 2019 |

I am trying to make a constraint where for example

constraint n > 3
such that n for x in set of elements 1..N {
if the element[x] satisfies some statement then n++ 
}

Is something like this possible in minizinc?

This is my code so far, but it doesn't work of course since I'm not quite sure how to represent the statement above in a constraint.

% skyscrapers https://www.conceptispuzzles.com/index.aspx?uri=puzzle/skyscrapers
include "alldifferent.mzn";
int: N = 4;
array[1..N, 1..N] of var 1..N: board;
% Each row must have all different numbers
constraint forall(i in 1..N)
              (alldifferent( board[i, 1..N] ));
% Each column must have all different numbers
constraint forall(j in 1..N)
              (alldifferent( board[1..N, j] ));
/* My first thought in order to figure out the number of visable skyscrapers within a column and row in a specified order matches the number given is to count how many numbers in a column or row, is greater than the first element in the column or row. For example, in following row...
                                         2 -> | 3 1 2 4 |
Starting from the left hand side...
                                         1 > 3 = False
                                         2 > 3 = False
                                         4 > 3 = True
Since, we can safely assume that the first element/skyscraper in the row is always going to visable we can start with number_of_visable_skyscrapers = 1. And with every element greater than the first one, we can add one two that number.
In which the constraint will be something like: if element[1,2] > element [1,1] then number_of_visable++
                  1  2
                  |  |
                  V  V
         | _, _, _, _ |
         | _, _, _, _ | <-2
     1-> | _, _, _, _ |
         | _, _, _, _ |
                  ^
                  |
                  3
*/
% facing south, there should be 1 visable skyscrapers from the north to the south of column 3
constraint x > 1 forall(i in 1..N)(if board[i,3] >= board[1,3] then x++ endif)
% facing south, there should be 2 visable skyscrapers from the north to the south of column 4
% facing north, there should be 3 visable skyscrapers from the south to the north of column 3
% facing east, there should be 1 visable skyscraper from the west to east of row 3
% facing west, there should be 2 visable skyscrapers from the east to west of row 2
Last edited by Kasutiryo at 19:50 Nov 06, 2019.
rabbott
Posts: 1649
Posted 21:11 Nov 06, 2019 |

Assume you have an array of ints and want to know how many of them are greater than the first element.

Will this help?

int: array_size = 7;
array[1..array_size] of int: a_row = [3, 1, 2, 4, 1, 8, 5];
var 1..array_size-1: tall_ones;
% Booleans can be treated as 0..1;
constraint tall_ones == sum([a_row[i] > a_row[1] | i in 2..array_size]);

output [show(tall_ones)];

 

P.S. Don't think in terms of x++. That's for procedural languages. MiniZinc is purely declarative.

Last edited by rabbott at 21:32 Nov 06, 2019.
Kasutiryo
Posts: 6
Posted 13:33 Nov 08, 2019 |

Thanks that helps a lot. I've managed to get these similar constraints working correctly (not including the commented ones out). 

% facing south, there should be 1 visible skyscraper from the north to the south of column 3. This sum should be zero as the first element  board[1,3] will always visible. However, the elements board[2,3], board[3,3], board[4,3] should not be greater than the first element.  Therefore if no elements are greater than the first, then no other skyscraper is visible besides the first.
constraint 0 == sum([board[i,3] > board[1,3] | i in 2..N]);
% facing south, there should be 2 visible skyscrapers from the north to the south of column 4
constraint 1 == sum([board[i,4] > board[1,4] | i in 2..N]);
% facing north, there should be 3 visible skyscrapers from the south to the north of column 3
% constraint 2 == sum([board[i,3] > board[4,3] | i in N-1..1]);
% facing east, there should be 1 visible skyscraper from the west to east of row 3
constraint 0 == sum([board[3,i] > board[3,1] | i in 2..N]);
% facing west, there should be 2 visible skyscrapers from the east to west of row 2
% constraint 1 == sum([board[2,i] > board[2,4] | i in N-1..1]);

Running the model gives me the following 2D array:

| 1, 2, 4, 3 |
| 2, 1, 3, 4 |
| 4, 3, 2, 1 |
| 3, 4, 1, 2 |

The constraints that aren't commented out are satisfied just right as seen in the array given. However, when I try to find the iterate the row/column from the end (left side for rows, bottom end for columns) to the start, it gives me this: 

Compiling skyscrapers.mzn
WARNING: model inconsistency detected
in binary '=' operator expression
Running skyscrapers.mzn
=====UNSATISFIABLE=====
Finished in 130msec

I tried using the following:

constraint 2 == sum([board[i,3] > board[4,3] | i in {3,2,1}]);

This works. Why doesn't the other method work? Does minizinc now allow to generate numbers from X -> Y where Y < X

Last edited by Kasutiryo at 13:36 Nov 08, 2019.