PK hrS}xr 7 EssencePrime/prob001/carSequencing/carSequencing.eprimelanguage ESSENCE' 1.0
given numcars : int(1..)
given numclasses : int(1..)
given numoptions : int(1..)
given optMax : matrix indexed by [ int(1..numoptions) ] of int(0..)
given windowSize : matrix indexed by [ int(1..numoptions) ] of int(0..)
given optionsRequired : matrix indexed by [ int(1..numclasses), int(1..numoptions) ] of bool
given numberPerClass : matrix indexed by [ int(1..numclasses) ] of int(1..)
$ Decision variables
find seq: matrix indexed by [ int(1..numcars) ] of int(1..numclasses)
such that
forAll option : int(1..numoptions) .
forAll windowStart : int(1..numcars-windowSize[option]+1) .
(sum pos : int(windowStart..windowStart+windowSize[option]-1) .
seq[pos] in toSet([ class | class : int(1..numclasses), optionsRequired[class, option]])
)<=optMax[option],
forAll option : int(1..numoptions) .
(sum pos : int(1..numcars) .
seq[pos] in toSet([ class | class : int(1..numclasses), optionsRequired[class, option]])
)=
(
sum class : int(1..numclasses) . optionsRequired[class, option]*numberPerClass[class]
),
gcc(seq, [ i | i : int(1..numclasses)], numberPerClass)
PK hrS@fO 5 EssencePrime/prob007/all_interval/all_interval.eprime$
$ All interval problem in Essence'.
$
$
$ CSPLib problem number 7
$ http://www.csplib.org/Problems/prob007
$ """
$ Given the twelve standard pitch-classes (c, c$, d, ...), represented by
$ numbers 0,1,...,11, find a series in which each pitch-class occurs exactly
$ once and in which the musical intervals between neighbouring notes cover
$ the full set of intervals from the minor second (1 semitone) to the major
$ seventh (11 semitones). That is, for each of the intervals, there is a
$ pair of neigbhouring pitch-classes in the series, between which this
$ interval appears. The problem of finding such a series can be easily
$ formulated as an instance of a more general arithmetic problem on Z_n,
$ the set of integer residues modulo n. Given n in N, find a vector
$ s = (s_1, ..., s_n), such that (i) s is a permutation of
$ Z_n = {0,1,...,n-1}; and (ii) the interval vector
$ v = (|s_2-s_1|, |s_3-s_2|, ... |s_n-s_{n-1}|) is a permutation of
$ Z_n-{0} = {1,2,...,n-1}. A vector v satisfying these conditions is
$ called an all-interval series of size n; the problem of finding such
$ a series is the all-interval series problem of size n. We may also be
$ interested in finding all possible series of a given size.
$ """
$
$ Model created by Hakan Kjellerstrand, hakank@gmail.com
$ See also my Essence'/Tailor page: http://www.hakank.org/savile_row/
$
$
$ Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
language ESSENCE' 1.0
letting n be 12
letting range be domain int(1..n)
letting range2 be domain int(1..n-1)
find x: matrix indexed by [range] of range
find diffs: matrix indexed by [range2] of range2
such that
allDiff(diffs),
allDiff(x),
forall k : range2 . diffs[k] = |x[k+1]-x[k]|,
$ symmetry breaking
x[1] < x[n-1],
diffs[1] < diffs[2]PK hrSb; ; 9 EssencePrime/prob016/traffic_lights/traffic_lights.eprime$
$ Traffic lights problem in Essence'
$
$ CSPLib problem 16
$ http://www.csplib.org/Problems/prob016
$ """
$ Specification:
$ Consider a four way traffic junction with eight traffic lights. Four of
$ the traffic lights are for the vehicles and can be represented by the
$ variables V1 to V4 with domains
$ {r,ry,g,y} (for red, red-yellow, green and yellow).
$ The other four traffic lights are for the pedestrians and can be
$ represented by the variables P1 to P4 with domains {r,g}.
$
$ The constraints on these variables can be modelled by quaternary
$ constraints on
$ (Vi, Pi, Vj, Pj ) for 1<=i<=4, j=(1+i)mod 4 which allow just the tuples
$ {(r,r,g,g), (ry,r,y,r), (g,g,r,r), (y,r,ry,r)}.
$
$ It would be interesting to consider other types of junction (e.g. five roads
$ intersecting) as well as modelling the evolution over time of the
$ traffic light sequence.
$ ...
$
$ Results
$ Only 2^2 out of the 2^12 possible assignments are solutions.
$
$ (V1,P1,V2,P2,V3,P3,V4,P4) =
$ {(r,r,g,g,r,r,g,g), (ry,r,y,r,ry,r,y,r), (g,g,r,r,g,g,r,r), (y,r,ry,r,y,r,ry,r)}
$ [(1,1,3,3,1,1,3,3), ( 2,1,4,1, 2,1,4,1), (3,3,1,1,3,3,1,1), (4,1, 2,1,4,1, 2,1)}
$
$
$ The problem has relative few constraints, but each is very tight.
$ Local propagation appears to be rather ineffective on this problem.
$ """
$
$ This Essence' model was created by Hakan Kjellerstrand, hakank@gmail.com
$ See also my Essence' page: http://www.hakank.org/savile_row/
$
$ Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
language ESSENCE' 1.0
letting n be 4
letting range be domain int(1..n)
letting r be 1 $ red
letting ry be 2 $ red-yellow
letting g be 3 $ green
letting y be 4 $ yellow
letting allowed =
[
[r,r,g,g],
[ry,r,y,r],
[g,g,r,r],
[y,r,ry,r]
]
letting Cars be domain int(r,ry,g,y)
letting Pedestrians be domain int(r,g)
$ decision variables
find V: matrix indexed by [range] of Cars
find P: matrix indexed by [range] of Pedestrians
such that
forall i, j: range .
(j = (1+i) % 4) => table([V[i], P[i], V[j], P[j]], allowed)
PK hrS4M/ 7 EssencePrime/prob049/set_partition/set_partition.eprime$
$ Set partition problem in Essence'
$
$
$ Problem formulation from
$ http://www.koalog.com/resources/samples/PartitionProblem.java.html
$ """
$ This is a partition problem.
$ 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).
$
$"""
$
$ This Essence' model was created by Hakan Kjellerstrand, hakank@gmail.com .
$ See also my Tailor/Essence' page: http://www.hakank.org/savile_row/ .
$
$ Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
language ESSENCE' 1.0
$ For num_sets n must be a multiple of 4 for this to work.
$ And - of course - num_sets must be a multiple of n.
letting n be 16
letting num_sets be 2
$ one solution
$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
$ 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2;
$ ->
$ 1: {1,2,7,8,11,12,13,14},
$ 2: {3,4,5,9,10,15,16}
$ Essence' don't support sets so we represent the sets
$ simply as a value in the a array.
find a: matrix indexed by [int(1..n)] of int(1..num_sets)
find sums: matrix indexed by [int(1..num_sets)] of int(0..n*n)
find sums_squared: matrix indexed by [int(1..num_sets)] of int(0..n*n*n*n)
such that
forall i: int(1..num_sets) .
sums[i] = (sum j: int(1..n) . j*(a[j]=i)) /\
sums_squared[i] = sum j: int(1..n) . j**2*(a[j]=i)
,
$ same cardinality and sums
forall i: int(2..num_sets) .
(sum j: int(1..n) . a[j]=i-1) = (sum j: int(1..n) . a[j]=i) /\
sums[i-1] = sums[i] /\
sums_squared[i-1] = sums_squared[i]
,
$ summetry breaking
a[1] = 1
PK hrS/ / % EssencePrime/prob053/k4p2/k4p2.eprimelanguage ESSENCE' 1.0
$written by Karen E. J. Petrie, 5th of Sept, 2015
find nodes : matrix indexed by [int(1..8)] of int(0..16)
find edges : matrix indexed by [int(1..16)] of int(1..16)
such that
|nodes[1] - nodes[2]| = edges[1],
|nodes[1] - nodes[3]| = edges[2],
|nodes[1] - nodes[4]| = edges[3],
|nodes[2] - nodes[3]| = edges[4],
|nodes[2] - nodes[4]| = edges[5],
|nodes[3] - nodes[4]| = edges[6],
|nodes[5] - nodes[6]| = edges[7],
|nodes[5] - nodes[7]| = edges[8],
|nodes[5] - nodes[8]| = edges[9],
|nodes[6] - nodes[7]| = edges[10],
|nodes[6] - nodes[8]| = edges[11],
|nodes[7] - nodes[8]| = edges[12],
|nodes[1] - nodes[5]| = edges[13],
|nodes[2] - nodes[6]| = edges[14],
|nodes[3] - nodes[7]| = edges[15],
|nodes[4] - nodes[8]| = edges[16],
alldifferent(edges),
alldifferent(nodes)PK PUTu.5 5 + EssencePrime/prob054/nqueens/nqueens.eprime$
$ N-queens in Essence'.
$
$ Using the 3 alldifferent approach with matrix comprehensions.
$
$ Model created by Hakan Kjellerstrand, hakank@gmail.com
$ See also my Essence'/Tailor page: http://www.hakank.org/savile_row/
$
$ Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
$
language ESSENCE' 1.0
$ given n : int(1..)
letting n be 8
letting dom be domain int(1..n)
find x: matrix indexed by [ dom ] of dom
$ branching on x
$ heuristic srf
such that
allDiff(x),
allDiff([x[i]+i | i : dom]),
allDiff([x[i]-i | i : dom])
PK hrSqTE
E
7 EssencePrime/prob057/killer_sudoku/killer_sudoku.eprime$
$ Killer Sudoku in Essence'.
$
$ http://en.wikipedia.org/wiki/Killer_Sudoku
$ """
$ Killer sudoku (also killer su doku, sumdoku, sum doku, addoku, or
$ samunamupure) is a puzzle that combines elements of sudoku and kakuro.
$ Despite the name, the simpler killer sudokus can be easier to solve
$ than regular sudokus, depending on the solver's skill at mental arithmetic;
$ the hardest ones, however, can take hours to crack.
$
$ ...
$
$ The objective is to fill the grid with numbers from 1 to 9 in a way that
$ the following conditions are met:
$
$ * Each row, column, and nonet contains each number exactly once.
$ * The sum of all numbers in a cage must match the small number printed
$ in its corner.
$ * No number appears more than once in a cage. (This is the standard rule
$ for killer sudokus, and implies that no cage can include more
$ than 9 cells.)
$
$ In 'Killer X', an additional rule is that each of the long diagonals
$ contains each number once.
$ """
$
$ Here we solve the problem from the Wikipedia page, also shown here
$ http://en.wikipedia.org/wiki/File:Killersudoku_color.svg
$
$ The output is:
$ 2 1 5 6 4 7 3 9 8
$ 3 6 8 9 5 2 1 7 4
$ 7 9 4 3 8 1 6 5 2
$ 5 8 6 2 7 4 9 3 1
$ 1 4 2 5 9 3 8 6 7
$ 9 7 3 8 1 6 4 2 5
$ 8 2 1 7 3 9 5 4 6
$ 6 5 9 4 2 8 7 1 3
$ 4 3 7 1 6 5 2 8 9
$
$
$ Model created by Hakan Kjellerstrand, hakank@gmail.com
$ See also my Essence'/Savile Row page: http://www.hakank.org/savile_row/
$
$ Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
language ESSENCE' 1.0
letting n be 9
letting range be domain int(1..9)
$ For a better view of the problem, see
$ http://en.wikipedia.org/wiki/File:Killersudoku_color.svg
letting num_p be 29 $ number of segments
letting num_hints be 4 $ number of hints per segments (that's max number of hints)
letting P =
[
[1,1, 1,2, 0,0, 0,0, 3],
[1,3, 1,4, 1,5, 0,0, 15],
[1,6, 2,5, 2,6, 3,5, 22],
[1,7, 2,7, 0,0, 0,0, 4],
[1,8, 2,8, 0,0, 0,0, 16],
[1,9, 2,9, 3,9, 4,9, 15],
[2,1, 2,2, 3,1, 3,2, 25],
[2,3, 2,4, 0,0, 0,0, 17],
[3,3, 3,4, 4,4, 0,0, 9],
[3,6, 4,6, 5,6, 0,0, 8],
[3,7, 3,8, 4,7, 0,0, 20],
[4,1, 5,1, 0,0, 0,0, 6],
[4,2, 4,3, 0,0, 0,0, 14],
[4,5, 5,5, 6,5, 0,0, 17],
[4,8, 5,7, 5,8, 0,0, 17],
[5,2, 5,3, 6,2, 0,0, 13],
[5,4, 6,4, 7,4, 0,0, 20],
[5,9, 6,9, 0,0, 0,0, 12],
[6,1, 7,1, 8,1, 9,1, 27],
[6,3, 7,2, 7,3, 0,0, 6],
[6,6, 7,6, 7,7, 0,0, 20],
[6,7, 6,8, 0,0, 0,0, 6],
[7,5, 8,4, 8,5, 9,4, 10],
[7,8, 7,9, 8,8, 8,9, 14],
[8,2, 9,2, 0,0, 0,0, 8],
[8,3, 9,3, 0,0, 0,0, 16],
[8,6, 8,7, 0,0, 0,0, 15],
[9,5, 9,6, 9,7, 0,0, 13],
[9,8, 9,9, 0,0, 0,0, 17]
]
$ decision variables
find x: matrix indexed by [range, range] of range
such that
$ forAll i: range .
$ allDiff([x[i,j] | j: range]) /\
$ allDiff([x[j,i] | j: range])
$ ,
$ this is neater:
forAll i: range . allDiff(x[..,i]) /\ allDiff(x[i,..]),
forAll i,j: int(0..2) . allDiff([x[r,c] | r: int(i*3+1..i*3+3), c: int(j*3+1..j*3+3)] ),
$ calculate the hints
forAll p: int(1..num_p) .
(sum([x[ P[p, 2*(i-1)+1], P[p,2*(i-1)+2] ] | i: int(1..num_hints), P[p,2*(i-1)+1] > 0])) = P[p, 2*num_hints+1]
PK hrSL A EssencePrime/prob079/partialqueens-comm/partialqueens-comm.eprimelanguage ESSENCE' 1.0
given n : int(1..)
letting AMOUNT_QUEENS be domain int(0..n-1)
given init : matrix indexed by [ int(1..given_queens), int(1..2) ] of AMOUNT_QUEENS
find m : matrix indexed by [AMOUNT_QUEENS, AMOUNT_QUEENS] of bool
such that
$ At most and at least one for each row and column.
forAll i : AMOUNT_QUEENS . (
sum(m[i,..])<=1 /\
sum(m[..,i])<=1 /\
or(m[i,..]) /\
or(m[..,i])
),
$ For sum diagonals, at most one
forAll i : int(0..2*n-2).
$sum([m[j,k] | j : AMOUNT_QUEENS, k : AMOUNT_QUEENS, j+k=i])<=1,
sum([m[j,k] | j : AMOUNT_QUEENS, k : int(i-j), k>=0, k=0, k