My MiniZinc page
(This original of this file is http://www.hakank.org/minizinc/index.html.)
This page was created by Hakan Kjellerstrand (hakank@bonetmail.com).
MiniZinc constraint programming system
MiniZinc is a very interesting constraint programming system/modeling language with a high level syntax. Some important links:
Solvers
In order to solve a problem stated in the MiniZinc modeling language, a solver must be used. The following solvers were available as of 2009-09-16.
Utilities
mzn_show.pl
Perl program mzn_show.pl
Since version 1.0 MiniZinc don't support the output [] anymore, and
it can be hard to see structured output, e.g. matrices. This program gives the result somewhat nicer output. I blogged about the program (first version) here: Miscellaneous news.
Usage: solver problem.mzn | mzn_show.pl "{parameter}"
The parameters are:
- {tr:from:to:}: translate digit to another digit/character
- {trvar:var:from:to:}: translate digit to another digit/character for a specific variable var
- {trtr:from_string:replacement_string:}: translates all digits in from_string to the corresponding digit/character in replacement_string (inspired from the Unix tr command)
- {trtrvar:var:from_string:replacement_string:}: as trtr but for a specific variable var
- {nospaces}: don't show space after character
- {noprintf}: don't try to be clever with printf stuff
- {noresult}: don't print the numerical result (just the translations)
- {nonogram}: shortcut for {trtr:12: #} {nospace} {noresult}
Example: for showing a nicer picture of a Nonogram:
flatzinc nonogram_create_automaton2.fzn | mzn_show.pl "{tr:1: :} {tr:2:#:} {nospace}"
Where the {tr:from:to:} means translate digit from to character to, and {nospace} means that no spaces are shown after each digit/character.
This is now probably better written with trtr:
flatzinc nonogram_create_automaton2.fzn | mzn_show.pl "{trtr:12: #:} {nospace}"
mzn.pl
I have also created a Perl program for handling all the different solvers from the command line, as well as changing the model parameters etc. The program may be obtained upon request by mailing me (hakank@bonetmail.com).
My MiniZinc models
The following is a list of (some of) my models: simple puzzles and not so simple puzzles, standard operation research / integer programming examples, and some global constraints (that are not in the MiniZinc globals.mzn). Some are just examples of modelling in MiniZinc.
Almost all models are commented with sources or inspirations, and quite a few have the main constraints generalized as a predicate.
All files (models, datafiles, etc) are available from the G12 SVN repository: www.g12.cs.mu.oz.au/mzn/hakank/.
Contents
The models are collected in the following categories:
Puzzles, small, and large
- 3_coins.mzn: 3 coins (THT), in exactly 3 flips make HHH or TTT
- 3_jugs.mzn: 3 jugs problem (as shortest path problem)
- 3_jugs2.mzn: 3 jugs problem (using shortest_path_model.mzn)
- 3_jugs2_all.mzn: 3 jugs problem (using shortest_path_model.mzn), searches for all solutions (which happens to be unique)
- a_round_of_golf.mzn: A round of golf puzzle (Dell Logic Puzzles)
- added_corner.mzn: Added corner puzzle
- arch_friends.mzn: Arch friends puzzle (Dell Logic Puzzles)
- atom_smasher.mzn: Digital Atom Smasher. alphametic problem: sqrt(ATOM) = A + TO + M
- averbach_1.2.mzn: Example 1.2 i Averbach & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.3.mzn: Example 1.3 i Averbach & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.4.mzn: Example 1.4 i Averbach & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.5.mzn: Example 1.5 i Averbach & Chein "Problem Solving Through Recreational Mathematics"
- babysitting.mzn: Babysitting puzzle (Dell Logic Puzzles)
- bales_of_hay.mzn: Bales of hay puzzle
- bank_card.mzn: Bank card puzzle
- birthdays_2010.mzn: A simple birthday puzzle of my own, based on a coincidence of my and my brother's birth years.
- breaking_news.mzn: Breaking news puzzle (Dell Logic Puzzles)
- bridge_and_torch_problem.mzn: Bridge and torch problem, crossing a bridge with a torch (a.k.a. The Midnight Train, and Dangerous crossing).
Data files:
- bus.mzn: Bus puzzle (from rec.puzzles FAQ)
- calculs_d_enfer.mzn: Calculs d'enfer puzzle (from the NCL manual)
- candles.mzn: Birthday candles problem (from Choco)
- clock_triplets.mzn: Clock Triplets
- coins_grid.mzn: Coins Grid (Tony Hurlimann)
- coins3.mzn: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro
- coins_problem.mzn: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro (alternative solution based on OPL code)
- coins_41_58.mzn: Minimize number of coins - with the same amount of the different denominations - that sums to 41.58 GBP
- col_sum_puzzle.mzn: Find out values in a matrix, given column and row sums and some hints.
- consecutive_digits.mzn: Consecutive digits (Martin Gardner)
- cube_sum.mzn: Sum a number with the minimum number of different cubes
- crossfigure.mzn: Crossfigure problem (CSPLib problem 21)
- crossword.mzn: Crossword solving (standard constraint programming example)
- crossword2.mzn: Crossword solving (standard constraint programming example), more general approach
- crypta.mzn: crypta, alphametic problem (standard Prolog benchmark)
- crypto.mzn: crypto, alphametic problem (standard Prolog benchmark), constraint programming model
- crypto_ip.mzn: crypto, alphametic problem (standard Prolog benchmark), integer programming model
- cur_num.mzn: Curious Number (Dudeney)
- curious_set_of_integers.mzn: Curious set of integers (Martin Gardner)
- defending_castle.mzn: Defending the Castle (Cut the knot)
- devils_word.mzn: Devil's Word problem (see the Devil's word page)
- digital_roots.mzn: Digital roots
- digits_of_the_square.mzn: Digits of the square problem
- dimes.mzn: Dimes puzzle (rec.puzzles FAQ)
- dinner.mzn: A dinner problem
- dividing_the_spoils.mzn: Dividing the spoils (Sam Loyd)
- divisible_by_7.mzn: Divisible by 7 (Sam Loyd)
- donald.mzn: Alphametic puzzle: DONALD + GERALD = ROBERT
- drinking_game.mzn: Drinking game (Marriott & Stuckey)
- einav_puzzle.mzn: Solving the A programming puzzle from Einav
- eliza_pseudonym7.mzn: Eliza Pseudonym of Puzzlania 7
- ein_ein_ein_ein_vier.mzn: EIN+EIN+EIN+EIN=VIER (Martin Gardner)
- einstein_hurlimann.mzn: Einstein puzzle (variant of Zebra puzzle)
- Enigma problems (originally from New Scientist Magazine)
- ett_ett_ett_ett_ett__fem.mzn: Alphametic puzzle ETT + ETT + ETT + ETT + ETT = FEM
- family_riddle.mzn: Family riddle
- fancy.mzn: Mr Greenguest puzzle (Fancy dress puzzle)
- farm_puzzle0.mzn: Farm puzzle, simple model
- farm_puzzle.mzn: Farm puzzle, more general model
- fill_a_pix.mzn: Fill-a-pix puzzle.
Data files:
- five_brigades.mzn: Five brigades (Dudeney)
- four_islands.mzn: Four islands puzzle (Dell Logic Puzzles)
- fractions.mzn: Fractions, alphametic problem (standard Prolog benchmark)
- franklin_8x8_magic_square.mzn: Benjamin Franklin's 8x8 Magic Square
- futoshiki.mzn: Futoshiki puzzle
- gardner_dinner.mzn: Dinner problem (Martin Gardner)
- gardner_prime_puzzle.mzn: Martin Gardner's prime puzzle
- grocery2.mzn: Grocery problem, alternative version
- hardy_1729.mzn: Hardy's 1729 problem
- hidato.mzn: Hidato puzzle
- hidato_exists.mzn: Hidato puzzle, same as above but it use
exists which is less efficient
- huey_dewey_louie.mzn: Huey, Dewey, Louie, logical problem from Marriott & Stuckey "Programming in Constraints"
- heterosquare.mzn: Heterosquare problem
- how_old_am_i.mzn: How old am I (from Choco)
- hundred_doors_unoptimized.mzn: 100 doors problem, unoptimized (array version) (Rosetta code)
- hundred_doors_unoptimized2.mzn: 100 doors problem, unoptimized (array version, alternative model) (Rosetta code)
- hundred_doors_optimized.mzn: 100 doors problem, optimized (set version) (Rosetta code)
- hundred_doors_optimized_array.mzn: 100 doors problem, optimized (array version) (Rosetta code)
- hundred_fowls.mzn: Hundred Fowls puzzle
- high_iq_problem.mzn: "High IQ problem"
- jobs_puzzle.mzn: Jobs puzzle (an automated reasoning problem)
- kakuro.mzn: Kakuro puzzle
- kenken2.mzn: KenKen puzzle
- killer_sudoku.mzn: Killer Sudoku puzzle
- knight_path.mzn: Knight path
- least_diff.mzn: Least diff problem: What is the smallest difference between two numbers X - Y if you must use all the digits (0..9) exactly once?
- lecture_series.mzn: Lecture series puzzle (Dell Logic Puzzles)
- letter_square.mzn: Letter square problem (Vaderlind).
Data files:
- locker.mzn: Locker puzzle.
- logic_puzzle_aop.mzn: Logic puzzle (from The Art of Prolog)
- M12.mzn: Solving the M12 puzzle
- magic.mzn: Magic square, integer programming (GLPK)
- magic3.mzn: Magic sequence, 3 x 3 (this formulations is from a standard Prolog benchark)
- magic4.mzn: Magic sequence, 4 x 4 (this formulations is from a standard Prolog benchark)
- magic_hexagon.mzn: Magic hexagon (CSPLib, problem 23)
- magic_sequence.mzn: Magic sequence (CSPLib)
- magic_sequence2.mzn: Magic sequence (CSPLib), alternative model
- magic_sequence3.mzn: Magic sequence (CSPLib), alternative model
- magic_sequence4.mzn: Magic sequence (CSPLib), alternative model
- magic_squares_and_cards.mzn: Magic squares and cards (Martin Gardner)
- marathon.mzn: Marathon puzzle (XPress example), MIP model
- marathon2.mzn: Marathon puzzle (XPress example), CP model
- message_sending.mzn: Message sending puzzle (cf all_paths_graph.mzn)
- minesweeper.mzn: Minesweeper puzzle
- minesweeper_model.mzn: Minesweeper puzzle, general model to be used with the following problems:
- miss_manners.mzn: Miss Manners' seating problem (standard benchmark for rule engines). Data:
- missing_digit.mzn: Missing digit probblem
- money_change.mzn: Simple money change problem
- monkey_coconuts.mzn: The Monkey and Coconuts problem
- monks_and_doors.mzn: Eight monks and four doors
- multipl.mzn: Unknown multiplication (standard Prolog benchmark)
- murder.mzn: Murder puzzle
- music_men.mzn: Music men puzzle
- n_puzzle.mzn: N-puzzle, e.g. 8-puzzle, 15-puzzle
- narcissistic_numbers.mzn: Narcissistic numbers
- number_puzzle.mzn: A number puzzle (of some kind)
- number_of_regions.mzn: Number of regions (Vaderlind, Guy, Larson: "The Inquisitive Problem Solver", problem 21)
- nine_digit_arrangement.mzn: Nine digit arrangement (Martin Gardner)
- nine_to_one_equals_100.mzn: Nine to one equals 100 (Martin Gardner)
- nonogram.mzn: Nonogram, a.k.a. Painting by numbers. Also, see "nonogram_regular.mzn" and "nonogram_create_automaton.mzn" below.
- nonogram_regular.mzn: Nongoram, a.k.a. Painting by numbers. This version uses the
regular constraints and is much faster than nonogram.mzn.
Note that the data models must be in a specific format (listing the finite states for the regular constraint, converted (for example) by the Perl program make_nonogram_automata.pl. Below is a list of data instances with the proper format. The data files used with nonogram_regular.mzn is the "*_aut.dzn" version. Also, see "nonogram_create_automaton.mzn" below.
- nonogram_create_automaton.mzn: Nonogram solver. This version uses the
regular constraints and is much faster than nonogram.mzn.
In contract to nonogram_regular.mzn it creates the automata from the Nonogram patterns (clues), so no preprocessing step is needed. The data file used is the files shown above for "nonogram_regular.mzn" with no "_aut" in its name.
- nonogram_create_automaton2.mzn: Nonogram solver. A version of nonogram_create_automaton.mzn that calculates the states as par variables (not decision variables). Note: It is the recommended model, especially for solvers that have an optimized version of the
regular constraint.
Data files: besides the data files above, there is now a dedicated page for Nonogram problems: MiniZinc: Nonogram problem instances in .dzn format (from JaCoP's distribution) .
- number_generation.mzn: Number generation (cf Devil's word)
- OandX.mzn: Three Dimensional Nought and Crosses (Tic-Tac-Toe) (Williams)
- olympic.mzn: Olympic problem (standard Prolog benchmark)
- pandigital_numbers.mzn: Pandigital numbers (any base <= 10)
- peacableArmyOfQueens.mzn: Peacable Army of Queens
- photo_hkj.mzn: Photo problem
- photo_hkj2_model.mzn: Photo problem model
- photo_hkj2_data1.mzn: Data for photo problem
- photo_hkj2_data2.mzn: Data for photo problem
- place_number.mzn: The Eight Number Puzzle
- pool_ball_triangles.mzn: Pool-ball triangles (Martin Gardner)
- puzzle1.mzn: Yet another column/row sum problem
- pyramid_of_numbers.mzn: Pyramid of numbers (Rosetta code)
- queens_ip.mzn: n-queens problem, integer programing model (GLPK)
- raven_puzzle.mzn: "Polyglot puzzle" (from Raven, swedish)
- remarkable_sequence.mzn: Remarkable sequence (from an Alma-0 model)
- rook_path.mzn: Rook path (on a square matrix)
- rookwise_chain.mzn: Rookwise Chain (Martin Gardner)
- safe_cracking.mzn: Safe cracking
- seating_plan.mzn: Seating plan (Daniel L. Dudley, The Nut Cracker suit #1)
- secret_santa.mzn: Secret Santa problem
- secret_santa2.mzn: Another Secret Santa problem
- self_referential_quiz.mzn: Self-referential quiz
- send_more_money.mzn: Alphametic puzzle: SEND + MORE = MONEY
- send_more_money2.mzn: Alphametic puzzle: SEND + MORE = MONEY, alternative model
- send_more_money_any_base.mzn: Alphametic puzzle: SEND + MORE = MONEY, in any base
- send_more_money_ip.mzn: Alphametic puzzle: SEND + MORE = MONEY, integer programming model (GLPK)
- send_most_money.mzn: Alphametic puzzle: SEND + MOST = MONEY (maximize MONEY)
- sequence_2_3.mzn: Simple permutation puzzle
- seseman.mzn: Seseman Convent problem (see Seseman Convent problem)
- seseman2.mzn: Seseman Convent problem, generalized model
- skyscraper.mzn: Skyscraper puzzle
- spy_girls.mzn: Spy girls problem
- set_puzzle.mzn: Solving SET Puzzles
- smullyan_knights_knaves.mzn: Raymond Smullyan's Knights and Knaves problems
- smullyan_knights_knaves_normals.mzn: Raymond Smullyan's Knights, Knaves, and Normals problems
- smullyan_knights_knaves_normals_bahava.mzn: Raymond Smullyan's Knights, Knaves, and Normals at the Island of Bahava problems
- smullyan_lion_and_unicorn.mzn: Raymond Smullyan's Lion and Unicorn problems
- smullyan_portia.mzn: Raymond Smullyan's Portia problems
- solitaire_battleship.mzn: Solitaire Battleship
- square_root_of_wonderful.mzn: Square Root of Wonderful (Martin Gardner)
- strimko.mzn: Strimko puzzle (Latin squares with "streams")
Some data files:
- strimko2.mzn: Strimko puzzle (Latin squares with "streams"). This variant uses an easier instance representation than strimko.mzn
Some data files:
- sudoku_gcc.mzn: Sudoku, using the global cardinality constraint.
sudoku_gcc_model.mzn, this is a general Sudoku to be included from a Sudoku problem instance. In the directory sudoku problems are all the Sudoku problems from Gecode's Sudoku model sudoku.cpp.
- sudoku_ip.mzn: Sudoku, integer programming (GLPK)
- sudoku_25x25_250.mzn: Sudoku 25 x 25 problen (very hardcoded, from a Prolog benchmark)
- subsets_100.mzn: Subsets 100 (rec.puzzles FAQ)
- sum_to_100.mzn: Five numbers should sum to 100, and all numbers must be divisible by 2 or 5
- survo_puzzle.mzn: Survo puzzle
- talisman_square.mzn: Talisman Square
- the_bomb.mzn: The bomb, logical puzzle (Janko "Die Bombe")
- three_digit.mzn: Three digit problem
- tickTackToe.mzn: Tick Tack Toe (Tic Tac Toe)
- tomography.mzn: Discrete Tomography (one color model)
- tomography_n_colors.mzn: Discrete Tomography (n color model)
- torn_number.mzn: Torn number puzzle (Dudeney)
- tunapalooza.mzn: Tunapalooza puzzle (Dell Logic Puzzles)
- two_cube_calendar.mzn: Two cube calendar (Martin Gardner)
- vingt_cinq_cinq_trente.mzn: VINGT+ CINQ + CINQ = TRENTE (Martin Gardner)
- war_or_peace.mzn: War or peace problem (Alma-0)
- water_buckets1.mzn: Water bucket problem (generalized)
- who_killed_agatha.mzn: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, a automated reasoning problem)
- wolf_goat_cabbage_lp.mzn: Wolf, goat, cabbage problem (a.k.a. river crossing problem) using a LP model. Shows all (2) solutions.
- word_golf.mzn: Word golf (word chain)
- word_golf_n3.mzn: 3 letter words for Word golf
- word_square.mzn: Word square: square matrix cross words (fill the whole square with unique words). (Data files: word_len3.mzn, word_len4.mzn, word_len5.mzn)
- wwr.mzn: alphametic problem: WRONG + WRONG = RIGHT
- xkcd.mzn: xkcd's knapsack problem (see the xkcd strip for the problem)
- zebra_inverse.mzn: Zebra puzzle, using global constraint
inverse instead of all_different
- zebra_ip.mzn: Zebra puzzle, integer programming model (GLPK)
Operations research, linear programming, integer programming
- agprice.mzn: Agricultural pricing (Williams)
- assignment.mzn: Assignment problem (Winston)
- assignment2.mzn: Assignment problem (Winston's swimming team example)
- assignment2_2.mzn: Assignment problem (Winston's swimming team example, expanded)
- assignment3.mzn: Assigment problem (Winston, celebreties on an island)
- assignment4.mzn: Yet another assigment problem
- assignment5.mzn: Yet another assigment problem
- assignment6.mzn: Assigment problem (GLPK:s example assign.mod)
- assignment_model.mzn: Assigment problem (model)
- bus_scheduling.mzn: Bus scheduling (Taha)
- capital_budget2.mzn: Capital Budget (Winston)
- chessset.mzn: Chess set problem (XPress)
- coloring_ip.mzn: Map coloring, integer programming (inspired by the GLPK model color.mod)
- constraint.mzn: Optimizing a constraint (Williams)
- contractor_costs.mzn: Contractor costs (Sam Loyd)
- crew.mzn: Crew scheduling (Gecode)
- crossbar.mzn: Crossbar problem (Prolog benchmark problem)
- critical_path1.mzn: Critical Path (Winston)
- curve_fitting1.mzn: Curve fitting 1 (Williams)
- curve_fitting2.mzn: Curve fitting 2 (Williams)
- curve_fitting3.mzn: Curve fitting 3, least squares (Williams)
- cutting_stock_winston.mzn: Cutting stock problem (Winston)
- dea.mzn: Data Envelopment Analysis (DEA) model (GLPK example)
- decent.mzn: Decentralization (Williams)
- diet1.mzn: Diet problem (standard OR example)
- diet2.mzn: Diet problem, larger (GLPK example)
- fixed_charged_transportation_problem.mzn: Fixed charged transportation problem
- food.mzn: Food manufacture problem (GLPK, AMPL)
- food2.mzn: Food manufacture problem, with extra constraints (GLPK, AMPL)
- football.mzn: Buying soccer players (lp_solve mailing list)
- freight_transfer.mzn: Freight Transfer (John Hooker)
- furniture_moving.mzn: Optimizing furniture moving (Marriott and Stuckey)
- gap.mzn: Generalized Assignment Problem (GLPK, AMPL)
- giapetto.mzn: Simple optimization problem of maximizing profit
- hitchcock_transporation_problem.mzn: Hitchcock-Koopmans transportation problem
- ice_cream.mzn: Ice cream production given monthly demand.
- integer_programming1.mzn: Simple integer programming problem
- jssp.mzn: Job-Shop Scheduling Problem (GLPK)
- knapsack_investments.mzn: Knapsack (investment) problem (Lundgren, Rönnqvist, Värbrand: Optimerings lära)
- lager.mzn: Stock model (swedish)
- least_square_optimeringslara_286.mzn: Least sqauare (Lundgren, Rönnqvist, Värbrand: Optimeringslära)
- lightmeal.mzn: Lightmeal problem (Colmerauer)
- lightmeal2.mzn: Lightmeal problem (Colmerauer), integer programming version (and more general than lightmeal.mzn)
- markov_chains.mzn: Markov chain of market shares (from "Statistisk Dataanalys")
- markov_chains_taha.mzn: Markov chains (fertlizer example from Taha "Operations Research")
- max_cut.mzn: Maximum cut problem (GLPK)
- max_flow_taha.mzn: Maximum flow problem (Taha)
- max_flow_winston1.mznMaximum flow problem (Winston)
- maxflow.mzn: Maximum flow problem (GLPK)
- mfasp.mzn: Minimum Feedback Arc Set Problem (GLPK)
- mfvsp.mzn: Minimum Feedback Vertex Set Problem (GLPK)
- misp.mzn: Maximum Independent Set Problem (GLPK)
- mvcp.mzn: Minimum Vertex Cover Problem (GLPK)
- nadel.mzn: B.A. Nadel's construction problem
- organize_day.mzn: Scheduling, organizing a day (ECLiPSe)
- pert.mzn: PERT problem (van Hentenryck)
- plan.mzn: Planning model (GLPK)
- post_office_problem.mzn: Post office problem (Winston)
- post_office_problem2.mzn: Post office problem, generalized model (Winston)
- prod0.mzn: Optimization problem (AMPL)
- product_configuration.mzn: Product configuration (John Hooker)
- rostering.mzn: Rostering problem (Regin)
- schedule1.mzn: Scheduling using cumulative constraint (Sicstus)
- scheduling_bratko.mzn: Scheduling problem from Ivan Bratko "Prolog - programming for Artificial Intelligence", example 1
- scheduling_bratko2.mzn: Scheduling problem from Ivan Bratko "Prolog - programming for Artificial Intelligence", example 2
- scheduling_chip.mzn: Scheduling problem from Nicolas Beldiceanu & Evelyne Contejean "Introducing Global Constraints in CHIP", page 3
- scheduling_speakers.mzn: Scheduling speakers (Rina Dechter)
- ski_assignment_problem.mzn: Ski assignment problem
- social_golfers1.mzn: Social golfers (OPL)
- sportsScheduling.mzn: Sport scheduling
- spp.mzn: Shortest path problem, integer programming (GLPK)
- stable_marriage.mzn: Stable marriage
- stigler.mzn: Original Stigler's 1939 diet problem (GLPK)
- stuckey_assignment.mzn: Assignment problem (Marriott and Stuckey)
- stuckey_seesaw.mzn: Balancing on a seesaw (Marriot and Stuckey)
- talent.mzn: Talent example from ILOG OPL
- transp.mzn: Transportation problem (GLPK)
- transportation.mzn: Transportation problem (ECLiPSe)
- transportation2.mzn: Transportation problem, generalized model
- tsp.mzn: Travelling Salesman Problem, integer programming (GLPK)
- transshipment.mzn: Transshipment problem (Winston)
Non linear problems
Combinatorial problems
- all_interval.mzn: All interval problem (series), (CSPLib problem 7)
- all_paths_graph.mzn: (All) paths from a graph presentation (cf message_sending.mzn)
- balanced_matrix.mzn: Balanced matrix
- bin_packing.mzn: Bin packing
- bin_packing2.mzn: Bin packing (different from the one above)
- bpp.mzn: Bin packing (GLPK example, but not using the "z heuristic")
- checker_puzzle.mzn: Checker puzzle (from MathOverflow Placing checkers with some restrictions)
- color_simple.mzn: Simple coloring of a map (Murty)
- combinatorial_auction.mzn: Simple combinatorial auction problem (compare with the set covering/set partition problem in set_covering4b.mzn)
- decision_tree_binary.mzn: Binary decision tree
- debruijn_binary.mzn: de Bruijn sequence (graph)
- dominating_set.mzn: Dominating set problem
- finding_celebrities.mzn: Finding celebrities at a party (indicence matrix).
- finding_celebrities2.mzn: Finding celebrities at a party, using only set constraints.
- fix_points.mzn: Number of fix points in an array
- graph_degree_sequence.mzn: Degree sequence for graphs, both matrix and edge representation
- gray_code.mzn: Gray code
- hamming_distance.mzn: Hamming distance
- K4P2GracefulGraph.mzn: K4P2 Graceful Graph
- K4P2GracefulGraph2.mzn: K4P2 Graceful Graph (more general model)
- knapsack1.mzn: Knapsack problem
- knapsack2.mzn: Another knapsack problem
- knapsack_problem.mzn: Knapsack problem (Rosetta code)
- lams_problem.mzn: Lam's problem (CSPLib problem 25)
- langford2.mzn: Langford's number problem (CSPLib problem 24)
- latin_square.mzn: Latin squares
- lectures.mzn: Lectures, schedule problem from Biggs "Discrete Mathematics"
- lichtenstein_coloring.mzn: Coloring problem: Lichtenstein's communes and exclaves
- logical_design.mzn: Logical design (Williams)
- map.mzn: Simple coloring of a map
- map_stuckey.mzn: Another coloring of a map (Marriott and Stuckey)
- maximum_subarray.mzn: Maximum subarray (Rosetta code)
- modulo_partition.mzn: Function partitioning
- parallel_resistors.mzn: Parallel resistors problem problem from Marriott & Stuckey "Programming in Constraints"
- partial_latin_square.mzn: Partial Latin squares
- partitions.mzn: Integer partitions
- perfect_shuffle.mzn: Perfect shuffle
- pigeon_hole.mzn: Pigeon hole problem (CLP-FD)
- pigeon_hole2.mzn: Another pigeon hole problem
- power_set.mzn: Power set
- quasiGroup3Idempotent.mzn: Quasigroup existence problem 3(CSPLib)
- quasiGroup3NonIdempotent.mzn: Quasigroup existence problem 3 (CSPLib)
- quasiGroup4Idempotent.mzn: Quasigroup existence problem 4(CSPLib)
- quasiGroup4NonIdempotent.mzn: Quasigroup existence problem 4(CSPLib)
- quasiGroup5Idempotent.mzn: Quasigroup existence problem 5(CSPLib)
- quasiGroup5NonIdempotent.mzn: Quasigroup existence problem 5(CSPLib)
- quasiGroup6.mzn: Quasigroup existence problem 6 (CSPLib)
- quasiGroup7.mzn: Quasigroup existence problem 7 (CSPLib)
- quasigroup_completion.mzn: Quasigroup completion problem
- quasigroup_completion_model.mzn: Quasigroup completion problem, model used by the following instances:
- ramsey_partition.mzn: Ramsey partition problem
- runs.mzn: Number of runs in an array (sequence)
- sat.mzn: Satisfiability Problem, integer programming (GLPK)
- satisfy.mzn: Satisfiability Problem (Alma-0)
- set_covering.mzn: Set covering, placing of firestations (Winston)
- set_covering2.mzn: Set covering, number of security telephons on a campus (Taha)
- set_covering3_model.mzn: Set covering model
- set_covering3.mzn: Set covering, senators making a committe (Murty)
- set_covering4.mzn: Set covering problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
- set_covering4b.mzn: Set covering problem, generalized version of set_covering4.mzn
- set_covering5.mzn: Set covering, work scheduling (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
- set_covering_deployment.mzn: Set covering deployment
- set_covering_skiena.mzn: Set covering (Skiena)
- set_packing.mzn: Set packing
- set_partition.mzn: Set partitioning
- shortest_path1.mzn: Shortest path problem, selling/buying a car (Winston)
- shortest_path2.mzn: Shortest path problem (Winston)
- shortest_path_model.mzn: Model for shortest path
- shortest_path_model_all.mzn: Model for shortest path, for showing all solutions (assuming an added constraint in the calling model)
- sonet_problem.mzn: SONET problem
- traffic_lights.mzn: Traffic lights problem (CSPLib problem 16)
- traffic_lights_table.mzn: Traffic lights problem (CSPLib problem 16), same as traffic_lights.mzn except that is use the global constraint table.
- subset_sum.mzn: Subset sum (Murty)
- temporal_reasoning.mzn: Temporal reasoning (Apt)
- tourist_site_competition.mzn: Tourist site competition (Pierre Flener)
- transpose.mzn: (Square) matrix operations, transpose, scalar addition, scalar multiplication
- tsp_circuit.mzn: Travelling salesperson problem, using circuit predicate
- voltage_divider.mzn: Voltage divider problem problem from Marriott & Stuckey "Programming in Constraints"
- young_tableaux.mzn Young tableaux
Global constraints (decompositions)
Here are some implementations (as decompositions) of the global constraints which are not already implemented in the MiniZinc globals.mzn, described in the great collection Global Constraint Catalog. Some global constraints not in the catalogue are also modelled.
Name clashes: If there exists a file in default directory with the same name as one of the global constraints defined in "global.mzn", there will be a name clash. If that happens, just rename the file in the default directory to something else, e.g. constraint_me.mzn.
- all_differ_from_at_least_k_pos.mzn: all_differ_from_at_least_k_pos, all rows in a matrix has values that differs in at least k positions
- all_equal_me.mzn: all_equal
- all_min_dist.mzn: all_min_dist, all values must have a minimum distance to each other
- alldifferent_cst.mzn: alldifferent_cst, and alldifferent_cst using multiplication instead of addition
- alldifferent_except_0.mzn: alldifferent except 0
- alldifferent_interval.mzn: alldifferent_modulo, all values modulo k shall be different
- alldifferent_modulo.mzn: alldifferent_modulo, all values modulo k shall be different
- alldifferent_on_intersection.mzn: alldifferent_on_intersection
- alldifferent_partition.mzn: alldifferent_partition
- alldifferent_same_value.mzn: alldifferent_same_value
- alldifferent_soft.mzn: alldifferent_soft (alldifferent_soft_ctr and alldifferent_soft_var)
- allperm.mzn: allperm, ensures that the first rows in a matrix is lexically less than all permutation of all other rows
- all_min_dist.mzn: all_min_dist, all pairs in an array have a distance of at least c
- among_diff_0.mzn: among_diff_0, number of values different from 0
- among_interval.mzn: among_interval, number of values in a certain interval
- among_low_up.mzn: among_low_up, the number values in an array matched another array shoule be constrained to low and up
- among_modulo.mzn: among_modulo, the number values in an array where a value modulo quotient = remainder
- among_seq.mzn: among_seq
- and.mzn: and, generalized and (array)
- arith.mzn: arith, enforces that all values in an array is RELOP (equal, not equal, less than, etc) some VALUE
- arith_or.mzn: arith_or
- arith_sliding.mzn: arith_sliding, all sliding sums from 1..j must satisfy RELOP VALUE
- assign_and_counts.mzn: assign_and_counts
- assign_and_nvalue.mzn: assign_and_nvalues
- atleast_nvalue.mzn: atleast_nvalue, at least NVAL values are different in an array
- atmost1.mzn: atmost1
- atmost_nvalue.mzn: atmost_nvalue, at most NVAL values are different in an array
- balance.mzn: balance, difference between the least and largest number of occurrences in an array
- balance_interval.mzn: balance_interval, difference between the least and largest number of occurrences in intervals in an array
- balance_modulo.mzn: balance_modulo, difference between the least and largest number of occurrences of the equivalience classes modulo an integer
- balance_partition.mzn: balance_partition, difference between the least and largest number of occurrences in partitions
- between_min_max.mzn: between_min_max, a specific number is between the minimum and maximum value of an array
- binary_tree.mzn: Binary tree
- bipartite.mzn: Bipartite graph
- cardinality_atleast: cardinality_atleast
- cardinality_atmost: cardinality_atmost
- cardinality_atmost_partition: cardinality_atmost_partition
- change.mzn: circular change, number of changes in an array
- change_pair.mzn: change_pair
- change_partition.mzn: change_partition
- circular_change.mzn: circular change, number of changes in an array (as change but with wrapping around the corner)
- circuit.mzn: circuit
- clique.mzn: clique
- common.mzn: common, also used_by
- common_interval.mzn: common_interval
- common_modulo.mzn: common_modulo
- common_partition.mzn: common_partition
- cond_lex_cost.mzn: cond_lex_cost
- cond_lex_less.mzn: cond_lex_less, cond_lex_lesseq, cond_lex_greater, cond_lex_greatereq
- contains_array.mzn: contains ("in" for arrays)
- count_ctr.mzn: count, more general than count in MiniZinc's globals.mzn
- counts.mzn: counts
- correspondence.mzn: correspondence
- cumulative_test.mzn: Test of cumulative (defined in globals.mzn)
- cumulative_test_mats_carsson.mzn: Another test of cumulative (small example from one of Mats Carlsson's lecture)
- cycle.mzn: cycle
- decreasing_me.mzn: decreasing
- derangement.mzn: derangement
- differs_from_at_least_k_pos.mzn: differs_from_at_least_k_pos
- diffn.mzn: diffn, (with three different representations of the orthotopes)
- discrepancy.mzn: discrepancy
- discjuntive.mzn: disjunctive
- distance_between.mzn: distance_between
- distance_change.mzn: distance_change
- domain.mzn: domain
- domain_constraint.mzn: domain_constraint
- element_greatereq.mzn: element_greatereq
- element_lesseq.mzn: element_lesseq
- element_matrix.mzn: element_matrix
- element_product.mzn: element_product
- element_sparse.mzn: element_sparse
- elementn.mzn: elementn
- elements.mzn: elements
- elements_alldifferent.mzn: elements_alldifferent
- global_cardinality_no_loop.mzn: global_cardinality_no_loop
- global_cardinality_with_costs.mzn: global_cardinality_with_costs
- global_cardinality_table.mzn: global_cardinality, using a table with the occurrences
- global_contiguity.mzn: global_contiguity
- imply.mzn: imply
- inflexions.mzn: inflexions, number of peaks in a sequence
- in_interval.mzn: in_interval
- in_relation.mzn: in_relation
- in_same_partition.mzn: in_same_partition
- in_set.mzn: in_set (cf the built in "in")
- indexed_sum.mzn: indexed_sum
- int_value_precede.mzn: int_value_precede
- inverse_within_range.mzn: inverse within range
- ith_pos_different_from_0.mzn: ith pos different from 0
- k_alldifferent.mzn: k alldifferent (all rows satisfy the alldifferent constraint)
- k_same.mzn: k_same
- k_same_modulo.mzn: k_same_modulo
- lex2.mzn: lex2
- lex_alldifferent.mzn: lex_alldifferent
- lex_between.mzn: lex_between
- lex_chain_less.mzn: lex_chain_less
- lex_different.mzn: lex_different
- lex_greater.mzn: lex_greater
- longest_change.mzn: longest change, size of the longest sub sequence which satisfy a comparison operator (such as !=, <, > etc)
- max_index.mzn: max_index, (also the extension max_index_val)
- max_n.mzn: max_n
- max_nvalue.mzn: max_nvalue
- max_size_set_of_consecutive_var.mzn: max_size_set_of_consecutive_var
- maximum_modulo.mzn: maximum_modulo
- min_index.mzn: min_index, (also the extension min_index_val)
- min_n.mzn: min_n
- min_nvalue.mzn: min_nvalue
- minimum_except_0.mzn: minimum_except_0
- minimum_greater_than.mzn: minimum_greater_than
- minimum_modulo.mzn: minimum_modulo
- minimum_weight_alldifferent.mzn: minimum_weight_alldifferent
- nchange.mzn: nchange, (also a generalized version nchange_cmp with choice of operators)
- nclass.mzn: nclass
- n_partitioning.mzn: n_partitioning
- n_change.mzn: n_change
- my_nvalue.mzn: nvalue, also: atleast_nvalue and atmost_nvalue (note: nvalue is defined in globals.mzn, hence the name my_nvalue)
- next_greater_element.mzn: next_greater_element
- next_value.mzn: next_value
- not_all_equal.mzn: not_all_equal
- not_in.mzn: not_in
- npair.mzn: npair
- nvalue_on_intersection.mzn: nvalue_on_intersection
- nvalues.mzn: nvalues
- nvalues_except_0.mzn: nvalues_except_0
- open_alldifferent.mzn: open_alldifferent
- open_among.mzn: open_among
- open_atleast.mzn: open_atleast
- open_atmost.mzn: open_atmost
- open_global_cardinality.mzn: open_global_cardinality
- open_global_cardinality_low_up.mzn: open_global_cardinality_low_up
- orth_link_ori_siz_end.mzn: orth_link_ori_siz_end
- orth_on_the_ground.mzn: orth_on_the_ground
- path_from_to.mzn: path_from_to, find a path from FROM to TO in a graph (incidence matrix)
- period.mzn: period (a sequence must have a period of a specific length)
- my_precedence.mzn: precedence (the first time we use j is before the first time we use k, for j < k)
- product_ctr.mzn: product_ctr
- range_ctr.mzn: range_ctr
- roots_test.mzn: Test of roots (defined in globals.mzn)
- same.mzn: same
- same_and_global_cardinality.mzn: same_and_global_cardinality
- same_and_global_cardinality_low_up.mzn: same_and_global_cardinality_low_up
- same_interval.mzn: same_interval
- same_modulo.mzn: same_modulo
- shift.mzn: shift
- sliding_sum.mzn: sliding_sum
- sliding_time_window.mzn: sliding_time_window
- sliding_time_window_from_start.mzn: sliding_time_window_from_start
- smooth.mzn: smooth
- soft_all_equal_ctr.mzn: soft_all_equal_ctr
- soft_same_var.mzn: soft_same_var
- sort_permutation.mzn: sort_permutation
- stretch_circuit.mzn: stretch_circuit
- stretch_path.mzn: stretch_path
- strictly_decreasing.mzn: strictly_decreasing. Also strictly_increasing and decreasing
- subsequence.mzn: subsequence
- subsequence_sum.mzn: subsequence sum
- sum_ctr.mzn: sum ctr
- sum_free.mzn: sum free, also: product_free
- sum_of_weights_of_distinct_values.mzn: sum_of_weights_of_distinct_values
- sum_set.mzn: sum set
- symmetric.mzn: symmetric
- symmetric_alldifferent.mzn: symmetric_alldifferent
- weighted_sum.mzn: weighted_sum (not in the catalogue)
Martin Chlond's Integer Programming Puzzles
Below are MiniZinc models of (almost) all puzzles of Martin Chlond's wonderful collections of Integer Programming Puzzles.
The collection is separated in four sections where the problems is presented
* Integer Programming Puzzles section 1
* Integer Programming Puzzles section 2
* Integer Programming Puzzles section 3
* Integer Programming Puzzles section 4
The models below are presented first with a link to MiniZinc page, and then to Martin Chlond's solution (in XPress Mosel, or for later solutions AMPL).
Problems from Integer Programming Puzzles section 1
Models:
Twelve draughts puzzle
(Chlond's solution)
Description : Twelve draughts puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P36)
Coin puzzle
(Chlond's solution)
Description : Coin puzzle
Source : Mathematical Puzzles of Sam Loyd (P111)
Egg basket puzzle
(Chlond's solution)
Description : Egg basket puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)
Evens puzzle
(Chlond's solution)
Description : Evens puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P8)
Fifty puzzle
(Chlond's solution)
Description : Fifty puzzle
Source : The Puzzles of Sam Loyd (P 54)
Honey division puzzle
(Chlond's solution)
Description : Honey division puzzle
Source : H E Dudeney - Amusements in Mathematics
Wine cask puzzle
(Chlond's solution)
Description : Wine cask puzzle
Source : M Kraitchik - Mathematical Recreations (p 31)
Knight domination puzzle - all squares threatened
(Chlond's solution)
Description : Knight domination puzzle - all squares threatened
Source : M Kraitchik - Mathematical Recreations (P256)
Mango puzzle
(Chlond's solution)
Description : Mango puzzle
Source : M Kraitchik - Mathematical Recreations (P32)
Remainder puzzle
(Chlond's solution)
Description : Remainder puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)
5 X 5 puzzle (alternative model: 5 X 5 puzzle v 2)
(Chlond's solution)
Description : 5 X 5 puzzle
Source : Unknown
Lights on puzzle
(Chlond's solution)
Description : Lights on puzzle
Source : Unknown
Problems from Integer Programming Puzzles section 2
Models:
Clarke's tobacconist
(Chlond's solution)
Description : Clarke's tobacconist
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.
Tommy's Birthday Coins
(Chlond's solution)
Description : Tommy's Birthday Coins
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.
Lewis Carroll coin puzzle
(Chlond's solution)
Description : Lewis Carroll coin puzzle
Source : Wakeling, E., (1995), Rediscovered Lewis Carroll Puzzles, Dover.
Dudeney's tea mixing problem
(Chlond's solution)
Description : Dudeney's tea mixing problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Jive turkeys
(Chlond's solution)
Description : Jive turkeys
Source : rec.puzzles
Public School Problem
(Chlond's solution)
Description : Public School Problem
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.
Dudeney's bishop placement problem I
(Chlond's solution)
Description : Dudeney's bishop placement problem I
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Dudeney's bishop placement problem II
(Chlond's solution)
Description : Dudeney's bishop placement problem II
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Kraitchik's queen placement problem
(Chlond's solution)
Description : Kraitchik's queen placement problem
Source : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.
Schuh's queen placement problem
(Chlond's solution)
Description : Schuh's queen placement problem
Source : Schuh, F., (1943), Wonderlijke Problemen;
Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.
Dudeney's queen placement problem
(Chlond's solution)
Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Joshua and his rats
(Chlond's solution)
Description : Joshua and his rats
Source : Sole, T., (1988), The Ticket to Heaven, Penguin Books
Problems from Integer Programming Puzzles section 3
Models:
The Abbott's Puzzle
(Chlond's solution)
Description : The Abbott's Puzzle
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
The Abbott's Window
(Chlond's solution)
Description : The Abbott's Window
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
The First Trial
(Chlond's solution)
Description : The First Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Second Trial
(Chlond's solution)
Description : The Second Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Third Trial
(Chlond's solution)
Description : The Third Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Fourth Trial
(Chlond's solution)
Description : The Fourth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Fifth Trial
(Chlond's solution)
Description : The Fifth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Sixth Trial
(Chlond's solution)
Description : The Sixth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
Werewolves II
(Chlond's solution)
Description : Werewolves II
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall
Werewolves IV
(Chlond's solution)
Description : Werewolves IV
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall
Earthlings
(Chlond's solution)
Description : Earthlings
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling
Equal Vision
(Chlond's solution)
Description : Equal Vision
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling
Problems from Integer Programming Puzzles section 4
Models:
On the road
(Chlond's solution)
Description : On the road
Source : Poniachik, J. & L, (1998), Hard-to-solve Brainteasers, Sterling
The Riddle of the Pilgrims
(Chlond's solution)
Description : The Riddle of the Pilgrims
Source : Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.
The Logical Labyrinth
(Chlond's solution)
Description : The Logical Labyrinth
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The gentle art of stamp-licking
(Chlond's solution)
Description : The gentle art of stamp-licking
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
The crowded board
(Chlond's solution)
Description : The crowded board
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Non-dominating queens problem
(Chlond's solution)
Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt
Enigma
(Chlond's solution)
Description : Enigma
Source : Herald Tribune circa November 1979 - courtesy of Dr Tito A. Ciriani
Price change puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations (p 33-35), Dover
Book buy puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover
Shopping puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover
Book discount problem
(Chlond's solution)
Source: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling
Seven 11 (Chlond's solution)
Source: alt.math.recreational
Models based on Martin Chlond's Puzzle articles in Informs Transations on Education
And here is some other models of recreational mathematics created by Martin Chlond, published in the Puzzle section of Informs Transations on Education (an open operations research journal).
Other models
Math, utils, etc.
Also, see my other pages about constraint programming systems:
* My Constraint Programming Blog, especially the MiniZinc category
* Constraint Programming
* My JaCoP page
* My Choco page
* My Gecode/R page
* My Comet page
* My Gecode page
* My ECLiPSe page
* My Tailor/Essence' page
* My SICStus Prolog page
Back to my homepage
Created by Hakan Kjellerstrand hakank@bonetmail.com