DM877 - Constraint Programming

Sheet 2

Task 1

Model and solve in MiniZinc the Magic Squares Problem. You can consult wikipedia to find out about magic squares. The problem consists in finding an $n \times n$ matrix such that:

every field is an integer between $1$ and $n^2$
fields are pairwise distinct
the sums of rows, columns, and the two main diagonals are equal It is a very hard problem for large $n$. Hence you can restrict yourself to consider the case for $n=3$. If you want to dig a bit more on this problem you can watch the related video in Numberphile.

Task 2

Model in CP and solve the Sudoku game. In specific, solve the following case:

$\begin{array}{||c|c|c||c|c|c||c|c|c||}\hline \hline & 4 & 3 & & 8 & & 2 & 5 & \\\hline 6 & & & & & & & & \\\hline & & & & & 1 & & 9 & 4 \\\hline \hline 9 & & & & & 4 & & 7 & \\\hline & & & 6 & & 8 & & & \\\hline & 1 & & 2 & & & & & 3 \\\hline \hline 8 & 2 & & 5 & & & & & \\\hline & & & & & & & & 5 \\\hline & 3 & 4 & & 9 & & 7 & 1 & \\\hline \hline \end{array}$

Task 3

Consider the following problem in Planning Wedding Seating:

There are 12 numbered seats in order around the table, 6 on each side. Males must sit in odd numbered seats, and females in even.
Ed cannot sit at the end of the table because of a phobia, and the bride and groom must sit next to each other.
The aim is to maximize the distance between known hatreds.
The distance between seats is the difference in seat number if on the same side, otherwise it’s the distance to the opposite seat + 1.

wedding

Consider another, frequent version of the seating problem:

Assign guests to tables while minimizing the unhappiness of all the guests. The unhappiness of guest is defined as their maximum unhappiness at being seated with each of the other guests at their table, i.e., it is a pairwise function. The unhappiness of a table is the maximum unhappiness of all the guests at the table. All guests must be seated and there is a limited number of seats at each table.

Model these problems in CP.

Task 4

Model and solve in CP the 8-Queens problem that asks to place 8 queens on a chess board such that the queens do not attack each other. Focus above all on the selection of variables.

Task 5

Model and solve in CP the bin packing problem: you are given a set of items each with a size and a set of bins each with a capacity that limits the total size of the items that can be placed in it. Your task is to place the items in the minimum number of bins such that the capacity constraint is not exceeded. Focus on modeling the problem with both arrays of variables and arrays of set variables. Calculate a lower and upper bound on the number of bins before starting the solution process.

Solve the two following two problems:

Small:

int: cap = 10;
int: n = 11;
array[1..n] int: size = [6, 6, 6, 5, 3, 3, 2, 2, 2, 2, 2];

Large:

int: cap = 100;
int: n = 50;
array[1..n] int: size = [
  99,98,95,95,95,94,94,91,88,87,86,85,76,74,73,71,68,60,55,54,51,
  45,42,40,39,39,36,34,33,32,32,31,31,30,29,26,26,23,21,21,21,19,
  18,18,16,15,5,5,4,1];

An optimal solution for the small instance:

packing