Overview

1. Balanced Incomplete Block Design (BIBD) (A)
2. Black Hole Patience (E)
3. Diet Problem (B)
4. Discrete Tomography (B)
5. Equidistant Frequency Permutation Arrays (EFPA) (E)
6. Farm Puzzle (B)
7. Futoshiki (A)
8. Golomb Ruler (B)
9. Grocery Puzzle (B)
10. Killer Sudoku (A)
11. Knapsack Problem (B)
12. Langford's Number Problem (A)
13. Magic Squares (B)
14. Map Colouring (B)
15. N-Queens Problem (B)
16. Peaceful Army of Queens (A)
17. Peg Solitaire (E)
18. Quasigroup Problem (A)
19. Send More Money Problem (B)
20. Sokoban (A)
21. SONET Problem (A)
22. Sportsscheduling (A)
23. Sudoku (B)

1. Balanced Incomplete Block Design (BIBD)

The BIBD problem is to assign v objects to b blocks such that such that each block contains k different objects, each object occurrs in exactly r different blocks and every 2 distinct objects occurr in exactly l blocks. We represent the problem by a vxb matrix of booleans, where matrix[i,j] equals 1(true) iff object i has been assign to block j. Below is the solution for the sample instance with v,b,k,r,l = 7,7,3,3,1.

    0, 0, 0, 0, 1, 1, 1
    0, 0, 1, 1, 0, 0, 1
    0, 1, 0, 1, 0, 1, 0
    0, 1, 1, 0, 1, 0, 0
    1, 0, 0, 1, 1, 0, 0
    1, 0, 1, 0, 0, 1, 0 
    1, 1, 0, 0, 0, 0, 1  

Here is the BIBD problem model together with some parameter instances: param1, param2, param3.

2. Black Hole Patience

Black Hole Solitaire is a (one-player) card game with the objective to place cards onto "the black hole", a centre stack. Starting from 17 stacks of 3 cards and the spades ace in the middle (the black hole), cards are put on top of the black hole. It will accept a card if its rank is one greater or one less than the rank of the card currently on top of it. The game is won when all cards from the stacks are placed onto the middle stack (the black hole).

The image above is taken from Lena Games and illustrates a sample initial configuration of Black Hole.

Here is a Black Hole Problem Model (based on this brilliant paper) and some parameter files: param1 and param2.

3. Diet Problem

The diet problem is a standard Operation Research example that is concerned with computing a particular diet (with respect to fat, sugar, calorie intake) with minimal cost (price). Here is an Essence' problem model and here is a parameter specification for computing a diet from a selection of four items (chocolate cake, chocolate icecream, coke and pineapple cheesecake).

4. Discrete Tomography

This is a little "tomography" problem, taken from an old issue of Scientific American: a matrix which contains zeroes and ones gets "x-rayed" vertically and horizontally, giving the total number of ones in each row and column. The problem is to reconstruct the contents of the matrix from this information. Sample run from Eclipse (http://eclipse.crosscoreop.com/examples/tomo.ecl.txt):

   ?- go.
      0 0 7 1 6 3 4 5 2 7 0 0
   0
   0
   8      * * * * * * * *
   2      *             *
   6      *   * * * *   *
   4      *   *     *   *
   5      *   *   * *   *
   3      *   *         *
   7      *   * * * * * *
   0
   0
 
 Eclipse solution by Joachim Schimpf, IC-Parc

5. Equidistant Frequency Permutation Arrays (EFPAs)

This example has been kindly provided by Ian Gent, Paul McKay, Ian Miguel, Peter Nightingale and Sophie Huczynska and stems from their joint paper Modelling Equidistant Frequency Permutation Arrays in Constraints.

Here is the problem model and here is a parameter file.

6. Farm Puzzle

This is a very simple puzzle: A farmer has 7 animals on his farm: pigs and hens. They all together have 22 legs. How many pigs and how many hens does the farmer have?

Here are two different models of the farmpuzzle: Farm Puzzle model 1 and Farm Puzzle model 2.

7. Futoshiki

Futoshiki is a japanese puzzle played on a square grid, where the objective is to place numbers 1..n in the grid so that every number occurs exactly once in each row and each column (like a latin square), while preserving inequalities that are set between cells of the grid. A sample futoshiki instances is given to the right, which is taken from this puzzle website. Here is the Futoshiki Problem Model and a parameter file.

8. Golomb Ruler

A Golomb Ruler is a ruler of minimal length with n ticks where the distances between all the ticks are different. The image to the right (from wikipedia) shows a sample golomb ruler of length 6 with 4 ticks. Here is an basic Golomb Ruler problem model and a parameter file.

9. Grocery Puzzle

A child goes to a shop and buys 4 items. When the cashier charges 7.11 Euro he notices that he accidently multiplied the prices of the items. So he adds up the prices and suprisingly he gets the same amount, 7.11 Euro. How much did each item cost?

Here is an Essence' Grocery problem model.

10. Killer Sudoku

A Killer Sudoku is a version of Sudoku extended with elements from Kakuro. The rules are the same as in Sudoku, with the additional rule that the sum of all numbers in extra cages (in the picture to the left the cages are depicted by colours) have to sum up to the number written into the cage. Here is an basic Killer Sudoku problem model and a parameter file.

11. Knapsack Problem

The knapsack problem is a combinatorial optimisation problem: given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items. (quoted from Wikipedia's entry on the knapsack problem).

12. Langford's Number Problem

We have a model of the Langford Number problem: arrange n sets of positive integers 1..k to a sequence, such that, following the first occurence of an integer i, each subsequent occurrence of i, appears i+1 indices later than the last. For example, for n=2, k=4, a solution would be 41312432.

We model this problem using a 1-dimensional array 'position' with length 2*k where the first k entries of the array hold the position of the i-th number, i.e. position[2] holds the position of the first occurrence of '2' in the sequence. In the sample solution for k=4, position[2] would hold the value '5', because '2' occurs first as 5th number in the sequence.
The second k entries in the array hold the second occurrence of each value in the sequence. Below we try to illustrate the relation between position and the sequence for the example with k=4.

sequence :   4 1 3 1 2 4 3 2

position    [2,5,3,1,4,8,7,6]   
of numbers   1 2 3 4 1 2 3 4 

Here is the simple Langford-2 problem model (for n=2) and general Langford-n problem model.

13. Magic Squares

An order n Magic Square is an n by n matrix containing the numbers 1 to n^2, where each row, column and main diagonal are equal to the same sum. The image to the right (from wikipedia) shows a sample magic square with n=3. Here is a Magic Square Problem Model and a parameter file.

14. Map Colouring Problem

Colour every contry on a map in such a way that no two adajacent countries have the same colour.

(image source: wikipedia)
Here is a problem instance: map_coloring.eprime.

15. N-Queens Problem

Place n queens on an nxn chessboard without attacking each other. A sample solution for n=8 is given in the picture.

We have two models of the n-queens problem: a standard n-Queens model and a more sophisticated n-Queens model.

16. Peaceful Army of Queens Problem

Place 2 equally-sized armies of queens (white and black) on a chess board without attacking each other and maximise the size of the armies. The picture to the right shows an example of two armies of queens (including a king on each side), where no queens of different colours can attack another. We model the problem by representing the board with an nxn matrix (2-dimensional array) that can take 3 values: 0,1 or 2. If a field is set to 0, it is not occupied, if a field is set to 1/2 it is occupied by a white/black queen. You can find the Peaceful Army of Queens problem model and a parameter file.

17. Peg Solitaire

Peg Solitaire is a (one-player) board game where pegs are arranged in holes, as shown in the picture (from wikipedia). In the English variant, the holes form a cross-like shape. In the initial setup, all holes are filled with pegs, except one. Then checkers-like moves are performed until there is only one peg left (that is positioned at the hole that was initially empty). We have 2 models of Peg Solitaire, that are both taken from this paper and that are further described in this paper. Here is the Peg Solitaire action-centric Model and Peg Solitaire state-centric Model, and some parameter files: param1,param2.

18. Quasigroup Existence Problems

A quasigroup is an mxm multiplication table of integers 1..m, where each element occurrs exactly once in each row and column and certain multiplication axioms hold. Depending on the multiplication axiom, the quaisgroup is enumerated (i.e. quasigroup3 denotes that mutliplication axiom 3 holds). We have models for several versions of the quasigroup existence problems:

1. Quasigroup3: QG3 idempotent model and QG3 non-idempotent model.
2. Quasigroup4: QG4 idempotent model and QG4 non-idempotent model.
3. Quasigroup5: GQ5 idempotent model and GQ5 non-idempotent model.
4. Quasigroup6: QG6 problem model.
5. Quasigroup7: QG7 problem model.

19. Send More Money

The Send More Money problem is concerned with finding a solution to the following sum where every letter stands for a distinct number between 0 and 9:

	     S E N D + 
	     M O R E
	   ----------
	   M O N E Y  
	    

20. Sokoban

Sokoban (Japanese for warehouse keeper) is a transport puzzle. that was invented by Hiroyuki Imabayashi, and published by Thinking Rabbit. The game is composed of a two dimensional warehouse laid out on a rectangular grid. An empty cell indicates a part of the warehouse floor where the sokoban, a porter, (red circle in the picture) can move freely. The walls constitute the boundaries of the warehouse. Some of the floor cells contain crates (yellow circles in the pictures). These crates are to be moved into designated target positions (squares in the pictures) by the porter. The number of target positions and the number of crates should be the same. The crates cannot be pulled and can be pushed only one at a time. Thus at a time, a cell may be empty, occupied by the sokoban or a crate, it can be a target position or a part of the warehouse wall. Here is the Sokoban Problem model. The image to the right shows a version of the Sokoban game and was taken from a Sokoban page from which we also took some problem samples: param1 (easy), param2 (medium). .

21. SONET Problem

The SONET problem is a network design problem: set up a network between n nodes, where only certain nodes require a connection. Nodes are connected by putting them on a ring, where all nodes on a ring can communicate. Putting a node on a ring requires a so-called ADM, and each ring has a capacity of nodes, i.e. ADMs. There is a certain amount of rings, r, that is available. The objective is to set up a network by using a minimal amount of ADMs.

The problem model has the amount of rings ('r'), amount of nodes('n'), the 'demand' (which nodes require communication) and node-capacity of each ring ('capacity_nodes') as parameters. The assignement of nodes to rings is modelled by a 2-dimensional matrix 'rings', indexed by the amnount of rings and nodes. The matrix-domain is boolean: If the node in column j is assigned to the ring in row i, then rings[i,j] = 1 and 0 otherwise. So all the '1's in the matrix 'rings' stand for an ADM. Hence the objective is to minimise the sum over all columns and rows of matrix 'rings'.

22. Sportsscheduling Problem

The sports scheduling problem is to schedule a sport competition with a certain amount of teams, weeks and periods such that teams play only once a week, every team plays at most twice a period and no game is repeated. This model is interesting for those who want to see how to use table constraints.

Here is the Sports Scheduling problem model and a parameter file.

23. Sudoku

Sudoku is a popular puzzle: assign each field of the 9x9 board a number between (1..9) such that every row, column and 3x3 box contains different numbers. A sample sudoku puzzle is given on the left. The Sudoku problem model and a parameter file.