Introduction

This document is a first introduction to Constraint Programming in Alice.

Constraint Progamming is a problem-solving technique for combinatorial problems that works by incorporating constraints into a programming environment (after [3] Principles of Constraint Programming. by Krysztof R. Apt).

Combinatorial problems question about properties (constraints) of a class of combinatorial structures which are characterized in terms of a finite set of variables and a finite value for each variable.

Finally, the constraint programming features of Alice that are build upon the Gecode [12] constraint library realize the requirements of Apt's definition.

First, this document covers combinatorial problems that can be stated with variables ranging over finite domains of integers. Later, those problems are expanded by allowing variables to range over finite sets of integers. Problems in this class range from puzzles to real world applications as diverse as scheduling, ware house allocation, configuration and placement.

The two basic techniques of constraint programming are constraint propagation and branching. Constraint propagation is an efficient inference mechanism obtained with concurrent propagators accumulating information in a constraint store. Branching splits a problem into complementary cases once constraint propagation cannot advance further, i.e. it reaches a fixpoint. By iterating propagation and branching, propagation will eventually determine the solutions of a problem.

Branching can easily lead to an exponential growth of the number of subproblems to be considered. Fortunately, this potential combinatorial explosion can often be contained by combining strong propagation mechanisms with problem specific heuristics for selecting branching steps.

The following puzzles give a first idea of the combinatorial problems that will be solved in this document:

• Money

  The Send More Money Problem consists in finding distinct digits for the letters D, E, M, N, O, R, S, Y such that S and M are different from zero (no leading zeros) and the equation SEND + MORE = MONEY is satisfied. The unique solution of the problem is 9567 + 1085 = 10652.

• Safe

  The code of Professor Smart's safe is a sequence of 9 distinct nonzero digits C₁,..., C₉ such that the following equations and inequations are satisfied:
  C₄ - C₆ = C₇
  C₁*C₂*C₃ = C₈ + C₉
  C₂ + C₃ + C₆ < C₈
  C₉ < C₈
  C₁ $\neq$ 1,..., C₉ $\neq$ 9

  Can you determine the code?

• Coloring

  Given a map showing the West European countries Netherlands, Belgium, France, Spain, Portugal, Germany, Luxemburg, Switzerland, Austria, and Italy, find a coloring such that neighboring countries have different color and a minimal number of colors is used.

• Grocery

  A kid goes into a grocery store and buys four items. The cashier charges $ 7.11, the kid pays and is about to leave when the cashier calls the kid back, and says

  `` Hold on, I multiplied the four items instead of adding them; I'll try again; Hah, with adding them the price still comes to $ 7.11 .''

  What were the prices of the four items?

• Queens

  Place 8 queens on a chess board such that no two queens attack each other.

The problems have in common that they can be stated with variables that are a priori constrained to finite sets of nonnegative integers. Consequently, the problems could be solved by simply checking all possible combinations of the values of the variables. This naive generate and test method is however infeasible for most realistic problems since there are just too many possible combinations.