version 4.1 was released yesterday (2009-12-11). Congratulations to the SICStus team! See here
for a summary of the news in this version.
For the past weeks I have tested the beta version of this release. In these tests I focused mainly on the following:
- the do-loops (for loops)
- support for MiniZinc version 1.0
- and somewhat SPIDER (the new IDE)
I did report some findings in the beta version, but most of the time I have been creating SICStus models and just learning the system, especially the
part. These models can be downloaded at My SICStus Prolog page
. See below for more about these models.
SICStus Prolog's support for do-loops
is based on Joachim Schimpf's paper Logical Loops
(link to CiteSeer). These constructs where first implemented in the ECLiPSe Constraint Programming System
(which I wrote about in Constraint programming in ECLiPSe Constraint Programming System
The following constructs are implemented in SICStus version 4.1:
An example: quasigroup_completion.pl
is a simple model that demonstrates the
loop, the constraints makes it a latin square given the hints in the Problem matrix:
domain(Vars, 1, N),
( foreach(Row, Problem)
( foreach(Column, ProblemTransposed)
problem(1, [[1, _, _, _, 4],
[_, 5, _, _, _],
[4, _, _, 2, _],
[_, 4, _, _, _],
[_, _, 5, _, 1]]).
Some other examples are from the Bin Loading model bin_packing.pl
. First is an example of a constraint that requires a (reversed) ordered array.
% load the bins in order:
% first bin must be loaded, and the list must be ordered
element(1, BinLoads, BinLoads1),
BinLoads1 #> 0,
This #>= Next
Next is how to sum occurrences of the loaded bins, using
to count the number
of loaded bins (
is a reified binary variable):
% calculate number of loaded bins
% (which we later will minimize)
Loaded in 0..1,
Load2 #> 0 #<=> Loaded #= 1,
Out #= In + Loaded
A slighly more general version of ordering an array is the predicate
( fromto(List, [This,Next | Rest], [Next|Rest],[_]),
where a comparison operator is used in the call, e.g.
to sort in reversed order.
Most of my models use these do loop constructs. As you can see of from the models I'm not a Prolog guy by profession, even though the language has fascinated me for a long time. SICStus' (and also ECLiPSe's) new approach of using for do-loops has made me appreciate Prolog in a new way. Very inspiring!
Two missing construct in SICStus (compared to the ECLiPSe implementation) are
for(...) * for(...)
. When writing the ECLiPSe models I used these two quite often, for example in the ECLiPSe model assignment.ecl
. Also, SICStus don't support the syntactic sugar of array/matrix access with
(note, this feature is not related to do-loops). When I first realized that they where missing in SICStus, I thought that it would be a hard job of converting my ECLiPSe models
to SICStus. Instead, these omissions was - to my surprise - quite a revelation.
My ECLiPSe models was mostly just a translation of the MiniZinc/Comet models I've written before, i.e. array/matrix based models where array access and loops such as
forall(i in 1..n) ()
is used all the time. Not surprising, my first SICStus models was then just a conversion of these array/matrix access to
constraints to simulate the ECLiPSe constructs. But it was not at all satisfactory; in fact, it was quite ugly sometimes, and also quite hard to understand. Instead I started to think about the problem again and found better ways of stating the problem, thus used much less of these constructs. Compare the above mentioned model with the SICStus version assignment.pl
which in my view is more elegant than my ECLiPSe version.
Here is a simple comparison of the assignment models mentioned above.
version (using -indices):
% exacly one assignment per row, all rows must be assigned
( for(I,1,Rows), param(X,Cols) do
sum(X[I,1..Cols]) #= 1
% zero or one assignments per column
( for(J,1,Cols), param(X,Rows) do
sum(X[1..Rows,J]) #=< 1
% calculate TotalCost
(for(I,1,Rows) * for(J,1,Cols),
Out #= In + X[I,J]*Cost[I,J]
As we see, this is heavily influenced by the MiniZinc/Comet way of coding.
Here is the corresponding code in SICStus
% exacly one assignment per row, all rows must be assigned
( foreach(Row, X) do
% zero or one assignments per column
( foreach(Column, Columns) do
% calculate TotalCost
(Almost the same code could be written in ECLiPSe as well; this is more about showing how my approach of coding has changed.)
However, I have not been able to completely free myself from the matrix approach; sometimes it was simply too hard, and sometimes I was just lazy.
A final note: The example directory of
now contains many examples of do-loops. Some of the older examples has also been rewritten using these constructs.
Support for MiniZinc/FlatZinc verion 1.0
One other quite large part of the testing was of the support of MiniZinc/FlatZinc
version 1.0 (the earlier SICStus version supported just version 0.9). The solver is often very fast, but I did not do any systematic comparison with other solvers using the beta version.
I am especially happy about that the FlatZinc solver now shows statistics, e.g.
% runtime: 80 ms
% solvetime: 10 ms
% solutions: 1
% constraints: 22
% backtracks: 1
% prunings: 64
This makes it easier to compare it to other solvers.
There are a number of ways of running a MiniZinc model or FlatZinc file (see the documentation
). Here is how I normally run the MiniZinc models from the command line (via my Perl wrapper program):
mzn2fzn -G sicstus minesweeper_3.mzn && sicstus --goal "use_module(library(zinc)), on_exception(E,zinc:fzn_run_file('minesweeper_3.fzn',[solutions(1),statistics(true),timeout(30000)]), write(user_error,E)), halt."
statistics(true): show the statistics
solutions(1): just show one solution. Use
solutions(all) for all solutions
timeout(30000): time out in milliseconds (here 30 seconds)
on_exception wrapper, so errors don't give the prompt. Note: There may be some strange results if the timeout from library(timeout) is used at the same time.
Note: "set vars" and "float vars" are not supported in this version.
I did just briefly tested SPIDER
, the Eclipse-based development environment for SICStus, and I honestly don't know how much I will use it instead of good old Emacs. However, where I a professional SICStus Prolog programmer, I would surely use it all the time since it has a lot of very good features especially crafted for SICStus.
One very useful feature is that it is quite good at detecting variables not properly declared in the do-loops (and singletons elsewhere); one has to use
for using a variable in inner loops. SPIDER is very good at detecting errors when such param values are missing (as well as other errors). For many models I have just started SPIDER to check if there where such bugs.
Another nice feature is the "balloon help", where the SICStus documentation is presented (click in the yellow area for more information).
My SICStus Prolog models
As always when starting learning a new constraint programming system, I started with my learning models
, this time mostly by translating the ECLiPSe models
. It first took quite a long time, since I missed some constructs I was used to in ECLiPSe (see above). But after a time it was rather easy to do it more like a SICStus approach, and now I really like writing in SICStus. Still, there are some models where this direct translations shows (and I'm not very proud of these models).
Also, I would like to thank Mats Carlsson and Magnus Ågren of the SICStus team for some great help with some of the first models.
So, I have now done almost all my ECLiPSe models in SICStus, except for those using floats or some where the SICStus' distributed examples are much better. SICStus don't support "set vars", so I used boolean lists instead, see for example steiner.pl
. Also, there are some 30-40 models not done in written ECLiPSe, and hopefully more is to come. All these models can be seen at My SICStus Prolog page
These models contains comments of the problem, e.g. references and also links to other of my models implementing the problem (in other constraint programming systems).
- 3_jugs.pl: 3 jugs problem (as a flow problem)
- a_round_of_golf.pl: A Round of Golf puzzle (Dell Logic Puzzles)
- abbots_puzzle.pl: Abbott's puzzle (Dudeney)
- added_corner.pl: Added corner puzzle
- alldifferent_except_0.pl: Decomposition of global constraint
- alldifferent_cst.pl: Decomposition of global constraint
- alldifferent_modulo.pl: Decomposition of global constraint
- all_differ_from_at_least_k_pos.pl: Decomposition of global constraint
- all_equal.pl: Decomposition of global constraint
- all_interval.pl: All interval problem (series), (CSPLib problem 7)
- all_min_dist.pl: Decomposition of global constraint
- allpartitions.pl: All partitions
- alpha.pl: Standard alphametic problem (a.k.a crypto)
- among.pl: Decomposition of global constraint
- among_seq.pl: Decomposition of global constraint
- arch_friends.pl: Arch friends (Dell Logic Puzzles)
- assignment.pl: Some assignment problems.
- averbach_1.2.pl: Example 1.2 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.4.pl: Example 1.4 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
- babysitting.pl: Babysitting puzzle (Dell Logic Problem)
- bin_packing.pl: Bin packing problems
- bin_packing2.pl: (Decomposition of the) global
constraint bin_packing (not exactly like the traditional bin packing))
- breaking_news.pl: Breaking news puzzle (Dell Logic Puzzles)
- build_a_house.pl: Build a house (simple scheduling)
- building_blocks.pl: Building blocks puzzle (for a more genral solution see labeled_dice.pl below)
- bus_schedule.pl: Simple bus scheduling (Taha)
- calculs_d_enfer.pl: Calculs d'enfer, an alphametic puzzle
- changes.pl: Coin changes
- circling_squares.pl: Circling squares (Dudeney)
- circuit.pl: Decomposition of global constraint
circuit (SICStus has a built in
- clique.pl: Decomposition of global constraint
- clock_triplet.pl: Clock triplet (Dean Clark, via Martin Gardner)
- coins3.pl: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro (ECLiPSe)
- coins_grid.pl: Coins grid problem (Tony Hurlimann)
- contracting_costs.pl: Contracting costs (Sam Loyd)
- covering_opl.pl: Set covering, selecting workers (from OPL example covering.mod)
- crew.pl: Crew Scheduling (via Gecode)
- crossword2.pl: Crossword solving (simple standard constraint programming example)
- crypta.pl: crypta, alphametic problem (standard Prolog/CLP benchmark)
- crypto.pl: crypto, alphametic problem (standard Prolog/CLP benchmark)
- cumulative_test.pl: Test of the built in
- curious_set_of_integers.pl: Curious set of integers (Gardner)
- cur_num.pl: Curious number (Dudeney)
- debruijn.pl: de Bruijn sequences
- devils_word.pl: Devil's word (sum of ASCII character of a word)
- diet1.pl: Simple diet optimization problem
- dinner.pl: Dinner problem
- discrete_tomography.pl: Discrete tomography
- distribute.pl: Decomposition of global constraint
- donald_gerald.pl: DONALD + GERALD = ROBERT (alphametic problem)
- einav_puzzle.pl: Solving the A programming puzzle from Einav
- eq10.pl: Eq 10, standard benchmark problem
- eq20.pl: Eq 20, standard benchmark problem
- exactly.pl: Decomposition of global constraint
- exodus.pl: Exodus puzzle (Dell Logic Puzzles)
- fancy.pl: Mr Greenguest puzzle (Fancy dress puzzle)
- fill_a_pix.pl: Fill-a-pix puzzle.
- five_brigands.pl: Five brigands problem (Dudeney)
- four_islands.pl: Four islands problem (Dell Logic Puzzles)
- fractions.pl: Fractions, alphametic problem (standard Prolog benchmark)
- furniture_moving.pl: Simple scheduling problem (using cumulative/2).
- futoshiki.pl: Futoshiki puzzle (yet another Japanese grid puzzle)
- general_store.pl: General store problem (Sam Loyd)
- global_contiguity.pl: Decomposition of global constraint
- hamming_distance.pl: Hamming distance
- heterosquare.pl: Heterosquare problem
- hidato.pl: Hidato puzzle
- huey_dewey_louie.pl: Huey, Dewey, Louie, logical problem from Marriott & Stuckey "Programming in Constraints"
- inverse.pl: Decomposition of global constraint
- isbn.pl: Some explorations in ISBN-13
- jobs_puzzle.pl: Jobs puzzle (a classic automated reasoning problem)
- just_forgotten.pl: Just forgotten puzzle (Enigma 1517)
- kakuro.pl: Kakuro grid puzzle
- K4P2GracefulGraph2.pl: K4P2 Graceful Graph
- kenken2.pl: Kenken grid puzzle
- killer_sudoku.pl: Killer Sudoku
- knapsack_investments.pl: Knapsack problem with investments (Lundgren, Rönnqvist, Värbrand: "Optimeringslära")
- knights_path.pl: Knights_path problem
- labeled_dice.pl: Labeled dice puzzle, more general approach (and contains the building_blocks.ecl as an instance). From Jim Orlin "Colored letters, labeled dice: a logic puzzle"
- langford.pl: Langford's number problem (CSP lib problem 24)
- latin_squares.pl: Latin squares
- least_diff.pl: Alphametic problem, smallest difference of two five digit numbers where are digits must be different.
- lecture_series.pl: Lecture seres (Dell Logic Puzzles)
- lectures.pl: Lectures, schedule problem from Biggs "Discrete Mathematics"
- lichtenstein_coloring.pl: Coloring problem: Lichtenstein's communes and exclaves
- magic_hexagon.pl: Magic hexagon (CSPLib, problem 23)
- magic_sequence.pl: Magic sequence (CSP lib problem)
- mamas_age.pl: Mama's age problem (Dudeney)
- mankell.pl: Generating all (mis) spelling of "Henrik Mankell" and "Kjellerstrand"
- map_coloring.pl: Simple map coloring example
- marathon2.pl: arathon Marathon puzzle (XPress example), CP model)
- minesweeper.pl: Minesweeper (with 14 problems, some from Gecode collections)
- miss_manners.pl: Miss Manners' seating problem (standard benchmark for rule engines). Includes problems of size 16, 64, and 128 guests.
- monks_and_doors.pl: Monks and doors
- mr_smith.pl: Mr Smith problem
- music_men.pl: Music men problem
- nadel.pl: B.A. Nadel's construction problem
- olympic.pl: Olympic puzzle (standard Prolog puzzle)
- pandigital_numbers.pl: Pandigital numbers
- pert.pl: Simple PERT problem (van Hentenryck)
- photo_problem.pl: Photo problem (Mozart/Oz)
- pigeon_hole.pl: Pigeon hole problem
- place_number_puzzle.pl: Place number puzzle
- post_office_problem2.pl: Post office problem (Winston)
- pythagoras.pl: Pythagoras number
- quasigroup_completion.pl: Quasigroup completion
- rabbits.pl: Rabbits problem (Van Hentenryck, OPL book)
- remainders.pl: Remainders problem (Kordemsky)
- remarkable_sequence.pl: Remarkable sequence (Coelho & Cotta "Prolog by Example" via Alma-0)
- safe_cracking.pl: Safe cracking (Mozart/Oz)
- send_more_money_any_base.pl: SEND+MORE=MONEY (in any base)
- scheduling_speakers.pl: Scheduling speakers (Rina Dechter)
- send_most_money.pl: Alphametic puzzle SEND + MOST = MONEY, where we maximize MONEY (and finds all solutions)
- sequence.pl: Decomposition of global constraint
- seseman.pl: Seseman convent puzzle
- set_covering.pl: Set covering (placing firestations, Winston)
- set_covering2.pl: Set covering (placing security telephones on a campus, Taha)
- set_covering3.pl: Set covering (selecting senators for a committee, Murty)
- set_covering4.pl: Set covering and set partition (Lundgren, Rönnqvist, Värbrand: "Optimeringslära")
- set_covering_deployment.pl: Set covering deployment problem (placing armies in the Roman Empire)
- set_covering_skiena.pl: Set covering (Skiena)
- set_partition.pl: Set partition problem
- ski_assignment.pl: Ski assignment problem
- sliding_sum.pl: Decomposition of global constraint
- smuggler_knapsack.pl: Smuggler's knapsack (Marriott & Stuckey)
- stable_marriage.pl: Stable marriage problem (examples from Van Hentenryck's OPL book, and MathWorld)
- steiner.pl: Steiner triplets (using boolean list as set representation)
- strimko2.pl: Strimko puzzle (Latin squares with "streams")
- stuckey_seesaw.pl: Seesaw problem (Marriott & Stuckey "Programming with Constraints")
- subset_sum.pl: Subset sum problem (Murty)
- sudoku.pl: Sudoku puzzle, an "all-loop" version (contains all 91 problems from Gecode's Sudoku problem set: 9x9, 16x16, and 25x25 problems)
- survo_puzzle.pl: Survo puzzle
- talisman_square.pl: Talisman square
- timpkin.pl: Mrs Timkin's Age (Dudeney)
- to_num.pl: Converts array <-> number
- torn_numbers.pl: Torn Numbers problem (Dudeney)
- tourist_site_competition.pl: Tourist site competition (P. Flener)
- traffic_lights.pl: Traffic lights problem (CSPLib problem 16)
- trains.pl: Trains problem (simple example of
table/2 from SWI Prolog manual)
- tsp.pl: Traveling salesperson problem, using loops and circuit (examples from Ulf Nilsson, SICStus' example tsp.pl, and the GLPK model tsp.mod)
- tunapalooza.pl: Tunalalooza puzzle (Dell Logic Puzzles)
- twin_letters.pl: Twin letters (Mozart/Oz)
- volsay1.pl: Volsay production problem (Van Hentenryck, The OPL Book)
- volsay2.pl: Volsay production problem (Van Hentenryck, The OPL Book), slightly different from volsay1.pl
- warehouse.pl: Warehouse location problem (OPL example)
- who_killed_agatha.pl: Who killed agatha? (a.k.a. The Dreadsbury Mansion Murder Mystery, an automated reasoning problem)
- xkcd.pl: Knapsack problem from xkcd
- young_tableaux.pl: Young tableaux and partitions