1 //
2 // Copyright 2012 Hakan Kjellerstrand
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 //     http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 
16 using System;
17 using Google.OrTools.ConstraintSolver;
18 using System.Collections;
19 using System.Linq;
20 
21 public class WhoKilledAgatha
22 {
23     /**
24      *
25      * Implements the Who killed Agatha problem.
26      * See http://www.hakank.org/google_or_tools/who_killed_agatha.py
27      *
28      */
Solve()29     private static void Solve()
30     {
31         Solver solver = new Solver("WhoKilledAgatha");
32 
33         int n = 3;
34         int agatha = 0;
35         int butler = 1;
36         int charles = 2;
37 
38         //
39         // Decision variables
40         //
41         IntVar the_killer = solver.MakeIntVar(0, 2, "the_killer");
42         IntVar the_victim = solver.MakeIntVar(0, 2, "the_victim");
43         IntVar[,] hates = solver.MakeIntVarMatrix(n, n, 0, 1, "hates");
44         IntVar[] hates_flat = hates.Flatten();
45         IntVar[,] richer = solver.MakeIntVarMatrix(n, n, 0, 1, "richer");
46         IntVar[] richer_flat = richer.Flatten();
47 
48         IntVar[] all = new IntVar[2 * n * n]; // for branching
49         for (int i = 0; i < n * n; i++)
50         {
51             all[i] = hates_flat[i];
52             all[(n * n) + i] = richer_flat[i];
53         }
54 
55         //
56         // Constraints
57         //
58 
59         // Agatha, the butler, and Charles live in Dreadsbury Mansion, and
60         // are the only ones to live there.
61 
62         // A killer always hates, and is no richer than his victim.
63         //     hates[the_killer, the_victim] == 1
64         //     hates_flat[the_killer * n + the_victim] == 1
65         solver.Add(hates_flat.Element(the_killer * n + the_victim) == 1);
66 
67         //    richer[the_killer, the_victim] == 0
68         solver.Add(richer_flat.Element(the_killer * n + the_victim) == 0);
69 
70         // define the concept of richer:
71         //     no one is richer than him-/herself...
72         for (int i = 0; i < n; i++)
73         {
74             solver.Add(richer[i, i] == 0);
75         }
76 
77         // (contd...) if i is richer than j then j is not richer than i
78         //   if (i != j) =>
79         //       ((richer[i,j] = 1) <=> (richer[j,i] = 0))
80         for (int i = 0; i < n; i++)
81         {
82             for (int j = 0; j < n; j++)
83             {
84                 if (i != j)
85                 {
86                     solver.Add((richer[i, j] == 1) - (richer[j, i] == 0) == 0);
87                 }
88             }
89         }
90 
91         // Charles hates no one that Agatha hates.
92         //    forall i in 0..2:
93         //       (hates[agatha, i] = 1) => (hates[charles, i] = 0)
94         for (int i = 0; i < n; i++)
95         {
96             solver.Add((hates[agatha, i] == 1) - (hates[charles, i] == 0) <= 0);
97         }
98 
99         // Agatha hates everybody except the butler.
100         solver.Add(hates[agatha, charles] == 1);
101         solver.Add(hates[agatha, agatha] == 1);
102         solver.Add(hates[agatha, butler] == 0);
103 
104         // The butler hates everyone not richer than Aunt Agatha.
105         //    forall i in 0..2:
106         //       (richer[i, agatha] = 0) => (hates[butler, i] = 1)
107         for (int i = 0; i < n; i++)
108         {
109             solver.Add((richer[i, agatha] == 0) - (hates[butler, i] == 1) <= 0);
110         }
111 
112         // The butler hates everyone whom Agatha hates.
113         //     forall i : 0..2:
114         //         (hates[agatha, i] = 1) => (hates[butler, i] = 1)
115         for (int i = 0; i < n; i++)
116         {
117             solver.Add((hates[agatha, i] == 1) - (hates[butler, i] == 1) <= 0);
118         }
119 
120         // Noone hates everyone.
121         //     forall i in 0..2:
122         //         (sum j in 0..2: hates[i,j]) <= 2
123         for (int i = 0; i < n; i++)
124         {
125             solver.Add((from j in Enumerable.Range(0, n) select hates[i, j]).ToArray().Sum() <= 2);
126         }
127 
128         // Who killed Agatha?
129         solver.Add(the_victim == agatha);
130 
131         //
132         // Search
133         //
134         DecisionBuilder db = solver.MakePhase(all, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
135 
136         solver.NewSearch(db);
137 
138         while (solver.NextSolution())
139         {
140             Console.WriteLine("the_killer: " + the_killer.Value());
141         }
142 
143         Console.WriteLine("\nSolutions: {0}", solver.Solutions());
144         Console.WriteLine("WallTime: {0}ms", solver.WallTime());
145         Console.WriteLine("Failures: {0}", solver.Failures());
146         Console.WriteLine("Branches: {0} ", solver.Branches());
147 
148         solver.EndSearch();
149     }
150 
Main(String[] args)151     public static void Main(String[] args)
152     {
153         Solve();
154     }
155 }
156