Constraint Programming: Modeling and Solving Problems with MiniZinc

Author

Your Name

Published

February 5, 2025

Introduction

This document summarizes a lecture on constraint programming, emphasizing the modeling of problems through variables, domains, and constraints. The lecture introduces MiniZinc, a declarative modeling language, and showcases its application via several examples, including the N-Queens problem, crypto-arithmetic puzzles, Latin squares, magic squares, Sudoku, and the Schur number problem. The primary objective is to demonstrate effective declarative problem modeling, harnessing the capabilities of constraint solvers without needing to develop explicit algorithms. This approach contrasts with traditional imperative programming, where the focus is on specifying the step-by-step execution of a solution. Instead, constraint programming allows us to define the problem’s properties and let the solver find a solution that satisfies all the given constraints.

Variables: Represent the unknown quantities in the problem.
Domains: Define the set of possible values that each variable can take.
Constraints: Specify the relationships between variables that must be satisfied for a solution to be valid.

The modeling process in constraint programming typically involves:

Identifying the variables relevant to the problem and defining their respective domains.
Formulating constraints that accurately capture the problem’s requirements and limitations.
Optionally, defining search heuristics to guide the solver towards a solution more efficiently.

The lecture also highlights the importance of choosing appropriate data structures and constraints for efficient modeling and solving.

Fundamentals of Constraint Programming

Constraint programming is a declarative programming paradigm where relationships between variables are expressed as constraints. Unlike imperative programming, which focuses on specifying a sequence of steps to be executed, constraint programming centers on describing the properties of the problem. A constraint solver then finds a solution that satisfies all the defined constraints. This approach allows for a more abstract and problem-oriented way of thinking about computation.

Key Concepts

Variables: These represent the unknown quantities or decision points in the problem. Each variable is a placeholder for a value that the solver needs to determine.
Domains: The domain of a variable defines the set of possible values that the variable can take. This set can be finite or infinite, depending on the problem.
Constraints: Constraints specify the relationships between variables that must hold true for a solution to be valid. These relationships can be logical, arithmetic, or symbolic.

Modeling Process

The process of modeling a problem using constraint programming typically involves the following steps:

Identifying Variables and Domains: The first step is to identify the variables that represent the unknowns in the problem and to define the set of possible values (the domain) for each variable.
Formulating Constraints: Next, the relationships between the variables are expressed as constraints. These constraints capture the problem’s requirements and limitations.
(Optional) Defining Search Heuristics: In some cases, the solver may need guidance to find a solution efficiently. Search heuristics can be defined to guide the solver in exploring the search space.

Declarative vs. Imperative: Constraint programming is declarative, focusing on describing the problem, while imperative programming focuses on describing how to solve the problem.
Solution Finding: In constraint programming, the solver is responsible for finding a solution that satisfies the constraints. In imperative programming, the programmer must explicitly define the steps to find a solution.

This declarative approach allows for more flexibility and can lead to more concise and understandable models, especially for complex problems.

MiniZinc: A Declarative Modeling Language

MiniZinc is a high-level, declarative modeling language designed for expressing constraint satisfaction and optimization problems. It provides a user-friendly syntax that allows modelers to describe problems in a natural and intuitive manner, abstracting away the complexities of the underlying solving process. This abstraction enables users to focus on the problem’s logic rather than the specific algorithms required to solve it. MiniZinc models are then translated into a low-level format that can be processed by various constraint solvers.

Basic Structure of a MiniZinc Model

A typical MiniZinc model consists of several key components, each serving a specific purpose:

Parameters: These are constants that define the specific instance of the problem being modeled. Parameters are typically used to specify the size of the problem, the values of known quantities, or other fixed data. They are declared using the ‘int’, ‘float’, or ‘string’ keywords, and can be assigned values directly or read from an external data file.
Variables: These are the decision variables that represent the unknowns in the problem. Each variable is associated with a domain, which specifies the set of possible values that the variable can take. Variables are declared using the ‘var’ keyword, followed by the domain specification.
Constraints: These are the relationships between variables that must hold true for a solution to be valid. Constraints are expressed using logical and arithmetic operators, as well as built-in predicates and functions. They define the problem’s rules and limitations.
Solve Item: This specifies the objective of the model. It indicates whether the goal is to find any solution that satisfies all the constraints (‘solve satisfy’), or to find a solution that optimizes a specific objective function (‘solve minimize’ or ‘solve maximize’).
Output: This defines how the solution should be displayed. It specifies the format in which the values of the variables should be presented. The ‘output’ section uses string formatting and list comprehensions to generate readable output.

Declarative Nature: MiniZinc allows users to describe the problem without specifying how to solve it.
High-Level Abstraction: It hides the low-level details of the solving process, allowing users to focus on the problem’s logic.
Multiple Solver Support: MiniZinc models can be solved by various constraint solvers, providing flexibility and choice.
Readability: The syntax is designed to be clear and easy to understand, making models easier to develop and maintain.

By using these components, modelers can create concise and expressive models that can be solved efficiently by constraint solvers. The separation of modeling and solving allows for greater flexibility and adaptability when tackling complex problems.

Example: N-Queens Problem

The N-Queens problem is a classic puzzle that involves placing N chess queens on an N×N chessboard in such a way that no two queens threaten each other. A queen can attack any other piece in the same row, column, or diagonal. This problem is often used to illustrate the power of constraint programming.

Modeling

To model the N-Queens problem, we define the following:

Variables: We use an array ‘Q’ of size N, where ‘Q[i]’ represents the row position of the queen in the i-th column. This means that each column has exactly one queen.
Domains: Each variable ‘Q[i]’ has a domain of 1, 2, ..., N, representing the possible rows where a queen can be placed in the i-th column.
Constraints:
1. No two queens in the same row: This constraint ensures that no two queens are placed in the same row. It is expressed as ‘Q[i] != Q[j]’ for all pairs of columns ‘i’ and ‘j’ where ‘i != j’.
2. No two queens on the same diagonal: This constraint ensures that no two queens are placed on the same diagonal. It is expressed as ‘abs(Q[i] - Q[j]) != abs(i - j)’ for all pairs of columns ‘i’ and ‘j’ where ‘i != j’. The absolute difference in row positions must not equal the absolute difference in column positions.

MiniZinc Code (Basic)

The basic MiniZinc code for the N-Queens problem is as follows:

int: n = 4; % Size of the chessboard
array[1..n] of var 1..n: Q; % Queen positions

constraint
  forall(i, j in 1..n where i < j)(
    Q[i] != Q[j] /\ % Different rows
    abs(Q[i] - Q[j]) != j - i % Different diagonals
  );

solve satisfy;

output [
  if fix(Q[j]) == i then "Q" else "." endif ++
  if j == n then "\n" else "" endif
  | i, j in 1..n
];

This code defines the size of the chessboard (‘n’), the array of variables ‘Q’, and the constraints. The ‘output’ section formats the solution for display.

Enhanced MiniZinc Code with Global Constraints

The performance of the N-Queens problem can be significantly improved by using global constraints, specifically the ‘alldifferent’ constraint. The enhanced MiniZinc code is as follows:

include "globals.mzn";

int: n = 20;
array[1..n] of var 1..n: Q;

constraint
  alldifferent(Q) /\
  alldifferent([Q[i] + i | i in 1..n]) /\
  alldifferent([Q[i] - i | i in 1..n]);

solve satisfy;

This code uses the ‘alldifferent’ constraint to ensure that all the queens are in different rows, and that no two queens are on the same diagonal.

‘alldifferent(Q)’: Ensures that all queens are in different rows.
‘alldifferent([Q[i] + i | i in 1..n])’: Ensures that no two queens are on the same diagonal (top-left to bottom-right).
‘alldifferent([Q[i] - i | i in 1..n])’: Ensures that no two queens are on the same diagonal (top-right to bottom-left).

Notes

Performance Improvement: Using ‘alldifferent’ significantly improves performance compared to the basic code because it allows the constraint solver to perform more efficient constraint propagation.
Global Constraints: The ‘globals.mzn’ library provides global constraints like ‘alldifferent’, which are designed to handle common constraints more efficiently.
Absolute Value Removal: The original constraint ‘abs(Q[i] - Q[j]) != abs(i - j)’ is equivalent to ‘Q[i] + i != Q[j] + j’ and ‘Q[i] - i != Q[j] - j’. By removing the absolute value, we replace a non-deterministic choice (due to the two cases of the absolute value) with a deterministic conjunction, potentially simplifying the constraint propagation process. This is because the solver no longer needs to consider the two cases of the absolute value separately.

A solution to the 4-Queens problem.

The figure 1 illustrates a possible solution for the 4-Queens problem.

Example: Crypto-Arithmetic Puzzle (SEND + MORE = MONEY)

Crypto-arithmetic puzzles, also known as alphametics, are mathematical puzzles where letters represent digits, and the goal is to find a mapping of letters to digits such that a given arithmetic equation holds true. The classic example is SEND + MORE = MONEY, where each letter must be assigned a unique digit from 0 to 9.

Modeling

To model the SEND + MORE = MONEY puzzle, we define the following:

Variables: We introduce variables for each letter in the puzzle: S, E, N, D, M, O, R, and Y. Each variable represents a digit.
Domains: Each variable has a domain of 0 to 9, except for S and M, which must be greater than 0 because they are the leading digits of the numbers.
Constraints:
1. Unique Digits: All letters must represent different digits. This is expressed using the ‘alldifferent’ constraint: ‘alldifferent([S, E, N, D, M, O, R, Y])’.
2. Arithmetic Equation: The equation SEND + MORE = MONEY must hold true. This is expressed as: \[\begin{aligned} 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E = 10000*M + 1000*O + 100*N + 10*E + Y \end{aligned}\]

MiniZinc Code

The basic MiniZinc code for the SEND + MORE = MONEY puzzle is as follows:

include "globals.mzn";

var 0..9: S; var 0..9: E; var 0..9: N; var 0..9: D;
var 0..9: M; var 0..9: O; var 0..9: R; var 0..9: Y;

constraint S > 0;
constraint M > 0;
constraint
  1000*S + 100*E + 10*N + D +
  1000*M + 100*O + 10*R + E
  == 10000*M + 1000*O + 100*N + 10*E + Y;
constraint alldifferent([S, E, N, D, M, O, R, Y]);

solve satisfy;

output ["\(S)\(E)\(N)\(D) + \(M)\(O)\(R)\(E) = \(M)\(O)\(N)\(E)\(Y)\n"];

This code defines the variables, their domains, and the constraints. The ‘output’ section formats the solution for display.

Enhanced MiniZinc Code with Array

The MiniZinc code can be enhanced by using an array to represent the variables, which makes the code more concise and easier to manage. The enhanced code is as follows:

include "globals.mzn";

array[1..8] of var 0..9: FD;
enum letters = {S, E, N, D, M, O, R, Y};
array[letters] of var 0..9: letter = [FD[i] | i in 1..8];

constraint letter[S] > 0;
constraint letter[M] > 0;
constraint
  1000*letter[S] + 100*letter[E] + 10*letter[N] + letter[D] +
  1000*letter[M] + 100*letter[O] + 10*letter[R] + letter[E]
  == 10000*letter[M] + 1000*letter[O] + 100*letter[N] + 10*letter[E] + letter[Y];
constraint alldifferent(FD);

solve satisfy;

In this enhanced code:

An array ‘FD’ of size 8 is used to hold the variables.
An ‘enum’ type ‘letters’ is defined to represent the letters.
An array ‘letter’ is created, indexed by the ‘letters’ enum, to access the variables using their corresponding letters.
The constraints are expressed using the ‘letter’ array, making the code more readable and maintainable.

Conciseness: Arrays reduce code verbosity, making it easier to read and understand.
Maintainability: Changes to the set of variables are easier to manage when using arrays.
Flexibility: Arrays can be easily extended or modified to accommodate different problem instances.

The use of arrays and enums provides a more structured and scalable approach to modeling crypto-arithmetic puzzles.

Example: Latin Square

A Latin square is a square grid of size N×N, filled with N different symbols, such that each symbol appears exactly once in each row and exactly once in each column. Latin squares are used in various applications, including experimental design and cryptography.

Modeling

To model a Latin square, we define the following:

Variables: We use an N×N matrix ‘X’, where ‘X[i, j]’ represents the symbol at row ‘i’ and column ‘j’.
Domains: Each variable ‘X[i, j]’ has a domain of 1, 2, ..., N, representing the N different symbols that can be placed in each cell.
Constraints:
1. Each row contains distinct symbols: This constraint ensures that each row contains all N symbols exactly once. It is expressed as ‘alldifferent([X[i, j] | j in 1..N])’ for each row ‘i’. This means that for each row ‘i’, the values ‘X[i, 1], X[i, 2], ..., X[i, N]’ must all be different.
2. Each column contains distinct symbols: This constraint ensures that each column contains all N symbols exactly once. It is expressed as ‘alldifferent([X[i, j] | i in 1..N])’ for each column ‘j’. This means that for each column ‘j’, the values ‘X[1, j], X[2, j], ..., X[N, j]’ must all be different.

MiniZinc Code

The MiniZinc code for the Latin square problem is as follows:

include "globals.mzn";

int: n = 4;
array[1..n, 1..n] of var 1..n: X;

constraint
  forall(i in 1..n)(
    alldifferent([X[i, j] | j in 1..n])
  )
  /\
  forall(j in 1..n)(
    alldifferent([X[i, j] | i in 1..n])
  );

solve satisfy;

This code defines the size of the Latin square (‘n’), the matrix of variables ‘X’, and the constraints. The ‘forall’ loops are used to apply the ‘alldifferent’ constraint to each row and each column.

Global Constraint: The ‘alldifferent’ constraint is crucial for ensuring that each row and column contains distinct symbols.
Concise Modeling: The use of list comprehensions within the ‘alldifferent’ constraint allows for a concise and readable model.
Generalization: The model can be easily generalized to different sizes of Latin squares by changing the value of ‘n’.

The ‘solve satisfy’ statement instructs the solver to find any solution that satisfies all the constraints. The output can be customized to display the Latin square in a readable format.

A solution to the 4x4 Latin Square problem.

The figure 2 shows one possible solution for a 4x4 Latin square.

Example: Magic Square

A magic square is an N×N table, where each cell contains a distinct integer from 1 to N², and the sum of the numbers in each row, each column, and both main diagonals is the same. This constant sum is known as the magic sum. Magic squares are a classic example of a constraint satisfaction problem.

Modeling

To model a magic square, we define the following:

Variables: We use an N×N matrix ‘X’, where ‘X[i, j]’ represents the number at row ‘i’ and column ‘j’.
Domains: Each variable ‘X[i, j]’ has a domain of 1, 2, ..., N², representing the distinct integers that can be placed in each cell.
Constraints:
1. All cells are different: This constraint ensures that all numbers from 1 to N² are used exactly once in the magic square. It is expressed as ‘alldifferent(X)’.
2. Each row sums to the magic sum S: This constraint ensures that the sum of the numbers in each row is equal to the magic sum ‘S’. It is expressed as ‘sum(j in 1..N)(X[i, j]) = S’ for each row ‘i’.
3. Each column sums to S: This constraint ensures that the sum of the numbers in each column is equal to the magic sum ‘S’. It is expressed as ‘sum(i in 1..N)(X[i, j]) = S’ for each column ‘j’.
4. Both diagonals sum to S: This constraint ensures that the sum of the numbers in both main diagonals is equal to the magic sum ‘S’. The main diagonal is expressed as ‘sum(i in 1..N)(X[i, i]) = S’, and the anti-diagonal is expressed as ‘sum(i in 1..N)(X[i, N - i + 1]) = S’.
Magic Sum: The magic sum ‘S’ can be precomputed using the formula ‘S = n * (n*n + 1) div 2’. This formula is derived from the sum of integers from 1 to N² and dividing by N.

MiniZinc Code

The MiniZinc code for the magic square problem is as follows:

include "globals.mzn";

int: n = 4;
array[1..n, 1..n] of var 1..n*n: X;
int: S = n * (n*n + 1) div 2; % Magic sum

constraint
  alldifferent(X)
  /\
  forall(i in 1..n)(
    sum(j in 1..n)(X[i, j]) = S
  )
  /\
  forall(j in 1..n)(
    sum(i in 1..n)(X[i, j]) = S
  )
  /\
  sum(i in 1..n)(X[i, i]) = S
  /\
  sum(i in 1..n)(X[i, n - i + 1]) = S;

solve satisfy;

This code defines the size of the magic square (‘n’), the matrix of variables ‘X’, the precomputed magic sum ‘S’, and the constraints. The ‘forall’ loops are used to apply the sum constraint to each row and each column.

Notes

Precomputing the Magic Sum: Precomputing the magic sum ‘S’ using the formula ‘S = n * (n*n + 1) div 2’ can significantly improve the solver’s performance. This is because it provides the solver with a concrete value for the sum, which can be used to prune the search space more effectively.
Handling the Case without Precomputed Magic Sum: When the magic sum is not precomputed, an additional variable ‘S’ can be introduced to represent the sum. The constraints are then modified to ensure that all rows, columns, and diagonals sum to this variable ‘S’. To aid the solver, bounds can be set for ‘S’. For example, ‘0 < S <= n*n*n’ provides a reasonable upper bound for the magic sum. The MiniZinc code for this case is as follows:
```
include "globals.mzn";

int: n = 4;
array[1..n, 1..n] of var 1..n*n: X;
var int: S; % Magic sum as a variable

constraint
  alldifferent(X)
  /\
  forall(i in 1..n)(
    sum(j in 1..n)(X[i, j]) = S
  )
  /\
  forall(j in 1..n)(
    sum(i in 1..n)(X[i, j]) = S
  )
  /\
  sum(i in 1..n)(X[i, i]) = S
  /\
  sum(i in 1..n)(X[i, n - i + 1]) = S;

constraint S > 0;
constraint S <= n*n*n;

solve satisfy;
```
In this version, ‘S’ is a variable, and we add constraints to define its bounds. This approach allows the solver to determine the magic sum as part of the solution process.

A solution to the 4x4 Magic Square problem.

The figure 3 shows one possible solution for a 4x4 magic square.

Example: Sudoku

Sudoku is a popular logic-based number placement puzzle. The objective is to fill a 9x9 grid with digits from 1 to 9, such that each column, each row, and each of the nine 3x3 subgrids contains all the digits from 1 to 9, without repetition. Sudoku puzzles are a common example of constraint satisfaction problems.

Modeling

To model a Sudoku puzzle, we define the following:

Variables: We use a 9x9 matrix ‘square’, where ‘square[i, j]’ represents the number in row ‘i’ and column ‘j’.
Domains: Each variable ‘square[i, j]’ has a domain of 1, 2, ..., 9, representing the possible digits that can be placed in each cell.
Constraints:
1. Each row contains distinct digits: This constraint ensures that each row contains all the digits from 1 to 9 without repetition. It is expressed as ‘alldifferent([square[i, j] | j in 1..9])’ for each row ‘i’.
2. Each column contains distinct digits: This constraint ensures that each column contains all the digits from 1 to 9 without repetition. It is expressed as ‘alldifferent([square[i, j] | i in 1..9])’ for each column ‘j’.
3. Each 3x3 subgrid contains distinct digits: This constraint ensures that each of the nine 3x3 subgrids contains all the digits from 1 to 9 without repetition. The subgrids are defined by their top-left corners, which are at positions (1,1), (1,4), (1,7), (4,1), (4,4), (4,7), (7,1), (7,4), and (7,7).
Input: The puzzle is represented by a partially filled 9x9 grid, where 0 indicates an empty cell. This input is used to set the initial values of the variables.

MiniZinc Code

The MiniZinc code for the Sudoku problem is as follows:

include "globals.mzn";

int: n = 9;
int: sqrt_n = 3;

array[1..n, 1..n] of var 1..n: square;

% Constraint: Each row contains distinct digits
constraint
  forall(i in 1..n)(
    alldifferent([square[i, j] | j in 1..n])
  );

% Constraint: Each column contains distinct digits
constraint
  forall(j in 1..n)(
    alldifferent([square[i, j] | i in 1..n])
  );

% Constraint: Each 3x3 subgrid contains distinct digits
constraint
  forall(r, c in 1..sqrt_n)(
    alldifferent([square[r*sqrt_n - i, c*sqrt_n - j] | i, j in 0..sqrt_n-1])
  );

% Input: Example Sudoku puzzle (replace with actual input)
array[1..n, 1..n] of int: input = [|
  0, 0, 0, 2,6, 0, 7, 0, 1,
  6, 8, 0, 0, 7, 0, 0, 9,0,
  1, 9, 0, 0, 0, 4, 5, 0, 0,
  8, 2, 0, 1, 0, 0, 0, 4, 0,
  0, 0, 4, 6, 0, 2, 9, 0, 0,
  0, 5, 0, 0, 0, 3, 0, 2, 8,
  0, 0, 9, 3, 0, 0, 0, 7, 4,
  0, 4, 0, 0, 5, 0, 0, 3, 6,
  7, 0, 3, 0, 1, 8, 0, 0, 0
|];

constraint
  forall(i, j in 1..n)(
    if input[i, j] != 0 then
      square[i, j] = input[i, j]
    else
      true
    endif
  );

solve satisfy;

This code defines the size of the Sudoku grid (‘n’), the matrix of variables ‘square’, and the constraints. The ‘forall’ loops are used to apply the ‘alldifferent’ constraint to each row, column, and 3x3 subgrid. The input Sudoku puzzle is provided as a 2D array, and the corresponding cells in the ‘square’ matrix are constrained to match the input values.

Notes

Subgrid Constraint: The subgrid constraint uses a nested ‘forall’ loop with indices ‘r’ and ‘c’ that iterate over the top-left corners of the 3x3 subgrids. The ‘alldifferent’ constraint is then applied to the cells within each subgrid, ensuring that they contain distinct digits.
Input Handling: The input Sudoku puzzle is provided as a 2D array named ‘input’. The ‘constraint’ section iterates through each cell of the input array, and if the cell contains a non-zero value, the corresponding cell in the ‘square’ matrix is constrained to have that value. This ensures that the initial values of the Sudoku puzzle are correctly set in the model.
Purpose of the Picture: The picture mentioned in the original notes aimed to visually illustrate the starting positions of the 3x3 subgrids within the 9x9 grid. The indices (1, 1), (1, 4), (1, 7), (4, 1), etc., represent the top-left corners of these subgrids. This is crucial for understanding how the subgrid constraint is applied.

A Sudoku puzzle with initial values.

The figure 4 shows a Sudoku puzzle with the initial values.

Example: Schur Number

The Schur number problem is a combinatorial problem that involves partitioning the integers from 1 to N into C bins, such that no bin contains two numbers (not necessarily distinct) whose sum is also in the same bin. This problem is related to the study of sum-free sets and has connections to Ramsey theory.

Modeling

To model the Schur number problem, we define the following:

Variables: We use an array ‘box’ of size N, where ‘box[i]’ represents the bin number assigned to the integer ‘i’.
Domains: Each variable ‘box[i]’ has a domain of 1, 2, ..., C, representing the C different bins into which the integers can be placed.
Constraints:
- Sum-free constraint: For any two integers ‘i’ and ‘j’ (where ‘i + j <= N’), if ‘box[i] == box[j]’, then ‘box[i + j] != box[i]’. This constraint ensures that if two numbers ‘i’ and ‘j’ are in the same bin, their sum ‘i + j’ cannot be in the same bin.

MiniZinc Code

The MiniZinc code for the Schur number problem is as follows:

int: n = 5; % Range of numbers (1 to n)
int: c = 2; % Number of bins

array[1..n] of var 1..c: box; % Bin assignment for each number

constraint
  forall(i in 1..n-1, j in 1..n-i)(
    if box[i] == box[j] then
      box[i + j] != box[i]
    else
      true
    endif
  );

% Symmetry breaking: Assign 1 to the first bin, 2 to the second bin
constraint box[1] == 1;
constraint box[2] == 2;

solve satisfy;

This code defines the range of numbers (‘n’), the number of bins (‘c’), the array of variables ‘box’, and the constraints. The ‘forall’ loop iterates through all pairs of integers ‘i’ and ‘j’ such that ‘i + j <= n’, and the conditional constraint ensures that the sum-free property is satisfied.

Notes

Symmetry Breaking: The code includes symmetry-breaking constraints to reduce the search space. The constraints ‘box[1] == 1’ and ‘box[2] == 2’ force the first two numbers to be in different bins, which is a valid symmetry breaking strategy.
Open Problem: The open problem related to Schur numbers is to determine the largest value of N for a given number of bins C such that a valid partitioning exists. This largest value is known as the Schur number S(C). For example:
- S(2) = 4: The largest N for which the integers from 1 to N can be partitioned into 2 bins is 4.
- S(3) = 13: The largest N for which the integers from 1 to N can be partitioned into 3 bins is 13.
- S(4) = 44: The largest N for which the integers from 1 to N can be partitioned into 4 bins is 44.
- S(5) = 160: The largest known N for which the integers from 1 to N can be partitioned into 5 bins is 160. However, it is unknown if a valid partitioning exists for N=161 or larger.
The determination of Schur numbers for C > 4 is an open problem in mathematics. The value of S(5) was determined using a combination of constraint programming and parallel computation. The problem becomes computationally challenging as the number of bins increases.

Combinatorial Problem: The Schur number problem is a fundamental problem in combinatorics, exploring the properties of partitions and sum-free sets.
Connections to Ramsey Theory: The problem has connections to Ramsey theory, which studies the emergence of order in large systems.
Computational Challenges: The problem is computationally challenging, requiring advanced techniques to find solutions for larger numbers of bins.

The Schur number problem serves as an excellent example of a combinatorial problem that can be modeled and solved using constraint programming, while also highlighting the challenges and open questions in the field.

Conclusion

This lecture has provided a comprehensive introduction to constraint programming and its practical application using the MiniZinc modeling language. We have explored a variety of examples, including the N-Queens problem, crypto-arithmetic puzzles (such as SEND + MORE = MONEY), Latin squares, magic squares, Sudoku, and the Schur number problem. These examples have demonstrated how to effectively model problems using variables, domains, and constraints, and how to leverage the powerful features of MiniZinc, such as global constraints and search heuristics.

Key takeaways from this lecture include:

Declarative Approach: Constraint programming offers a declarative approach to problem-solving, allowing us to focus on describing what the problem is, rather than how to solve it. This contrasts with imperative programming, where the focus is on specifying the steps to find a solution.
MiniZinc as a Modeling Tool: MiniZinc is a powerful and versatile tool for modeling and solving constraint satisfaction and optimization problems. Its high-level syntax and support for various solvers make it an excellent choice for both beginners and experienced users.
Importance of Modeling Choices: Choosing appropriate data structures and constraints is crucial for efficient modeling. The way a problem is modeled can significantly impact the performance of the solver.
Global Constraints: Global constraints, such as ‘alldifferent’, can significantly improve performance by enabling more efficient constraint propagation. These constraints capture common patterns and allow solvers to reason about them more effectively.
Search Heuristics: Search heuristics can be customized to guide the solver towards a solution, but built-in heuristics are often effective. Understanding how these heuristics work can help in fine-tuning the solving process.
Symmetry Breaking: Symmetry breaking constraints can help reduce the search space by eliminating redundant solutions. Identifying and applying appropriate symmetry breaking techniques can lead to significant performance improvements.

Follow-up Questions/Topics for Next Lecture:

Optimization Problems: How to model optimization problems in MiniZinc, using ‘solve minimize’ and ‘solve maximize’ to find optimal solutions, rather than just satisfying solutions.
Search Heuristics in Detail: A deeper dive into search heuristics and their impact on performance, including how to choose and implement effective heuristics for different types of problems.
Advanced Symmetry Breaking: More advanced techniques for symmetry breaking, including how to identify and exploit symmetries in complex problems.
Exploring Global Constraints: Further exploration of other global constraints and their applications, including how to use them effectively in different modeling scenarios.
Limitations of Constraint Programming: A discussion of the limitations of constraint programming and when other techniques, such as integer programming or local search, might be more suitable.
Solver Selection: How to choose between different solvers (e.g., Chuffed, Gecode, OR-Tools) based on the problem characteristics and performance requirements.

By understanding the concepts presented in this lecture and by practicing with different problems, students can gain proficiency in constraint programming and apply it to solve a wide range of real-world problems. The ability to model problems declaratively and leverage the power of constraint solvers is a valuable skill in many areas of computer science and operations research.

This lecture has laid the foundation for further exploration of constraint programming techniques and their applications. The follow-up topics will delve deeper into the more advanced aspects of modeling and solving constraint problems.

--- title: "Constraint Programming: Modeling and Solving Problems with MiniZinc" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This document summarizes a lecture on constraint programming, emphasizing the modeling of problems through variables, domains, and constraints. The lecture introduces MiniZinc, a declarative modeling language, and showcases its application via several examples, including the N-Queens problem, crypto-arithmetic puzzles, Latin squares, magic squares, Sudoku, and the Schur number problem. The primary objective is to demonstrate effective declarative problem modeling, harnessing the capabilities of constraint solvers without needing to develop explicit algorithms. This approach contrasts with traditional imperative programming, where the focus is on specifying the step-by-step execution of a solution. Instead, constraint programming allows us to define the problem's properties and let the solver find a solution that satisfies all the given constraints. ::: tcolorbox - **Variables**: Represent the unknown quantities in the problem. - **Domains**: Define the set of possible values that each variable can take. - **Constraints**: Specify the relationships between variables that must be satisfied for a solution to be valid. ::: The modeling process in constraint programming typically involves: 1. Identifying the variables relevant to the problem and defining their respective domains. 2. Formulating constraints that accurately capture the problem's requirements and limitations. 3. Optionally, defining search heuristics to guide the solver towards a solution more efficiently. The lecture also highlights the importance of choosing appropriate data structures and constraints for efficient modeling and solving. # Fundamentals of Constraint Programming Constraint programming is a declarative programming paradigm where relationships between variables are expressed as constraints. Unlike imperative programming, which focuses on specifying a sequence of steps to be executed, constraint programming centers on describing the properties of the problem. A constraint solver then finds a solution that satisfies all the defined constraints. This approach allows for a more abstract and problem-oriented way of thinking about computation. ## Key Concepts - **Variables**: These represent the unknown quantities or decision points in the problem. Each variable is a placeholder for a value that the solver needs to determine. - **Domains**: The domain of a variable defines the set of possible values that the variable can take. This set can be finite or infinite, depending on the problem. - **Constraints**: Constraints specify the relationships between variables that must hold true for a solution to be valid. These relationships can be logical, arithmetic, or symbolic. ## Modeling Process The process of modeling a problem using constraint programming typically involves the following steps: 1. **Identifying Variables and Domains**: The first step is to identify the variables that represent the unknowns in the problem and to define the set of possible values (the domain) for each variable. 2. **Formulating Constraints**: Next, the relationships between the variables are expressed as constraints. These constraints capture the problem's requirements and limitations. 3. **(Optional) Defining Search Heuristics**: In some cases, the solver may need guidance to find a solution efficiently. Search heuristics can be defined to guide the solver in exploring the search space. ::: tcolorbox - **Declarative vs. Imperative**: Constraint programming is declarative, focusing on describing the problem, while imperative programming focuses on describing how to solve the problem. - **Solution Finding**: In constraint programming, the solver is responsible for finding a solution that satisfies the constraints. In imperative programming, the programmer must explicitly define the steps to find a solution. ::: This declarative approach allows for more flexibility and can lead to more concise and understandable models, especially for complex problems. # MiniZinc: A Declarative Modeling Language MiniZinc is a high-level, declarative modeling language designed for expressing constraint satisfaction and optimization problems. It provides a user-friendly syntax that allows modelers to describe problems in a natural and intuitive manner, abstracting away the complexities of the underlying solving process. This abstraction enables users to focus on the problem's logic rather than the specific algorithms required to solve it. MiniZinc models are then translated into a low-level format that can be processed by various constraint solvers. ## Basic Structure of a MiniZinc Model A typical MiniZinc model consists of several key components, each serving a specific purpose: - **Parameters**: These are constants that define the specific instance of the problem being modeled. Parameters are typically used to specify the size of the problem, the values of known quantities, or other fixed data. They are declared using the 'int', 'float', or 'string' keywords, and can be assigned values directly or read from an external data file. - **Variables**: These are the decision variables that represent the unknowns in the problem. Each variable is associated with a domain, which specifies the set of possible values that the variable can take. Variables are declared using the 'var' keyword, followed by the domain specification. - **Constraints**: These are the relationships between variables that must hold true for a solution to be valid. Constraints are expressed using logical and arithmetic operators, as well as built-in predicates and functions. They define the problem's rules and limitations. - **Solve Item**: This specifies the objective of the model. It indicates whether the goal is to find any solution that satisfies all the constraints ('solve satisfy'), or to find a solution that optimizes a specific objective function ('solve minimize' or 'solve maximize'). - **Output**: This defines how the solution should be displayed. It specifies the format in which the values of the variables should be presented. The 'output' section uses string formatting and list comprehensions to generate readable output. ::: tcolorbox - **Declarative Nature**: MiniZinc allows users to describe the problem without specifying how to solve it. - **High-Level Abstraction**: It hides the low-level details of the solving process, allowing users to focus on the problem's logic. - **Multiple Solver Support**: MiniZinc models can be solved by various constraint solvers, providing flexibility and choice. - **Readability**: The syntax is designed to be clear and easy to understand, making models easier to develop and maintain. ::: By using these components, modelers can create concise and expressive models that can be solved efficiently by constraint solvers. The separation of modeling and solving allows for greater flexibility and adaptability when tackling complex problems. # Example: N-Queens Problem The N-Queens problem is a classic puzzle that involves placing N chess queens on an N×N chessboard in such a way that no two queens threaten each other. A queen can attack any other piece in the same row, column, or diagonal. This problem is often used to illustrate the power of constraint programming. ## Modeling To model the N-Queens problem, we define the following: - **Variables**: We use an array 'Q' of size N, where 'Q\[i\]' represents the row position of the queen in the i-th column. This means that each column has exactly one queen. - **Domains**: Each variable 'Q\[i\]' has a domain of 1, 2, \..., N, representing the possible rows where a queen can be placed in the i-th column. - **Constraints**: 1. **No two queens in the same row**: This constraint ensures that no two queens are placed in the same row. It is expressed as 'Q\[i\] != Q\[j\]' for all pairs of columns 'i' and 'j' where 'i != j'. 2. **No two queens on the same diagonal**: This constraint ensures that no two queens are placed on the same diagonal. It is expressed as 'abs(Q\[i\] - Q\[j\]) != abs(i - j)' for all pairs of columns 'i' and 'j' where 'i != j'. The absolute difference in row positions must not equal the absolute difference in column positions. ## MiniZinc Code (Basic) The basic MiniZinc code for the N-Queens problem is as follows: int: n = 4; % Size of the chessboard array[1..n] of var 1..n: Q; % Queen positions constraint forall(i, j in 1..n where i < j)( Q[i] != Q[j] /\ % Different rows abs(Q[i] - Q[j]) != j - i % Different diagonals ); solve satisfy; output [ if fix(Q[j]) == i then "Q" else "." endif ++ if j == n then "\n" else "" endif | i, j in 1..n ]; This code defines the size of the chessboard ('n'), the array of variables 'Q', and the constraints. The 'output' section formats the solution for display. ## Enhanced MiniZinc Code with Global Constraints The performance of the N-Queens problem can be significantly improved by using global constraints, specifically the 'alldifferent' constraint. The enhanced MiniZinc code is as follows: include "globals.mzn"; int: n = 20; array[1..n] of var 1..n: Q; constraint alldifferent(Q) /\ alldifferent([Q[i] + i | i in 1..n]) /\ alldifferent([Q[i] - i | i in 1..n]); solve satisfy; This code uses the 'alldifferent' constraint to ensure that all the queens are in different rows, and that no two queens are on the same diagonal. - 'alldifferent(Q)': Ensures that all queens are in different rows. - 'alldifferent(\[Q\[i\] + i \| i in 1..n\])': Ensures that no two queens are on the same diagonal (top-left to bottom-right). - 'alldifferent(\[Q\[i\] - i \| i in 1..n\])': Ensures that no two queens are on the same diagonal (top-right to bottom-left). ## Notes - **Performance Improvement**: Using 'alldifferent' significantly improves performance compared to the basic code because it allows the constraint solver to perform more efficient constraint propagation. - **Global Constraints**: The 'globals.mzn' library provides global constraints like 'alldifferent', which are designed to handle common constraints more efficiently. - **Absolute Value Removal**: The original constraint 'abs(Q\[i\] - Q\[j\]) != abs(i - j)' is equivalent to 'Q\[i\] + i != Q\[j\] + j' and 'Q\[i\] - i != Q\[j\] - j'. By removing the absolute value, we replace a non-deterministic choice (due to the two cases of the absolute value) with a deterministic conjunction, potentially simplifying the constraint propagation process. This is because the solver no longer needs to consider the two cases of the absolute value separately. <figure id="fig:nqueens"> <figcaption>A solution to the 4-Queens problem.</figcaption> </figure> The figure [1](#fig:nqueens){reference-type="ref" reference="fig:nqueens"} illustrates a possible solution for the 4-Queens problem. # Example: Crypto-Arithmetic Puzzle (SEND + MORE = MONEY) Crypto-arithmetic puzzles, also known as alphametics, are mathematical puzzles where letters represent digits, and the goal is to find a mapping of letters to digits such that a given arithmetic equation holds true. The classic example is SEND + MORE = MONEY, where each letter must be assigned a unique digit from 0 to 9. ## Modeling To model the SEND + MORE = MONEY puzzle, we define the following: - **Variables**: We introduce variables for each letter in the puzzle: S, E, N, D, M, O, R, and Y. Each variable represents a digit. - **Domains**: Each variable has a domain of 0 to 9, except for S and M, which must be greater than 0 because they are the leading digits of the numbers. - **Constraints**: 1. **Unique Digits**: All letters must represent different digits. This is expressed using the 'alldifferent' constraint: 'alldifferent(\[S, E, N, D, M, O, R, Y\])'. 2. **Arithmetic Equation**: The equation SEND + MORE = MONEY must hold true. This is expressed as: $$\begin{aligned} 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E = 10000*M + 1000*O + 100*N + 10*E + Y \end{aligned}$$ ## MiniZinc Code The basic MiniZinc code for the SEND + MORE = MONEY puzzle is as follows: include "globals.mzn"; var 0..9: S; var 0..9: E; var 0..9: N; var 0..9: D; var 0..9: M; var 0..9: O; var 0..9: R; var 0..9: Y; constraint S > 0; constraint M > 0; constraint 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E == 10000*M + 1000*O + 100*N + 10*E + Y; constraint alldifferent([S, E, N, D, M, O, R, Y]); solve satisfy; output ["\(S)\(E)\(N)\(D) + \(M)\(O)\(R)\(E) = \(M)\(O)\(N)\(E)\(Y)\n"]; This code defines the variables, their domains, and the constraints. The 'output' section formats the solution for display. ## Enhanced MiniZinc Code with Array The MiniZinc code can be enhanced by using an array to represent the variables, which makes the code more concise and easier to manage. The enhanced code is as follows: include "globals.mzn"; array[1..8] of var 0..9: FD; enum letters = {S, E, N, D, M, O, R, Y}; array[letters] of var 0..9: letter = [FD[i] | i in 1..8]; constraint letter[S] > 0; constraint letter[M] > 0; constraint 1000*letter[S] + 100*letter[E] + 10*letter[N] + letter[D] + 1000*letter[M] + 100*letter[O] + 10*letter[R] + letter[E] == 10000*letter[M] + 1000*letter[O] + 100*letter[N] + 10*letter[E] + letter[Y]; constraint alldifferent(FD); solve satisfy; In this enhanced code: - An array 'FD' of size 8 is used to hold the variables. - An 'enum' type 'letters' is defined to represent the letters. - An array 'letter' is created, indexed by the 'letters' enum, to access the variables using their corresponding letters. - The constraints are expressed using the 'letter' array, making the code more readable and maintainable. ::: tcolorbox - **Conciseness**: Arrays reduce code verbosity, making it easier to read and understand. - **Maintainability**: Changes to the set of variables are easier to manage when using arrays. - **Flexibility**: Arrays can be easily extended or modified to accommodate different problem instances. ::: The use of arrays and enums provides a more structured and scalable approach to modeling crypto-arithmetic puzzles. # Example: Latin Square A Latin square is a square grid of size N×N, filled with N different symbols, such that each symbol appears exactly once in each row and exactly once in each column. Latin squares are used in various applications, including experimental design and cryptography. ## Modeling To model a Latin square, we define the following: - **Variables**: We use an N×N matrix 'X', where 'X\[i, j\]' represents the symbol at row 'i' and column 'j'. - **Domains**: Each variable 'X\[i, j\]' has a domain of 1, 2, \..., N, representing the N different symbols that can be placed in each cell. - **Constraints**: 1. **Each row contains distinct symbols**: This constraint ensures that each row contains all N symbols exactly once. It is expressed as 'alldifferent(\[X\[i, j\] \| j in 1..N\])' for each row 'i'. This means that for each row 'i', the values 'X\[i, 1\], X\[i, 2\], \..., X\[i, N\]' must all be different. 2. **Each column contains distinct symbols**: This constraint ensures that each column contains all N symbols exactly once. It is expressed as 'alldifferent(\[X\[i, j\] \| i in 1..N\])' for each column 'j'. This means that for each column 'j', the values 'X\[1, j\], X\[2, j\], \..., X\[N, j\]' must all be different. ## MiniZinc Code The MiniZinc code for the Latin square problem is as follows: include "globals.mzn"; int: n = 4; array[1..n, 1..n] of var 1..n: X; constraint forall(i in 1..n)( alldifferent([X[i, j] | j in 1..n]) ) /\ forall(j in 1..n)( alldifferent([X[i, j] | i in 1..n]) ); solve satisfy; This code defines the size of the Latin square ('n'), the matrix of variables 'X', and the constraints. The 'forall' loops are used to apply the 'alldifferent' constraint to each row and each column. ::: tcolorbox - **Global Constraint**: The 'alldifferent' constraint is crucial for ensuring that each row and column contains distinct symbols. - **Concise Modeling**: The use of list comprehensions within the 'alldifferent' constraint allows for a concise and readable model. - **Generalization**: The model can be easily generalized to different sizes of Latin squares by changing the value of 'n'. ::: The 'solve satisfy' statement instructs the solver to find any solution that satisfies all the constraints. The output can be customized to display the Latin square in a readable format. <figure id="fig:latinsquare"> <figcaption>A solution to the 4x4 Latin Square problem.</figcaption> </figure> The figure [2](#fig:latinsquare){reference-type="ref" reference="fig:latinsquare"} shows one possible solution for a 4x4 Latin square. # Example: Magic Square A magic square is an N×N table, where each cell contains a distinct integer from 1 to N², and the sum of the numbers in each row, each column, and both main diagonals is the same. This constant sum is known as the magic sum. Magic squares are a classic example of a constraint satisfaction problem. ## Modeling To model a magic square, we define the following: - **Variables**: We use an N×N matrix 'X', where 'X\[i, j\]' represents the number at row 'i' and column 'j'. - **Domains**: Each variable 'X\[i, j\]' has a domain of 1, 2, \..., N², representing the distinct integers that can be placed in each cell. - **Constraints**: 1. **All cells are different**: This constraint ensures that all numbers from 1 to N² are used exactly once in the magic square. It is expressed as 'alldifferent(X)'. 2. **Each row sums to the magic sum S**: This constraint ensures that the sum of the numbers in each row is equal to the magic sum 'S'. It is expressed as 'sum(j in 1..N)(X\[i, j\]) = S' for each row 'i'. 3. **Each column sums to S**: This constraint ensures that the sum of the numbers in each column is equal to the magic sum 'S'. It is expressed as 'sum(i in 1..N)(X\[i, j\]) = S' for each column 'j'. 4. **Both diagonals sum to S**: This constraint ensures that the sum of the numbers in both main diagonals is equal to the magic sum 'S'. The main diagonal is expressed as 'sum(i in 1..N)(X\[i, i\]) = S', and the anti-diagonal is expressed as 'sum(i in 1..N)(X\[i, N - i + 1\]) = S'. - **Magic Sum**: The magic sum 'S' can be precomputed using the formula 'S = n \* (n\*n + 1) div 2'. This formula is derived from the sum of integers from 1 to N² and dividing by N. ## MiniZinc Code The MiniZinc code for the magic square problem is as follows: include "globals.mzn"; int: n = 4; array[1..n, 1..n] of var 1..n*n: X; int: S = n * (n*n + 1) div 2; % Magic sum constraint alldifferent(X) /\ forall(i in 1..n)( sum(j in 1..n)(X[i, j]) = S ) /\ forall(j in 1..n)( sum(i in 1..n)(X[i, j]) = S ) /\ sum(i in 1..n)(X[i, i]) = S /\ sum(i in 1..n)(X[i, n - i + 1]) = S; solve satisfy; This code defines the size of the magic square ('n'), the matrix of variables 'X', the precomputed magic sum 'S', and the constraints. The 'forall' loops are used to apply the sum constraint to each row and each column. ## Notes - **Precomputing the Magic Sum**: Precomputing the magic sum 'S' using the formula 'S = n \* (n\*n + 1) div 2' can significantly improve the solver's performance. This is because it provides the solver with a concrete value for the sum, which can be used to prune the search space more effectively. - **Handling the Case without Precomputed Magic Sum**: When the magic sum is not precomputed, an additional variable 'S' can be introduced to represent the sum. The constraints are then modified to ensure that all rows, columns, and diagonals sum to this variable 'S'. To aid the solver, bounds can be set for 'S'. For example, '0 \< S \<= n\*n\*n' provides a reasonable upper bound for the magic sum. The MiniZinc code for this case is as follows: include "globals.mzn"; int: n = 4; array[1..n, 1..n] of var 1..n*n: X; var int: S; % Magic sum as a variable constraint alldifferent(X) /\ forall(i in 1..n)( sum(j in 1..n)(X[i, j]) = S ) /\ forall(j in 1..n)( sum(i in 1..n)(X[i, j]) = S ) /\ sum(i in 1..n)(X[i, i]) = S /\ sum(i in 1..n)(X[i, n - i + 1]) = S; constraint S > 0; constraint S <= n*n*n; solve satisfy; In this version, 'S' is a variable, and we add constraints to define its bounds. This approach allows the solver to determine the magic sum as part of the solution process. <figure id="fig:magicsquare"> <figcaption>A solution to the 4x4 Magic Square problem.</figcaption> </figure> The figure [3](#fig:magicsquare){reference-type="ref" reference="fig:magicsquare"} shows one possible solution for a 4x4 magic square. # Example: Sudoku Sudoku is a popular logic-based number placement puzzle. The objective is to fill a 9x9 grid with digits from 1 to 9, such that each column, each row, and each of the nine 3x3 subgrids contains all the digits from 1 to 9, without repetition. Sudoku puzzles are a common example of constraint satisfaction problems. ## Modeling To model a Sudoku puzzle, we define the following: - **Variables**: We use a 9x9 matrix 'square', where 'square\[i, j\]' represents the number in row 'i' and column 'j'. - **Domains**: Each variable 'square\[i, j\]' has a domain of 1, 2, \..., 9, representing the possible digits that can be placed in each cell. - **Constraints**: 1. **Each row contains distinct digits**: This constraint ensures that each row contains all the digits from 1 to 9 without repetition. It is expressed as 'alldifferent(\[square\[i, j\] \| j in 1..9\])' for each row 'i'. 2. **Each column contains distinct digits**: This constraint ensures that each column contains all the digits from 1 to 9 without repetition. It is expressed as 'alldifferent(\[square\[i, j\] \| i in 1..9\])' for each column 'j'. 3. **Each 3x3 subgrid contains distinct digits**: This constraint ensures that each of the nine 3x3 subgrids contains all the digits from 1 to 9 without repetition. The subgrids are defined by their top-left corners, which are at positions (1,1), (1,4), (1,7), (4,1), (4,4), (4,7), (7,1), (7,4), and (7,7). - **Input**: The puzzle is represented by a partially filled 9x9 grid, where 0 indicates an empty cell. This input is used to set the initial values of the variables. ## MiniZinc Code The MiniZinc code for the Sudoku problem is as follows: include "globals.mzn"; int: n = 9; int: sqrt_n = 3; array[1..n, 1..n] of var 1..n: square; % Constraint: Each row contains distinct digits constraint forall(i in 1..n)( alldifferent([square[i, j] | j in 1..n]) ); % Constraint: Each column contains distinct digits constraint forall(j in 1..n)( alldifferent([square[i, j] | i in 1..n]) ); % Constraint: Each 3x3 subgrid contains distinct digits constraint forall(r, c in 1..sqrt_n)( alldifferent([square[r*sqrt_n - i, c*sqrt_n - j] | i, j in 0..sqrt_n-1]) ); % Input: Example Sudoku puzzle (replace with actual input) array[1..n, 1..n] of int: input = [| 0, 0, 0, 2,6, 0, 7, 0, 1, 6, 8, 0, 0, 7, 0, 0, 9,0, 1, 9, 0, 0, 0, 4, 5, 0, 0, 8, 2, 0, 1, 0, 0, 0, 4, 0, 0, 0, 4, 6, 0, 2, 9, 0, 0, 0, 5, 0, 0, 0, 3, 0, 2, 8, 0, 0, 9, 3, 0, 0, 0, 7, 4, 0, 4, 0, 0, 5, 0, 0, 3, 6, 7, 0, 3, 0, 1, 8, 0, 0, 0 |]; constraint forall(i, j in 1..n)( if input[i, j] != 0 then square[i, j] = input[i, j] else true endif ); solve satisfy; This code defines the size of the Sudoku grid ('n'), the matrix of variables 'square', and the constraints. The 'forall' loops are used to apply the 'alldifferent' constraint to each row, column, and 3x3 subgrid. The input Sudoku puzzle is provided as a 2D array, and the corresponding cells in the 'square' matrix are constrained to match the input values. ## Notes - **Subgrid Constraint**: The subgrid constraint uses a nested 'forall' loop with indices 'r' and 'c' that iterate over the top-left corners of the 3x3 subgrids. The 'alldifferent' constraint is then applied to the cells within each subgrid, ensuring that they contain distinct digits. - **Input Handling**: The input Sudoku puzzle is provided as a 2D array named 'input'. The 'constraint' section iterates through each cell of the input array, and if the cell contains a non-zero value, the corresponding cell in the 'square' matrix is constrained to have that value. This ensures that the initial values of the Sudoku puzzle are correctly set in the model. - **Purpose of the Picture**: The picture mentioned in the original notes aimed to visually illustrate the starting positions of the 3x3 subgrids within the 9x9 grid. The indices (1, 1), (1, 4), (1, 7), (4, 1), etc., represent the top-left corners of these subgrids. This is crucial for understanding how the subgrid constraint is applied. <figure id="fig:sudoku"> <figcaption>A Sudoku puzzle with initial values.</figcaption> </figure> The figure [4](#fig:sudoku){reference-type="ref" reference="fig:sudoku"} shows a Sudoku puzzle with the initial values. # Example: Schur Number The Schur number problem is a combinatorial problem that involves partitioning the integers from 1 to N into C bins, such that no bin contains two numbers (not necessarily distinct) whose sum is also in the same bin. This problem is related to the study of sum-free sets and has connections to Ramsey theory. ## Modeling To model the Schur number problem, we define the following: - **Variables**: We use an array 'box' of size N, where 'box\[i\]' represents the bin number assigned to the integer 'i'. - **Domains**: Each variable 'box\[i\]' has a domain of 1, 2, \..., C, representing the C different bins into which the integers can be placed. - **Constraints**: - **Sum-free constraint**: For any two integers 'i' and 'j' (where 'i + j \<= N'), if 'box\[i\] == box\[j\]', then 'box\[i + j\] != box\[i\]'. This constraint ensures that if two numbers 'i' and 'j' are in the same bin, their sum 'i + j' cannot be in the same bin. ## MiniZinc Code The MiniZinc code for the Schur number problem is as follows: int: n = 5; % Range of numbers (1 to n) int: c = 2; % Number of bins array[1..n] of var 1..c: box; % Bin assignment for each number constraint forall(i in 1..n-1, j in 1..n-i)( if box[i] == box[j] then box[i + j] != box[i] else true endif ); % Symmetry breaking: Assign 1 to the first bin, 2 to the second bin constraint box[1] == 1; constraint box[2] == 2; solve satisfy; This code defines the range of numbers ('n'), the number of bins ('c'), the array of variables 'box', and the constraints. The 'forall' loop iterates through all pairs of integers 'i' and 'j' such that 'i + j \<= n', and the conditional constraint ensures that the sum-free property is satisfied. ## Notes - **Symmetry Breaking**: The code includes symmetry-breaking constraints to reduce the search space. The constraints 'box\[1\] == 1' and 'box\[2\] == 2' force the first two numbers to be in different bins, which is a valid symmetry breaking strategy. - **Open Problem**: The open problem related to Schur numbers is to determine the largest value of N for a given number of bins C such that a valid partitioning exists. This largest value is known as the Schur number S(C). For example: - S(2) = 4: The largest N for which the integers from 1 to N can be partitioned into 2 bins is 4. - S(3) = 13: The largest N for which the integers from 1 to N can be partitioned into 3 bins is 13. - S(4) = 44: The largest N for which the integers from 1 to N can be partitioned into 4 bins is 44. - S(5) = 160: The largest known N for which the integers from 1 to N can be partitioned into 5 bins is 160. However, it is unknown if a valid partitioning exists for N=161 or larger. - The determination of Schur numbers for C \> 4 is an open problem in mathematics. The value of S(5) was determined using a combination of constraint programming and parallel computation. The problem becomes computationally challenging as the number of bins increases. ::: tcolorbox - **Combinatorial Problem**: The Schur number problem is a fundamental problem in combinatorics, exploring the properties of partitions and sum-free sets. - **Connections to Ramsey Theory**: The problem has connections to Ramsey theory, which studies the emergence of order in large systems. - **Computational Challenges**: The problem is computationally challenging, requiring advanced techniques to find solutions for larger numbers of bins. ::: The Schur number problem serves as an excellent example of a combinatorial problem that can be modeled and solved using constraint programming, while also highlighting the challenges and open questions in the field. # Conclusion This lecture has provided a comprehensive introduction to constraint programming and its practical application using the MiniZinc modeling language. We have explored a variety of examples, including the N-Queens problem, crypto-arithmetic puzzles (such as SEND + MORE = MONEY), Latin squares, magic squares, Sudoku, and the Schur number problem. These examples have demonstrated how to effectively model problems using variables, domains, and constraints, and how to leverage the powerful features of MiniZinc, such as global constraints and search heuristics. Key takeaways from this lecture include: - **Declarative Approach**: Constraint programming offers a declarative approach to problem-solving, allowing us to focus on describing *what* the problem is, rather than *how* to solve it. This contrasts with imperative programming, where the focus is on specifying the steps to find a solution. - **MiniZinc as a Modeling Tool**: MiniZinc is a powerful and versatile tool for modeling and solving constraint satisfaction and optimization problems. Its high-level syntax and support for various solvers make it an excellent choice for both beginners and experienced users. - **Importance of Modeling Choices**: Choosing appropriate data structures and constraints is crucial for efficient modeling. The way a problem is modeled can significantly impact the performance of the solver. - **Global Constraints**: Global constraints, such as 'alldifferent', can significantly improve performance by enabling more efficient constraint propagation. These constraints capture common patterns and allow solvers to reason about them more effectively. - **Search Heuristics**: Search heuristics can be customized to guide the solver towards a solution, but built-in heuristics are often effective. Understanding how these heuristics work can help in fine-tuning the solving process. - **Symmetry Breaking**: Symmetry breaking constraints can help reduce the search space by eliminating redundant solutions. Identifying and applying appropriate symmetry breaking techniques can lead to significant performance improvements. **Follow-up Questions/Topics for Next Lecture:** 1. **Optimization Problems**: How to model optimization problems in MiniZinc, using 'solve minimize' and 'solve maximize' to find optimal solutions, rather than just satisfying solutions. 2. **Search Heuristics in Detail**: A deeper dive into search heuristics and their impact on performance, including how to choose and implement effective heuristics for different types of problems. 3. **Advanced Symmetry Breaking**: More advanced techniques for symmetry breaking, including how to identify and exploit symmetries in complex problems. 4. **Exploring Global Constraints**: Further exploration of other global constraints and their applications, including how to use them effectively in different modeling scenarios. 5. **Limitations of Constraint Programming**: A discussion of the limitations of constraint programming and when other techniques, such as integer programming or local search, might be more suitable. 6. **Solver Selection**: How to choose between different solvers (e.g., Chuffed, Gecode, OR-Tools) based on the problem characteristics and performance requirements. ::: tcolorbox By understanding the concepts presented in this lecture and by practicing with different problems, students can gain proficiency in constraint programming and apply it to solve a wide range of real-world problems. The ability to model problems declaratively and leverage the power of constraint solvers is a valuable skill in many areas of computer science and operations research. ::: This lecture has laid the foundation for further exploration of constraint programming techniques and their applications. The follow-up topics will delve deeper into the more advanced aspects of modeling and solving constraint problems.