Decision Management Community November 2014 Challenge: Who killed Agatha?
This blog post was inspired by Decision Management Community November 2014 Challenge: Challenge Nov-2014 Decision model 'Who killed Agatha?'. The original text - and the one linked to from the Challenge page - is here.
From DM Community Challenge Nov-2014:
All the decodings has the same approach: defining two binary 3x3 matrices of decision variables:
The constraints will then on these two decision variables, the two matrices + the
First I describe the MiniZinc model in detail and after that a discussion about the solution and why it returns 8 solutions (all with the same killer: Agatha).
The decoding shown below is slightly altered for simpler presentation.
Hates: Regarding the concept of hatred there is no logic involved how it can be used: A and B can both hate each other, or one of them can hate the other, or neither hates the other. Note that A can hate him/herself.
Richer: The concept of richer is a completely different matter, however. There is a logic involved in this relation:
As mentioned above, we don't need to - and cannot - do a similar analysis on (the semantic meaning of) the hate relation.
See below A note on the richer relation for a comment on the assumption that either A is richer than B or B is richer than A.
It is important to not forget that Agatha can hate herself. Missing this fact in this model would yield that either Agatha or Charles is the killer.
The reason this model give more than one solution is because it is - in my interpretation of the problem - under constrained: there is not enough information about certain relations in the
Below are the values of the
The entries with "0..1" are the decision variables that are not constrained (decided) enough before search. (Note: Not all CP solvers have the feature to show the inferred variable domains before search. The table below is from my Picat model, slightly altered: who_killed_agatha.pi)
Thus 8 different solutions:
From DM Community Challenge Nov-2014:
Someone in Dreadsbury Mansion killed Aunt Agatha.A model for this problem is actually one of the first I implement whenever I learn a new Constraint Programming (CP) system since in my approach it has some features that are important to test (they are explained in some details below):
Agatha, the butler, and Charles live in Dreadsbury Mansion, and
are the only ones to live there. A killer always hates, and is
no richer than his victim. Charles hates noone that Agatha hates.
Agatha hates everybody except the butler. The butler hates everyone
not richer than Aunt Agatha. The butler hates everyone whom Agatha hates.
Noone hates everyone. Who killed Agatha?
- reification: "reasoning about constraints"
- matrix element: how to index a matrix with decision variables
All the decodings has the same approach: defining two binary 3x3 matrices of decision variables:
- a "hates" matrix, i.e. who hates who
- a "richer" than matrix: who is richer than who
Killer decision variable of range 1..3 (Agatha=1, Butler=2,
and Charles=3). In some encodings (as the one below), Victim is also
a decision variable, but we know that Agatha is the Victim from the
start so this decision variable can be skipped.
The constraints will then on these two decision variables, the two matrices + the
Killer decision variable.
First I describe the MiniZinc model in detail and after that a discussion about the solution and why it returns 8 solutions (all with the same killer: Agatha).
The Minizinc model
My original MiniZinc model is here who_killed_agatha.mzn.The decoding shown below is slightly altered for simpler presentation.
Initiation of constants and domains
The following defines the dimension of the matrices (3x3) and also the domain - the possible values - of the killer and victim variables (1..3).int: n = 3; set of int: r = 1..3;Here we define the constants
agatha, butler, and charles.
The values are fixed to
the integers 1..3 since the solvers used handles finite domains in terms
of integers. (There are exceptions to this. To state it short: finite domains
in terms of integers is the most common in CP. Some systems also support set variables
and/or float decision variables.)
% the people involved int: agatha = 1; int: butler = 2; int: charles = 3;
Decision variables
The two decision variablesthe_killer and the_victim has both the domain
1..3, i.e. the set {agatha, butler charles}.
var r: the_killer; var r: the_victim;The 3x3 entries in the two matrices
hates and richer are binary decision
variables: 1 represents true, 0 represents false.
array[r,r] of var 0..1: hates; array[r,r] of var 0..1: richer;The following statement just states that the CP solver should use its default search method.
solve satisfy;Aside: There is a range of different search heuristics available for most CP solvers, than can speed up more complex CSP's significantly, e.g. for an array
x of decision variables one could state:
solve :: int_search(x, first_fail, indomain_split, complete);but for this simple problem we just settle for the default.
Constraints
Next is the constraint section where all the requirements (constraints) of the problem are specified. The order of the constraints is the same order as the problem description. In contrast to the MiniZinc version on my MiniZinc site (the link above), I have here separated each constraint in its own section to emphasize the specific constraint.Constraint: A killer always hates, and is no richer than his victim.
Here we see an example of a "matrix element" constraint, i.e. that a decision variable (the_killer) is used as an index of a matrix of decision variables,
e.g.
hates[the_killer, the_victim] = 1<
[Aside: In MiniZinc this can be done in this most syntactical pleasing ("natural") way,
though most of the other CP systems cannot handle this syntax so an alternative
syntax must be used.
However, most CP systems have a syntax for the one dimensional element constraint,
which is then stated as
element(Y,X,Z)
which corresponds to
X[Y] = Z,
where X and both Y and Z can be decision variables. The element constraint is central
for CP and is one of the features that separates it from traditional LP/MIP modeling
systems.]
The first constraint
hates[the_killer, the_victim] = 1simply means that the killer hates the victim, and the second that the killer is not richer than the victim.
constraint % A killer always hates, and is no richer than his victim. hates[the_killer, the_victim] = 1 /\ richer[the_killer, the_victim] = 0 ;
The concept of richer
The only relations we are using here are hates and richer, and we must take care of the meaning of these concepts.Hates: Regarding the concept of hatred there is no logic involved how it can be used: A and B can both hate each other, or one of them can hate the other, or neither hates the other. Note that A can hate him/herself.
Richer: The concept of richer is a completely different matter, however. There is a logic involved in this relation:
- if A is richer than B, then B cannot be richer than A
- A cannot be richer than him/herself
As mentioned above, we don't need to - and cannot - do a similar analysis on (the semantic meaning of) the hate relation.
See below A note on the richer relation for a comment on the assumption that either A is richer than B or B is richer than A.
constraint
% define the concept of richer
% no one is richer than him-/herself
forall(i in r) (
richer[i,i] = 0
)
% (contd...) if i is richer than j then j is not richer than i
/\
forall(i, j in r where i != j) (
richer[i,j] = 1 <-> richer[j,i] = 0
)
;
Constraint: Charles hates noone that Agatha hates.
Here again, reifications is handy. In pseudo code:
FOR EACH person I in the house:
IF Agatha hates I THEN Charles don't hate I
constraint
% Charles hates noone that Agatha hates.
forall(i in r) (
hates[charles, i] = 0 <- hates[agatha, i] = 1
)
;
Constraint: Agatha hates everybody except the butler
Here we simply state three hate facts.It is important to not forget that Agatha can hate herself. Missing this fact in this model would yield that either Agatha or Charles is the killer.
constraint % Agatha hates everybody except the butler. hates[agatha, charles] = 1 /\ hates[agatha, agatha] = 1 /\ hates[agatha, butler] = 0 ;
Constraint: The butler hates everyone not richer than Aunt Agatha.
Same as above, we use reification to handle this:
FOR EACH person I in the house
IF I is not richer than Agatha THEN Butler hates I
which is implemented as
constraint
% The butler hates everyone not richer than Aunt Agatha.
forall(i in r) (
hates[butler, i] = 1 <- richer[i, agatha] = 0
)
;
Constraint: The butler hates everyone whom Agatha hates.
Same reasoning with reifications as above.
constraint
% The butler hates everyone whom Agatha hates.
forall(i in r) (
hates[butler, i] = 1 <- hates[agatha, i] = 1
)
;
Constraint: Noone hates everyone.
Here we count - for each person - the number of 1's (i.e. true) for each row in the hates matrix, and ensure that they are less than 3 (i.e. not all).
constraint
% Noone hates everyone.
forall(i in r) (
sum(j in r) (hates[i,j]) <= 2
)
;
Who killed Agatha?
As mentioned above, this is not really needed since we could have hard codedthe_victim to agatha without changing anything.
constraint % Who killed Agatha? the_victim = agatha ;To summarize: This model use a couple of important concepts in Constraint Programming:
- decision variables with specific (finite) domains
- reifications, implication and equivalence between constraints
- element constraint (here in term of the more complex variant: matrix element)
Solution and analysis
There are total 8 different solutions for this MiniZinc model, all stating that Agatha is the killer. (Being able to get all solutions to a combinatorial problem is a excellent feature in Constraint Programming.)The reason this model give more than one solution is because it is - in my interpretation of the problem - under constrained: there is not enough information about certain relations in the
hates and richer matrices to yield a unique solution.
Below are the values of the
hates and richer matrices after all constraints have
been activated, but before search (searching in the search tree and assign all the decision
variables to give a solution), as well as the killer variable.
The entries with "0..1" are the decision variables that are not constrained (decided) enough before search. (Note: Not all CP solvers have the feature to show the inferred variable domains before search. The table below is from my Picat model, slightly altered: who_killed_agatha.pi)
Killer:
killer= 1
Hates
--------
Agatha : Agatha : 1 Butler : 0 Charles: 1
Butler : Agatha : 1 Butler : 0 Charles: 1
Charles: Agatha : 0 Butler : 0..1 Charles: 0
Richer
--------
Agatha : Agatha : 0 Butler : 0 Charles: 0..1
Butler : Agatha : 1 Butler : 0 Charles: 0..1
Charles: Agatha : 0..1 Butler : 0..1 Charles: 0
These undecided variables involves if:
- Charles hates Butler (or not)
- Agatha is richer than Charles (or not)
- Butler is richer than Charles (or not)
- Charles is richer than Agatha (or not)
- Charles is richer than Butler (or not)
- The killer has been assigned to 1 (= Agatha).
- Many (namely 5) of the variables including Charles are undecided before search, i.e. using the constraints only can not figure out if they are true of not. This is perhaps not too surprising since most constraints in the model - and problem statement - involves only Agatha and Butler.
- "Agatha is richer than Charles" and "Charles is richer than Agatha"
- "Butler is richer than Charles" and "Charles is richer than Butler"
Thus 8 different solutions:
[0,1,0,1,0]
[0,1,0,1,1]
[0,1,1,0,0]
[0,1,1,0,1]
[1,0,0,1,0]
[1,0,0,1,1]
[1,0,1,0,0]
[1,0,1,0,1]
This concludes the analysis.
A note on the "richer" relation
Nothing rules out that A can be as rich as B (i.e. that neither is richer than the other). However, in this simple model, we assume a stricter variant: that either A is richer than B, or B is richer than A. If we would change the equivalence relationricher[i,j] = 1 <-> richer[j,i] = 0(which means:
IF A is richer than B THEN B is not richer than A AND IF B is not richer than A THEN A is richer than B)to an implication
richer[i,j] = 1 -> richer[j,i] = 0
(IF A is richer than B THEN B is not richer than A)then it don't change the principal solution but we would yield 18 solutions instead of 8, all point to the same killer: Agatha.
OTHER ENCODINGS
Here is a list of all the encodings of the Agatha murder problem that I have implemented so far. Whenever I learn a new CP system, the Agatha problem will probably be one of the first to test. See http://hakank.org/common_cp_models/#whokilledagatha:- AIMMS+CP: WhoKilledAgatha.aim
- AMPL: who_killed_agatha.mod
- B-Prolog: who_killed_agatha.pl
- Choco: WhoKilledAgatha.java
- Choco3: WhoKilledAgatha.java
- Comet: who_killed_agatha.co
- ECLiPSE: who_killed_agatha.ecl
- Essence'/Savile row: who_killed_agatha.eprime
- Essence'/Tailor: who_killed_agatha.eprime
- Gecode: who_killed_agatha.cpp
- Google CP Solver/C#: who_killed_agatha.cs
- Google CP Solver/Java: WhoKilledAgatha.java
- Google CP Solver/Python: who_killed_agatha.py
- JaCoP: WhoKilledAgatha.java
- JaCoP/Scala: WhoKilledAgatha.scala
- JSR-331: WhoKilledAgatha.java
- MiniZinc: who_killed_agatha.mzn
- OscaR: WhoKilledAgatha.scala
- Picat: who_killed_agatha.pi
- SICStus: who_killed_agatha.pl
- Zinc: who_killed_agatha.zinc
- Answer Set Programming: who_killed_agatha.lp Note: Answer Set Programming is not a CP system but is interesting to see the encoding as a comparison.