### Constraint programming in ECLiPSe Constraint Programming System

This last few weeks I have programmed in ECLiPSe Constraint Logic Programming system more systematically than before. For example, many of my "learning models" has now been implemented in ECLiPSe. These and other ECLiPSe models is now collected at My ECLiPSe Page.

Arrays are very handy to use, especially in combinations with loops, see below for an example. Using loops and arrays means that I have been able to port my models quite easy, often directly from the MiniZinc and/or Comet models. This means that there are very few traditional Prolog recursive predicates in these models. Note that loops don't require arrays, they are as powerful with plain old lists, and ECLiPSe has of course also support for traditional Prolog logic programming.

As I understand it, SICStus Prolog will soon support logical loops (inspired by the ECLiPSe approach). That's great!

The model has two principal parts: *

Below is the code for solving the problem and filling out the squares, as well as keep the Latin square condition (for all rows and all columns there must be unique numbers):

Comment: This problem is really a subset of solving a Sudoku. The ECLiPSe distribution has an example for solving these problems: sudoku.ecl.txt.

Using "plain" lists and the syntactic sugar for multiplying two lists is is quite short:

As indicated above, most of these models use arrays and logical loops instead of the traditional Prolog recursion technique. I really like using these extensions since it is much easier to state the constraints, at least of me coming from MiniZinc, Comet and other non-logical programming.

#### ECLiPSe

ECLiPSe is very well documented system with a couple of online books for different aspects of the system. For more info see:- Documentation
- Examples
- The book
**Constraint Programming using ECLiPSe**by Krzysztof R. Apt and Mark Wallace, Cambridge University Press, 2006, ISBN: 9780521866286. - Mailing lists

#### My ECLiPSe page

There is now a My ECLiPSe Page with so far 46 ECLiPSe models (see below). Expect that this number will increase.#### Arrays and loops

In these models I have almost exclusively used the following two really great features of ECLiPSe, which are extensions to Prolog proper:- logical loops, e.g. for, foreach, fromto
- arrays with slices

Arrays are very handy to use, especially in combinations with loops, see below for an example. Using loops and arrays means that I have been able to port my models quite easy, often directly from the MiniZinc and/or Comet models. This means that there are very few traditional Prolog recursive predicates in these models. Note that loops don't require arrays, they are as powerful with plain old lists, and ECLiPSe has of course also support for traditional Prolog logic programming.

As I understand it, SICStus Prolog will soon support logical loops (inspired by the ECLiPSe approach). That's great!

#### Example: Diet problem

For a starter, let's implement a simple diet's problem, where we want to minimize the cost of different food given that the nutrition constraints is met. This problem is in diet.ecl and is shown below.:- lib(ic). :- lib(branch_and_bound). go :- % % fetch the data % data(Price, Limits, Calories, Chocolate, Sugar, Fat), % Xs is the decision variable containing the number % of nutrition to buy length(Calories, Len), % for setting the length of Xs length(Xs, Len), % set the same length for Xs Xs :: 0..10, % domains for Xs % convert Limits to LimitArray (so we can use LimitArray[i] below) length(Limits, LimitLength), dim(LimitArray, [LimitLength]), collection_to_list(LimitArray, Limits), % these constraints calculates: sum(Xs[i]*Y[i]) >= limit Xs * Calories #>= LimitArray[1], % 500, Xs * Chocolate #>= LimitArray[2], % 6, Xs * Sugar #>= LimitArray[3], % 10, Xs * Fat #>= LimitArray[4], % 8, % % search: minimize the sum of Xs * Price % XSum #= Xs * Price, minimize(search(Xs,0,first_fail,indomain,complete,[]),XSum), writeln([XSum, Xs]). % % data % data( [ 50, 20, 30, 80], % price in cents for each nutrition [500, 6, 10, 8], % limits, requirements for each nutrition % type % nutrition for each product [400, 200, 150, 500], % calories [3,2,0,0], % chocolate [2,2,4,4], % sugar [2,4,1,5] % fat ).Note especially the construct

`Total = List1 * List2`

which is a syntactical sugar for following (using MiniZinc/Comet syntax):
Total = sum(i from 1..n) (List1[i]*List2[i])

#### Using loops and arrays: Quasigroup completion

Quasigroup completion is a problem where starting from a not fully completed Latin square, and the object is to complete this square. quasigroup_completion.ecl is a model for this problem.The model has two principal parts: *

**stating the problem instances**, which I have done as a matrix using an array of arrays. The`[](....)`

is used for declaring arrays. Here is the first problem:
problem(1, []([](1, _, _, _, 4), [](_, 5, _, _, _), [](4, _, _, 2, _), [](_, 4, _, _, _), [](_, _, 5, _, 1))).*

**the model**Below is the code for solving the problem and filling out the squares, as well as keep the Latin square condition (for all rows and all columns there must be unique numbers):

solve(ProblemNum) :- problem(ProblemNum, Problem), dim(Problem, [N,N]), % get the size of the problem Problem[1..N,1..N] :: 1..N, (for(I, 1, N), param(Problem, N) do ic_global:alldifferent(Problem[I,1..N]), ic_global:alldifferent(Problem[1..N,I]) ), search(Problem,0,first_fail,indomain,complete,[backtrack(Backtracks)]), nl, pretty_print(Problem), writeln(backtracks:Backtracks).Here the loop (

`for(I,1,N)...`

) is used for looping through all the rows of the matrix. Note how easy it is to use "slices" of the matrix, e.g. `Problem[I,1..N]`

.
Comment: This problem is really a subset of solving a Sudoku. The ECLiPSe distribution has an example for solving these problems: sudoku.ecl.txt.

#### Another example: XKCD knapsack problem

The xkcd knapsack problem is implemented in xkcd.ecl. The models show some different approaches.Using "plain" lists and the syntactic sugar for multiplying two lists is is quite short:

go4 :- Prices = [215, 275, 335, 355, 420, 580], Total = 1505, length(Prices, Len), length(Xs, Len), Xs :: [0..10], Total #= Xs * Prices, labeling(Xs), writeln([Total, Xs]).The multiplication syntactic sugar don't work with arrays, but we can convert the array (a "collection") to a list with

`collection_to_list/2`

. This version also minimize the number of dishes:
go3 :- Prices = [](215, 275, 335, 355, 420, 580), % Prices for the dishes Total = 1505, % multiply 15.05 with 100 for integer usage dim(Prices, [Len]), % get length of Prices dim(Xs, [Len]), % same length of Xs Xs :: [0..10], % domain of Xs % get all solutions knapsack(Prices, Total, Xs), collection_to_list(Xs, XsList), sum(XsList, NumDishes), minimize(search(XsList,0,first_fail,indomain_max,complete,[]),NumDishes), writeln([Total, Xs, NumDishes]).Another approach when using arrays is to use for loops which is shown in the

`knapsack`

predicate below. Here `for(I,1,Len)`

is used for incrementing the index counter, and then `fromto`

does the actual summation. Note that `fromto`

is very versatile and can be used for other things. See the documentation for more info.
% % Sum the totals: Total = Prices * Xs % knapsack(Prices, Total, Xs) :- dim(Prices, [Len]), % get the length of the array ( for(I, 1, Len), fromto(0, S1, S2, Total), param(Prices, Xs) do S2 #= S1+Prices[I]*Xs[I] ), labeling(Xs). % % simple version: Total = 1505 % % This use the array representation % go :- Prices = [](215, 275, 335, 355, 420, 580), % Prices for the dishes Total = 1505, % multiply 15.05 with 100 for integer usage dim(Prices, [Len]), % get length of Prices dim(Xs, [Len]), % same length of Xs Xs :: [0..10], % domain of Xs findall(Xs, knapsack(Prices, Total, Xs), L), length(L, LLen), % length of solutions writeln([total:Total, num_solutions:LLen, solutions:L]).

#### Some more comments about ECLiPSe

Here are some more comments of ECLiPSe- ECLiPSe is based on Prolog, which is a programming language that has fascinated me for a long time.

`struct`

(records) is another great extension, but I have just used it for a map coloring example map.ecl. - There are not very many built in global constraints in ECLiPSe (compared to SICStus Prolog) which is a pity. I have plans to implement decompositions for some global constraints from Global Constraint Catalog.
- Almost all of the implemented model has used the
`ic`

library. I have yet to study (and use) the other libraries,`eplex`

,`suspend`

,`propia`

, and`repair`

which all seem very interesting. - there are many useful examples, almost all of them use loops and arrays. A wish: More examples of how to use the
`eplex`

library would be nice. - MiniZinc/FlatZinc: ECLiPSe has a great support for MiniZinc/FlatZinc, but unfortunately it - as of writing - don't support the recent version of MiniZinc (version 1.0).
- tkECLiPSe: This is a GUI in TclTk, but I have not used it much (I'm a Emacs guy). There are some visualizations libraries that should be tested more.
- ECLiPSe is a large system, see the Documentation for the full story.

#### My ECLiPSe models

I have implemented most of my "learning models" in ECLiPSe. Some are not yet done and will hopefully come later. Also, there are some older experiments in recreational mathematics. See My ECLiPSe Page.As indicated above, most of these models use arrays and logical loops instead of the traditional Prolog recursion technique. I really like using these extensions since it is much easier to state the constraints, at least of me coming from MiniZinc, Comet and other non-logical programming.

- abbots_puzzle.ecl: Abbot's puzzle
- alldifferent_except_0.ecl: Global constraint all different except 0 (decomposition)
- allpartitions.ecl: All partitions
- build_a_house.ecl: Build a house (scheduling)
- bus_schedule.ecl: Bus scheduling (Taha)
- calculs_d_enfer.ecl: Calculs d'enfer
- changes.ecl: Coin changes
- circling_squares.ecl: Circling squares
- coins_grid.ecl: Coins grid, CP version (Hubermann)
- coins_grid_eplex.ecl: Coins grid, MIP version (Huberman)
- contracting_costs.ecl: Contracting costs
- cur_num.ecl: Curious number
- debruijn.ecl: de Bruijn sequences (both "traditional" and "arbitrary"
- devils_word.ecl: Devil's word
- diet.ecl: Diet problem
- dinner.ecl: Dinner problem
- five_brigands.ecl: Five bridands problem
- furniture_moving.ecl: Furniture moving
- general_store.ecl: General store problem
- latin_squares.ecl: Latin squares
- least_diff2.ecl: Least diff problem
- mamas_age.ecl: Mama's age problem
- mankell.ecl: Generating all (mis) spelling of "Henrik Mankell" and "Kjellerstrand". Note: this is not really constraint programming, but it is a nice application of DCG's.
- map.ecl: Map coloring
- monks_and_doors.ecl: Monks and doors
- mortgage.ecl: Mortgage, experiments
- mr_smith.ecl: Mr Smith problem
- music_men.ecl: Music men problem
- pandigital_numbers.ecl: Pandigital numbers
- pythagoras.ecl: Pythagoras number
- quasigroup_completion.ecl: Quasigroup completion
- remainders.ecl: Remainders problem
- safe_cracking.ecl: Safe cracking problem
- schedule1.ecl: Simple sceduling problem
- schedule2.ecl: Simple sceduling problem
- send_more_money_any_base.ecl: SEND + MORE = MONEY (any base)
- send_most_money.ecl: SEND + MOST = MONEY, maximizes MONEY. All solutions.
- seseman.ecl: Seseman problem
- seven1.ecl: Seven eleven problem
- smuggler_knapsack.ecl: Smuggler's knapsack
- survo_puzzle.ecl: Survo puzzle
- timpkin.ecl: Mr Timpkin problem
- tonum.ecl: toNum, converts a number to array (and vice versa)
- torn_numbers.ecl: Torn numbers problem
- twin_letters.ecl: Twin letters problem
- xkcd.ecl: XKCD knapsack problem

## Comments

Nice page, and you have done a greater job, I'm wondering if you have make the model for the knight tour problem, because I'm trying to do this but without successful

Posted by: juan | August 18, 2009 02:00 AM

Hi Juan,

I have implemented three knight path models:

* MiniZinc: http://www.hakank.org/minizinc/knight_path.mzn

* Comet: http://www.hakank.org/comet/knights_path.co

* ECLiPSe: http://www.hakank.org/eclipse/knights_path.ecl

All are using the same principle of solving the problem.

Hope this helps.

Posted by: hakank | August 18, 2009 06:29 AM