9. CP

9.1. Theory

9.2. Project : Constraint Programming

In the 5th project, you will discover Constraint Programming by solving 3 exercises: the Magic Square, the Killer Sudoku and the Knight-Tour problems. Those problems are rather hard to solve, and you will use a Constraint Programming solver to tackle them. But first you have to complete certain methods to ensure that your solver is ready to be used.

9.2.1. Solver implementation

Here are the required steps to have your required constraints working:

  1. Implement the removeAbove and removeBelow methods from the Domain class. Those methods will remove all values within a domain that are greater / lower than a given threshold.

  2. Implement the propagator from the Sum constraint. This constraint is applied on an array of Variable \(x\) and on one expected sum, \(y\). It ensures that \(\sum x = y\). Your algorithm must be bound-consistent: you only need to update the maximum and minimum values of the variables present within the constraint.

  3. Implement the propagator from the LessOrEqual constraint. This constraint is applied on two Variable: \(x\) and \(y\), and ensures that \(x \leq y\). Your algorithm must be bound-consistent: you only need to update the maximum and minimum values of the variables present within the constraint.

For each of those steps, you will find corresponding unit tests to ensure that your solver is working as expected before moving on to the modeling.

9.2.2. Modeling the problems

There are two problems to model in this project:

  1. The Magic Square Problem. Given an square of \(n\times n\) cells, you need to find an assignment of values to each cell such that

  1. Every value appears once and only once;

  2. The sum of every row, column and of both diagonal within the square are the same.

  1. The Killer Sudoku Problem. In this variation of the Sudoku, the cells belong to a group. The sum of values within the cell belonging to a group must equal to a given input value. The whole set of constraints in this problem is thus

  1. Each row, column, and subsquare contains each number exactly once;

  2. The sum of all numbers in a group must match the expected sum of the group.

  1. The KnightTour Problem: A knight’s tour is a sequence of moves of a knight on a chessboard, such that

  1. The knight visits every square exactly once, and

  2. returns to the starting square.

The implementation needs to be done within the KnightTourSolver by completing the TODO’s. You’ll also need to implement the KnightMove constraint.

9.2.3. Gradescope

On Gradescope, find the written assignment for the project about constraint programming. You will first give some details about the modeling of a Magic Square Problem. Afterwards, you will examine how to derive additional solutions by examining the symmetries within the problem. Finally, a last step will ask you to run some experiments using your solver. You’ll also study an interesting alternative model for the KnightTour problem.