Constraint Programming Part I - Introduction

Constraint programming is programming for searching the solutions by specifying the constraints of a problem, and then generating the satisfied solutions. Constraint programming is unlike Brute-force search, which Brute-force generates all possible solutions and then tests all solutions for the answer. Constraint programming can reduce a huge time to search by discarding large set of unsatisfied solutions.

A solution is a combination set of finite domains. And a satisfied solution is the solution that satisfies all constraints. For instance, in Sudoku, a solution is a set of 1 to 9 with size of 9 rows and 9 columns. Satisfied solutions are values of all cells in each column, each row, and each 3 x 3 grid must be unique.

Constraint programming can solve solutions by "guess-and-check", this can be done by technics called backtracking and local consistency.

BackTracking is recursive algorithm to guess a value, and check if the value is satisfied the constraints. If the value is satisfied, it will recurse and guess a value for next item. The recursion will be done until solution is valid. If no solution is valid, it will rollback and guess next value, and continue searching for valid solutions again.

Local consistency is algorithm to cut off number of items in a domain. This will reduce time and space to search. Moreover, local consistency is also checker for satisfied solutions.

For instance, for 4-queens problem, you have to place 4 queens on 4 x 4 board, with the constraint that all 4 queens must not eat each other. In this problem, there are 4 variables, which are queens for row 1, 2, 3, 4. And there are 4 items in a finite domain, which are column A, B, C, D. And there are 2 constraints, all queens cannot be in the same column, and all queens cannot place diagonally to previous queens.

To start, constraint programming will pick value for the first queen, which is column A.

  A B C D
1 Q . . .
2 . . _ _
3 . _ . _
4 . _ _ .

With local consistency, it enforces that in second row, you cannot place queen on column A and B. In third row, you cannot place queen on column A and C, and for forth row, you cannot place queen on column A and D.

Next, constraint programming will pick value for the second queen, which is column C.

  A B C D
1 Q . . .
2 . . Q .
3 . . . .
4 . _ . .

You can see that, when we place second queen on column C, we cannot continue place queen on third row. Therefore, the solution is failed. Constraint programming will backtrack and try pick next value for the second queen, which is column D.

  A B C D
1 Q . . .
2 . . . Q
3 . _ . .
4 . . _ .

Next, for the third queen.

  A B C D
1 Q . . .
2 . . . Q
3 . Q . .
4 . . . .

Again, we cannot continue place queen for the forth row. Constraint programming will backtrack. The third row has only one option. Backtracking will perform again to the second row, unfortunately, second row used all available options. Then, we have to backtrack to the first row. Next value for the first row is column B.

  A B C D
1 . Q . .
2 . . . _
3 _ . _ .
4 _ . _ _

Next, for second row.

  A B C D
1 . Q . .
2 . . . Q
3 _ . . .
4 _ . _ .

Next, for third row.

  A B C D
1 . Q . .
2 . . . Q
3 Q . . .
4 . . _ .

Next, for the last row.

  A B C D
1 . Q . .
2 . . . Q
3 Q . . .
4 . . Q .

No conflict, solution is completed! Constraint programming can continue find whether there are any other solutions.

Next, we will start programming, and solve 8 queens problem.