### Some new Answer Set Programming Programs

Here are some new Answer Set Programming (ASP) programs not mentioned before.
They are in about the order they where implemented. All of them are
also at my Answer Set Programming page.

Other implementations: Almost all of these problem have been implemented earlier in a couple of CP systems, but instead of linking to all of these individually, I have linked to the problem entry at my Common constraint programming problems. That page contains all of the problems that have been implemented in at least two different CP systems (242 as of writing), and now also contains my ASP programs (83 right now). There are 59 problems which has been been implemented in at least 6 systems. (4 problems has been implemented in all 12 systems:(Survo Puzzle, Seseman, Quasigroup Completion, and Coins Grid).

From Uwe Hoffmann's Finding celebrities at a party (PDF):

In summary: Find some distinct clique where everyone known a celebrity, and all celebrities only know all other celebrities.

Here's the code:

Solution:

building_blocks2.lp: faster version

From Brown Buffalo logic puzzle collection (with implementations in Prolog): BuildingBlocksClues:

The second version, building_blocks2.lp, use another representation, where the words instead are defined as

Or shorter as

Now we can encode the problem as:

Performance: This version is much faster than the first approach. Generating all 24 solution now takes 10 seconds (which essentially is the grounding time).

But it's still slow: all the CP implementations generates all solutions well under one second.

See other implementations

From Jim Orlin's Colored letters, labeled dice: a logic puzzle:

See other implementations

In A first look at Answer Set Programming I complained that Clingo was very slow on these kind of alphametic puzzles (the reason was the grounding time). However, when

Project Euler problem 1:

Note that the two

Project Euler problem 2 involving Fibonacci numbers.

The predicate

This is small excursion in number theory. Unfortunately gringo don't support arbitrary precision, and the grounding takes long time so this is usable only for small(ish) numbers.

Some definition of primes:

This translates quite well in ASP, where the set notation (

Another way of defining prime numbers:

From "The ECLiPSe Book" pages 99f and 234 ff (the ECLiPSe encoding is at page 236.).

See other implementations

From Math World SetCoveringDeployment:

The solution found is the following:

(There are 6 optimal solutions of this problem.)

See other implementations

From Wikipedia Sicherman_dice:

And it shows the two solutions mentioned above.

See other implementations

Problem formulation taken from Koalog (could not find the exact page now)

Problem 1.4 from the book "Problem Solving Through Recreational Mathematics" by Averbach and Chein.

The integrity constraint means that we remove all the solutions that contains the stated condition (hence the

See other implementations

Scheduling of 6 speakers in 6 slots. From Rina Dechter, Constraint Processing, page 72.

See other implementations

This is a small problem from the CSPLib where the object is to find different combinations of lights for cars and pedestrians.

See other implementations

This is a small problem I found the other day at the site for the logic programming system Hansei (in ML):

From Wikipedia: Zebra_Puzzle

See other implementations

Wikipedia: KenKen

Here are some of constraints for handling 2 parameter hints.

See other implementations

I wrote about this grid problem last August in Nontransitive dice, Ormat game, 17x17 challenge.

This ASP encoding solves 14x14 quite fast (< 1 second) using the following parameters:

with these statistics:

Kakuro is yet another grid puzzle. From Wikipedia: Kakuro:

See other implementations

See Wikipedia: Young_tableau:

The five partitions of 4 are

The corresponding standard Young tableaux are:

See other implementations

From the Gecode example crew:

See other implementations

sudoku_pi_gcc.lp: with "occurrence count"

Via 360's: Pi Day Sudoku 2009:

This was quite easy to encode but very time consuming to convert all the 12 regions to predicates. The cardinality constraints ("exact 3 occurrences of Pi") is encoded quite directly in ASP.

However, I miss the generality of the global constraint

Both versions solve the problem in about 0.04 seconds but have slightly different number of choices and conflicts:

sudoku_pi.lp: 7 choices, 2 conflicts, 0 restarts

sudoku_pi_gcc.lp: 39 choices, 12 conflicts, 0 restarts

This implements the Steiner triplet problem. Formulation from BProlog

I'm not really happy with this encoding. It could probably be done in a more neater way since modeling set constraints is quite natural in ASP. Also, I have not found a way of encode a good symmetry breaking to ensure that the sets are in increasing order.

Here are some statistics for clingo for generating 1 solution with default parameters:

See other implementations

Other implementations: Almost all of these problem have been implemented earlier in a couple of CP systems, but instead of linking to all of these individually, I have linked to the problem entry at my Common constraint programming problems. That page contains all of the problems that have been implemented in at least two different CP systems (242 as of writing), and now also contains my ASP programs (83 right now). There are 59 problems which has been been implemented in at least 6 systems. (4 problems has been implemented in all 12 systems:(Survo Puzzle, Seseman, Quasigroup Completion, and Coins Grid).

### Finding celebrities

Encoding: finding_celebrities.lpFrom Uwe Hoffmann's Finding celebrities at a party (PDF):

Problem: Given a list of people at a party and for each person the list of people they know at the party, we want to find the celebrities at the party. A celebrity is a person that everybody at the party knows but that only knows other celebrities. At least one celebrity is present at the party.(The paper includes an implementation in Scala.)

In summary: Find some distinct clique where everyone known a celebrity, and all celebrities only know all other celebrities.

Here's the code:

```
knows(adam, dan;alice;peter;eva).
```

knows(dan, adam;alice;peter).

knows(eva, alice;peter).

knows(alice, peter).

knows(peter, alice).

person(X) :- knows(X, _).

num_p(N) :- N = #sum [person(P) ].

% 1) a person is a celebrity if everyone

% knows P

celebrity(C) :-

person(C),

num_p(N),

N-1 { knows(P, C) : person(P) } N-1.

% 2) and the celebrities only know other

% celebrities, i.e.

% C is not a celebrity if he/she

% knows anyone that is not a celebrity)

:- celebrity(C), person(C), not celebrity(P), knows(C, P).

Solution:

celebrity(alice) celebrity(peter)See other implementations

### Building blocks

Encodings: building_blocks.lpbuilding_blocks2.lp: faster version

From Brown Buffalo logic puzzle collection (with implementations in Prolog): BuildingBlocksClues:

Each of four alphabet blocks has a single letter of the alphabet on each of its six sides. In all, the four blocks contain every letter but Q and Z. By arranging the blocks in various ways, you can spell all of the words listed below. Can you figure out how the letters are arranged on the four blocks?This was quite easy to implement. However, here - as well as in some other ASP encodings - I really miss the global constraint

BAKE ONYX ECHO OVAL

GIRD SMUG JUMP TORN

LUCK VINY LUSH WRAP

`alldifferent`

that is so convenient in constraint programming systems. Here is my first version of ensuring that the letters of a word (`L1, L2, L3, L4`

) should be on a different die. The words are represented as `word(b,a,k,e).`

.
% the letters of each word must be on % difference dice diff(L1,L2,L3,L4) :- letters(L1;L2;L3;L4), d(D1;D2;D3;D4), letter(L1,D1), letter(L2,D2), letter(L3,D3), letter(L4,D4), % explicitly state the diffs D1 != D2, D1 != D3, D1 != D4, D2 != D3, D2 != D4, D3 != D4. :- not diff(L1,L2,L3,L4), word(L1,L2,L3,L4).Performance: It takes 1 minute and 10 seconds for gringo/clasp to generate all 24 solutions. The grounding takes much of this time: 30 seconds.

The second version, building_blocks2.lp, use another representation, where the words instead are defined as

```
word(1, b).
```

word(1, a).

word(1, k).

word(1, e).

% ...

Or shorter as

`word(1, b;a;k;e).`

.Now we can encode the problem as:

```
words(1..12).
```

letters(a;b;c;d;e;f;g;h;i;j;k;l;m;n;o;p;r;s;t;u;v;w;x;y).

d(1..4).

1 { letter(Letter, Dice) : d(Dice) } 1 :- letters(Letter).

6 { letter(Letter, Dice) : letters(Letter) } 6 :- d(Dice).

:- words(W),

word(W, L1),

word(W, L2),

L1 < L2,

letter(L1,D1),

letter(L2,D2),

D1==D2.

Performance: This version is much faster than the first approach. Generating all 24 solution now takes 10 seconds (which essentially is the grounding time).

But it's still slow: all the CP implementations generates all solutions well under one second.

See other implementations

### Labeled dice

Encoding: labeled_dice.lpFrom Jim Orlin's Colored letters, labeled dice: a logic puzzle:

My daughter Jenn bough a puzzle book, and showed me a cute puzzle. There are 13 words as follows: BUOY, CAVE, CELT, FLUB, FORK, HEMP, JUDY, JUNK, LIMN, QUIP, SWAG, VISA, WISH.The encoding is very similar to the building blocks problem (see above)

There are 24 different letters that appear in the 13 words. The question is: can one assign the 24 letters to 4 different cubes so that the four letters of each word appears on different cubes. (There is one letter from each word on each cube.) It might be fun for you to try it. I'll give a small hint at the end of this post. The puzzle was created by Humphrey Dudley.

See other implementations

### SEND+MORE=MONEY, variant with fixed M

Encoding: send_more_money_b.lpIn A first look at Answer Set Programming I complained that Clingo was very slow on these kind of alphametic puzzles (the reason was the grounding time). However, when

`M`

is fixed to the value 1 it takes just 5 seconds to solve it, in comparison to 45 seconds when M is "free" (i.e. just > 0).
### Project Euler problem 1

Encoding: euler1.lpProject Euler problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.Here is the complete model.

```
#const n=1000.
```

number(1..n).

mod_test(N) :- number(N), N #mod 3 == 0.

mod_test(N) :- number(N), N #mod 5 == 0.

total(Sum) :- Sum = #sum [mod_test(N) : number(N) : N < n = N].

#hide.

#show total(Sum).

Note that the two

`mod_test`

predicates are to be seend as **or**, i.e. either multiple of 3 or multiple of 5.### Project Euler problem 2

Encoding: euler2.lpProject Euler problem 2 involving Fibonacci numbers.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all the even-valued terms in the sequence which do not exceed four million.

```
#const n=45. % max value of N
```

#const limit = 4000000.

number(1..n).

fib(0, 1).

fib(1, 1).

fib(N, X1 + X2) :- number(N), N > 1, fib(N - 1, X1), fib(N - 2, X2).

total(Sum) :- Sum = #sum [fib(N, Res) : Res < limit : Res #mod 2 == 0 = Res].

The predicate

`total(Sum)`

contains the answer.
### Prime numbers, small excursion in number theory

Encoding: prime_number.lpThis is small excursion in number theory. Unfortunately gringo don't support arbitrary precision, and the grounding takes long time so this is usable only for small(ish) numbers.

Some definition of primes:

*A number N is a prime number if there is no number I: 2..N / 2 such that N % I == 0.*This translates quite well in ASP, where the set notation (

`{ ... } 0`

) mean that
the set should be empty, i.e. the cardinality of the set is 0.
```
prime(N) :-
number(N),
N > 1,
{ number(I) : I > 1 : I < 1+(N #div 2) : N #mod I == 0} 0.
```

Another way of defining prime numbers:

*A number N ( > 1) is a prime number if it has no divisors.*```
divisor(N, I) :- number(I), I > 1, I < 1+(N #div 2), N #mod I == 0, number(N), N > 1.
```

prime2(N) :- number(N), N > 1, {divisor(N,I) : number(I) } 0.

### A Coin problem

Encoding: coins3.lpFrom "The ECLiPSe Book" pages 99f and 234 ff (the ECLiPSe encoding is at page 236.).

What is the minimum number of coins that allows one to pay _exactly_ any amount smaller than one Euro? Recall that there are six different euro cents, of denomination 1, 2, 5, 10, 20, 50This was harder than I first thought, and was on the wrong track at first. The solution I settled on was to define

`x(Coin, N)`

so that N is the maximum value for the N in `y`

(the "matrix" for all combinations of values).
```
#const max_val = 99.
```

#const max_amount = 5.

coins(1;2;5;10;25;50).

val(1..max_val). % total

amount(0..max_amount). % max amount per coin

% ensure that all number 1..max_val

% are summed in some way

Value #sum [y(Value, Coin, N) : coins(Coin) : N*Coin <= Value : amount(N) = N*Coin] Value :- val(Value).

% x(Coin, N):

% for each coins Coin, N is the maximum value

% in all y's for this Coin

x(Coin, N) :-

coins(Coin),

amount(N),

N = #max[y(Value, Coin, N2) : val(Value) : amount(N2) = N2].

total(Total) :- Total = #sum [x(Coin, N) = N].

% Object: Minimize the total number of coins.

#minimize [x(Value, N) = N].

See other implementations

### Set Covering Deployment

Encoding: set_covering_deployment.lpFrom Math World SetCoveringDeployment:

Set covering deployment (sometimes written "set-covering deployment" and abbreviated SCDP for "set covering deployment problem") seeks an optimal stationing of troops in a set of regions so that a relatively small number of troop units can control a large geographic region. ReVelle and Rosing (2000) first described this in a study of Emperor Constantine the Great's mobile field army placements to secure the Roman Empire.Here is my encoding, except for the matrix of neighbour regions (in

`matrix(Region1, Region2)`

:
```
#const n=8. % number of cities
```

cities(1..n).

army(0..1).

% unique indices of the cities

1 { x(City, Army1, Army2) : army(Army1;Army2) } 1 :- cities(City).

% Constraint 1: There is always an army in a city (+ maybe a backup)

% Or rather: Is there is a backup, there must be an an army

:- x(City, Army1, Army2), Army1 < Army2.

% Constraint 2: There should always be an backup army near every city

:- x(City, Army11, Army12), S = #sum[ x(City2, Army21, Army22) : matrix(City, City2) = Army22], Army11 + S < 1.

% show the selected cities with name

selected(City, Name, Army1, Army2) :- x(City, Army1, Army2), Army1 > 0, name(City, Name).

#minimize [x(City, Army1, Army2) = Army1 + Army2].

The solution found is the following:

selected(3,britain,1,1) selected(1,alexandria,1,1)which means that we should place one army and one reserv in each britain and alexandria.

(There are 6 optimal solutions of this problem.)

See other implementations

### Sicherman Dice

Encoding: sicherman_dice.lpFrom Wikipedia Sicherman_dice:

Sicherman dice are the only pair of 6-sided dice which are not normal dice, bear only positive integers, and have the same probability distribution for the sum as normal dice.

The faces on the dice are numbered 1, 2, 2, 3, 3, 4 and 1, 3, 4, 5, 6, 8.

```
#const n = 6. % number of side per die
```

#const m = 10. % max integer on a die

#const start = 1. % start value (set to 0 for the extra two solutions)

% standard distribution of 2 dice

dist(2, 1). dist(3, 2). dist(4, 3).

dist(5, 4). dist(6, 5). dist(7, 6).

dist(8, 5). dist(9, 4). dist(10,3).

dist(11,2). dist(12,1).

sides(1..n).

values(start..m).

dists(2..12).

dist_sums(S) :- dist(_, S).

1 { d1(Side, Value) : values(Value) } 1 :- sides(Side).

1 { d2(Side, Value) : values(Value) } 1 :- sides(Side).

% combine the dice so we can #sum over them

comb(S1,V1,S2,V2) :- d1(S1,V1), d2(S2,V2).

1 { comb(S1,V1,S2,V2) : values(V1;V2) } 1 :- sides(S1;S2).

% symmetry breaking

:- d1(S1a,V1a), d1(S1b,V1b), S1a < S1b, V1a > V1b.

:- d2(S2a,V2a), d2(S2b,V2b), S2a < S2b, V2a > V2b.

:- d1(S,V1),d2(S,V2), V1 > V2.

Sum #sum [ comb(S1, V1, S2, V2) : sides(S1;S2) : values(V1;V2) : V1+V2 == K] Sum :- dist(K, Sum).

#hide.

#show d1(Side, Value).

#show d2(Side, Value).

And it shows the two solutions mentioned above.

See other implementations

### Set Partition

Encoding: set_partition.lpProblem formulation taken from Koalog (could not find the exact page now)

This is a partition problem.See other implementations

Given the set S = {1, 2, ..., n},

it consists in finding two sets A and B such that:

- A U B = S

- |A| = |B|

- sum(A) = sum(B)

- sum_squares(A) = sum_squares(B)

### Averbach problem 1.4

Encoding: averbach_1.4.lpProblem 1.4 from the book "Problem Solving Through Recreational Mathematics" by Averbach and Chein.

Messr Baker, Dyer, Farmer, Glover, and Hosier are seated around a circular table, playing poker. Each gentleman is the namesake of the profession of one of the others.This is one of my standard problem for testing the modulo operator (

The dyer is seated two places to the left of Mr Hosier.

The baker sits two places to Mr Baker's right.

The farmer is seated to the left of Mr Farmer.

Mr Dyer is on the glover's right.

What is the name of the dyer?

`#mod`

in Clingo). The constraint *The dyer is seated two places to the left of Mr Hosier.*(which may be stated as`dyer = (Hosier - 2) mod 5`

in, say, MiniZinc) is
translated into:
```
:- x(_, p_dyer, P1), x(n_hosier, _, P2), P1 != (P2 - 2) #mod 5.
```

The integrity constraint means that we remove all the solutions that contains the stated condition (hence the

`!=`

). Sometimes it's confusing
to state the constraint in this manner; on the other hand sometimes it's very convenient.
See other implementations

### Scheduling speakers

Encoding: scheduling_speakers.lpScheduling of 6 speakers in 6 slots. From Rina Dechter, Constraint Processing, page 72.

See other implementations

### Traffic lights problem, CSPLib #16

Encoding: traffic_lights.lpThis is a small problem from the CSPLib where the object is to find different combinations of lights for cars and pedestrians.

See other implementations

### Daily schedule, small scheduling problem

Encoding: daily_schedule.lpThis is a small problem I found the other day at the site for the logic programming system Hansei (in ML):

Solving the logical puzzle (scheduling problem) posed by Mikael More on October 25, 2010:It is as direct as possible:

For the daily schedule for Monday to Wednesday:

One of the days I'll shop.

One of the days I'll take a walk.

One of the days I'll go to the barber.

One of the days I'll go to the supermarket.

The same day as I go to the supermarket, I'll shop.

The same day as I take a walk I'll go to the barber.

I'll go to the supermarket the day before the day I'll take a walk.

I'll take a walk Tuesday.

Which are all possible daily schedules, regarding those four events?

...

That is, on Monday I go to the supermarket and shop, on Tuesday I walk and take a haircut. There is only one schedule satisfying the constraints.

```
days(monday;tuesday;wednesday).
```

actions(shop;walk;barber;supermarket).

% an action is done exactly once

1 { x(Day, Action) : days(Day) } 1 :- actions(Action).

% The same day as I go to the supermarket, I'll shop.

:- x(Day1, supermarket), x(Day2, shop), Day1 != Day2.

% The same day as I take a walk I'll go to the barber.

:- x(Day1, walk), x(Day2, barber), Day1 != Day2.

% I'll go to the supermarket the day before the day I'll take a walk.

:- x(Day1, supermarket), x(Day2, walk), Day1 >= Day2.

% I'll take a walk Tuesday.

x(tuesday, walk).

### Zebra problem

Encoding: zebra.lpFrom Wikipedia: Zebra_Puzzle

1. There are five houses.The complete code:

2. The Englishman lives in the red house.

3. The Spaniard owns the dog.

4. Coffee is drunk in the green house.

5. The Ukrainian drinks tea.

6. The green house is immediately to the right of the ivory house.

7. The Old Gold smoker owns snails.

8. Kools are smoked in the yellow house.

9. Milk is drunk in the middle house.

10. The Norwegian lives in the first house.

11. The man who smokes Chesterfields lives in the house next to the man with the fox.

12. Kools are smoked in the house next to the house where the horse

is kept. (should be ".. a house ...", see Discussion section)

13. The Lucky Strike smoker drinks orange juice.

14. The Japanese smokes Parliaments.

15. The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.

```
% domains
```

colors(red;green;ivory;yellow;blue).

nationalities(english;spaniard;ukrainian;norwegian;japanese).

animals(dog;fox;horse;zebra;snails).

drinks(coffee;tea;milk;orange_juice;water).

cigarettes(old_gold;kools;chesterfields;lucky_strike;parliaments).

% 1. There are five houses.

houses(1..5).

% alldifferents

1 { color(House, Color) : colors(Color) } 1 :- houses(House).

1 { color(House, Color) : houses(House) } 1 :- colors(Color).

1 { nationality(House, Nationality) : nationalities(Nationality) } 1 :- houses(House).

1 { nationality(House, Nationality) : houses(House) } 1 :- nationalities(Nationality).

1 { animal(House, Animal) : animals(Animal) } 1 :- houses(House).

1 { animal(House, Animal) : houses(House) } 1 :- animals(Animal).

1 { drink(House, Drink) : drinks(Drink) } 1 :- houses(House).

1 { drink(House, Drink) : houses(House) } 1 :- drinks(Drink).

1 { smoke(House, Cigarette) : cigarettes(Cigarette) } 1 :- houses(House).

1 { smoke(House, Cigarette) : houses(House) } 1 :- cigarettes(Cigarette).

next_to(H1,H2) :- houses(H1;H2), |H1-H2| == 1.

% 2. The Englishman lives in the red house.

:- color(H1, red), nationality(H2, english), H1 != H2.

% 3. The Spaniard owns the dog.

:- nationality(H1, spaniard), animal(H2,dog), H1 != H2.

% 4. Coffee is drunk in the green house.

:- color(H1, green), drink(H2, coffee), H1 != H2.

% 5. The Ukrainian drinks tea.

:- nationality(H1, ukrainian), drink(H2, tea), H1 != H2.

% 6. The green house is immediately to the right of the ivory house.

:- color(H1, green), color(H2, ivory), H1 != H2 + 1.

% 7. The Old Gold smoker owns snails.

:- smoke(H1,old_gold), animal(H2, snails), H1 != H2.

% 8. Kools are smoked in the yellow house.

:- smoke(H1, kools), color(H2, yellow), H1 != H2

.

% 9. Milk is drunk in the middle house.

:- not drink(3, milk).

% 10. The Norwegian lives in the first house.

:- not nationality(1,norwegian).

% 11. The man who smokes Chesterfields lives in the house next to the man with the fox.

:- smoke(H1, chesterfields), animal(H2, fox), not next_to(H1,H2).

% 12. Kools are smoked in the house next to the house where the horse

% is kept. (should be ".. a house ...", see Discussion section)

:- smoke(H1, kools), animal(H2, horse), not next_to(H1,H2).

% 13. The Lucky Strike smoker drinks orange juice.

:- smoke(H1, lucky_strike), drink(H2, orange_juice), H1 != H2.

% 14. The Japanese smokes Parliaments.

:- nationality(H1, japanese), smoke(H2, parliaments), H1 != H2.

% 15. The Norwegian lives next to the blue house.

:- nationality(H1, norwegian), color(H2, blue), not next_to(H1, H2).

has_zebra(Nationality) :- nationality(House, Nationality), animal(House, zebra).

drinks_water(Nationality) :- nationality(House, Nationality), drink(House,water).

% for output:

house(House, Color, Nationality, Animal, Drink, Cigarette) :-

houses(House),

color(House, Color),

nationality(House, Nationality),

animal(House, Animal),

drink(House, Drink),

smoke(House, Cigarette).

See other implementations

### KenKen

Encoding: kenken2.lpWikipedia: KenKen

KenKen or KEN-KEN is a style of arithmetic and logical puzzle sharing several characteristics with sudoku. The name comes from Japanese and is translated as "square wisdom" or "cleverness squared".It took a while to get both principal representation and then the conditions correct. The hints are represented with the operators explicitly stated:

...

The objective is to fill the grid in with the digits 1 through 6 such that:

* Each row contains exactly one of each digit

* Each column contains exactly one of each digit

* Each bold-outlined group of cells is a cage containing digits which

achieve the specified result using the specified mathematical operation:

addition (+),

subtraction (-),

multiplication (x),

and division (/).

(Unlike in Killer sudoku, digits may repeat within a group.)

...

More complex KenKen problems are formed using the principles described above but omitting the symbols +, -, x and/, thus leaving them as yet another unknown to be determined.

```
p("+", 11, 1,1, 2,1).
```

p("/", 2, 1,2, 1,3).

...

Here are some of constraints for handling 2 parameter hints.

```
% 2 arguments
```

:- p("+", Res, X1,X2, Y1,Y2), x(X1,X2, A), x(Y1,Y2, B), A+B != Res.

:- p("*", Res, X1,X2, Y1,Y2), x(X1,X2, A), x(Y1,Y2, B), A*B != Res.

...

See other implementations

### 17x17 grid problem

Encoding: 17.lpI wrote about this grid problem last August in Nontransitive dice, Ormat game, 17x17 challenge.

This ASP encoding solves 14x14 quite fast (< 1 second) using the following parameters:

```
clingo -c num_rows=14 -c num_cols=14 --stat --heuristic=Vsids --restarts=2000,1.5 --shuffle=1,1 17.lp
```

with these statistics:

Time : 0.470 Prepare : 0.220 Prepro. : 0.050 Solving : 0.200 Choices : 5276 Conflicts : 3881 Restarts : 1However, for larger values (n = 15..16) and experimenting with different solve parameters, I have had no luck.

### Kakuro

Encoding: kakuro.lpKakuro is yet another grid puzzle. From Wikipedia: Kakuro:

The object of the puzzle is to insert a digit from 1 to 9 inclusive into each white cell such that the sum of the numbers in each entry matches the clue associated with it and that no digit is duplicated in any entry. It is that lack of duplication that makes creating Kakuro puzzles with unique solutions possible, and which means solving a Kakuro puzzle involves investigating combinations more, compared to Sudoku in which the focus is on permutations. There is an unwritten rule for making Kakuro puzzles that each clue must have at least two numbers that add up to it. This is because including one number is mathematically trivial when solving Kakuro puzzles; one can simply disregard the number entirely and subtract it from the clue it indicates.The encoding is quite fast, solves the problem instance in 0.090s. However, it isn't very general since it only supports clues of length 2..5. Also, it's a tedious job stating the alldifferent constraint for the different arguments.

See other implementations

### Young Tableaux and partition

Encoding: young_tableaux.lpSee Wikipedia: Young_tableau:

A Young diagram (also called Ferrers diagram, particularly when represented using dots) is a finite collection of boxes, or cells, arranged in left-justified rows, with the row lengths weakly decreasing (each row has the same or shorter length than its predecessor).Also see MathWorld: YoungTableau.

The five partitions of 4 are

```
{4}, {3,1}, {2,2}, {2,1,1}, {1,1,1,1}
```

The corresponding standard Young tableaux are:

1. 1 2 3 4 2. 1 2 3 1 2 4 1 3 4 4 3 2 3. 1 2 1 3 3 4 2 4 4 1 2 1 3 1 4 3 2 2 4 4 3 5. 1 2 3 4I thought this should be quite complicated to implement my standard approach of this in ASP. But actually it was quite easy to translate from the MiniZinc model:

See other implementations

### Airline crew allocation

Encoding: crew.lpFrom the Gecode example crew:

Example: Airline crew allocation Assign 20 flight attendants to 10 flights. Each flight needs a certain number of cabin crew, and they have to speak certain languages. Every cabin crew member has two flights off after an attended flight.This encoding solves the problem very fast for a schedule all 20 flight attendants, which is the object. However, if we regard it as an optimization problem where the object is to minimize the number of person filling the schedule (i.e. 19), it takes "forever". It finds 19 very fast, but to prove it takes very long (as do many CP system).

See other implementations

### Pi Day Sudoku 2009

Encodings: sudoku_pi.lpsudoku_pi_gcc.lp: with "occurrence count"

Via 360's: Pi Day Sudoku 2009:

Each row, column, and region contains the digits 1-9 exactly once plus three [Pi] symbols. There's a printable .pdf file hereAlso see BrainFrees Puzzles: Pi Day 2009.

This was quite easy to encode but very time consuming to convert all the 12 regions to predicates. The cardinality constraints ("exact 3 occurrences of Pi") is encoded quite directly in ASP.

```
#const n=12.
```

% domains

rows(1..n).

cols(1..n).

val(1;2;3;4;5;6;7;8;9;p).

val1_9(1..9).

regions(Region) :- region(Region, _, _).

% unique index

1 { x(Row, Col, Val) : val(Val) } 1 :- rows(Row), cols(Col).

% assign hints

x(Row, Col, Val) :- hint(Row, Col, Val).

% all different 1..9

1 { x(Row, Col, Val) : rows(Row) } 1 :- val1_9(Val), cols(Col).

1 { x(Row, Col, Val) : cols(Col) } 1 :- val1_9(Val), rows(Row).

% 3 occurrences of pi per row and column

3 { x(Row, Col, p) : cols(Col) } 3 :- rows(Row).

3 { x(Row, Col, p) : rows(Row) } 3 :- cols(Col).

% handle the regions

% all different for 1..9 in regions

1 { x(Row, Col, Val) : region(Region, Row, Col) } 1 :- regions(Region), val1_9(Val).

% 3 occurrences of pi in the regions

3 { x(Row, Col, p) : region(Region, Row, Col) } 3 :- regions(Region).

However, I miss the generality of the global constraint

`global cardinality count`

, and did implement (in sudoku_pi_gcc.lp) some sort of ersatz which handles both the 1 and 3 counts (by the value `Occ`

for each value `occ(Val, Occ)`

instead of stating them separately:
```
% occ(Number, Occurrences).
```

occ(1;2;3;4;5;6;7;8;9, 1).

occ(p, 3).

% ..

.

% rows and columns

Occ { x(Row, Col, Val) : rows(Row) } Occ :- val1_9(Val), cols(Col), occ(Val, Occ).

Occ { x(Row, Col, Val) : cols(Col) } Occ :- val1_9(Val), rows(Row), occ(Val, Occ).

% handle the regions

Occ { x(Row, Col, Val) : region(Region, Row, Col) } Occ :- regions(Region), val1_9(Val), occ(Val, Occ).

Both versions solve the problem in about 0.04 seconds but have slightly different number of choices and conflicts:

sudoku_pi.lp: 7 choices, 2 conflicts, 0 restarts

sudoku_pi_gcc.lp: 39 choices, 12 conflicts, 0 restarts

### Steiner triplets

Encoding: steiner.lpThis implements the Steiner triplet problem. Formulation from BProlog

The ternary Steiner problem of order n is to find n(n-1)/6 sets of elements in {1,2,...,n} such that each set contains three elements and any two sets have at most one element in common.Also see MathWorld SteinerTripleSystem.

For example, the following shows a solution for size n=7:

{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}

Problem taken from:

C. Gervet: Interval Propagation to Reason about Sets: Definition and Implementation of a PracticalLanguage, Constraints, An International Journal, vol.1, pp.191-246, 1997.

I'm not really happy with this encoding. It could probably be done in a more neater way since modeling set constraints is quite natural in ASP. Also, I have not found a way of encode a good symmetry breaking to ensure that the sets are in increasing order.

```
#const n = 7.
```

#const nb = n * (n-1) #div 6.

% domain

val(1..n).

sets(1..nb).

0 { x(Set, Val) } 1 :- sets(Set), val(Val).

% 3 values of each set

3 { x(Set, Val) : val(Val) } 3 :- sets(Set).

% count the number of common occurrences of each pair of Sets

check(Set1, Set2, Val, N) :-

sets(Set1;Set2),

Set1 < Set2,

val(Val),

N = #count { x(Set1,Val), x(Set2,Val) }.

% ensure that there are at most 1 occurrence

% with the same value (i.e. N=2) for any two sets.

:- sets(Set1;Set2), Set1 < Set2, 2 #sum[check(Set1, Set2, Val, N) : N == 2 ].

Here are some statistics for clingo for generating 1 solution with default parameters:

n time Choices Conflicts Restarts -------------------------------------- 7 0.01s 183 116 1 9 0.02s 412 136 1 13 0.33s 6269 2385 6 15 2.35s 22801 13755 10 19 > 2hWith

`--restarts=10,2.5`

it's a bit faster, but not much.
7 0.01s 57 20 1 9 0.03s 833 329 4 13 0.32s 6516 2387 6 15 0.46s 6744 1134 5 19 ?

See other implementations