Could we use decision tables to represent and solve complex logical problems? An example of such problem was offered by the DMCommunity.org in the Nov-2014 Challenge called “Who Killed Agatha“. Here is the problem description:

Someone in Dreadsbury Mansion killed Aunt Agatha. 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?

It is only natural to solve such problems using Constraint Programming (CP) techniques. Hakan Kjellerstrand submitted his solution using MiniZinc and provided links to 22 similar solutions using other CP tools. First I tried to present this problem in Java using JSR331 – see DreadsburyMansionMurder.java.

However, what I really wanted to do was to present and solve this problem without any programming language. I wanted to use business-oriented decision tables in the simple Excel format supported by OpenRules Rule Solver. After quite a few try-and-fail attempts, I finally got it working. The proper solution can be found in this Excel file DecisionWhoKilledAgatha.xls. Below I will described the proper decision tables and all found solutions.

In my decision tables I freely introduced various decision variables in plain English (like “Agatha Hates Butler”) on as needed basis. The very first rule “A killer always hates, and is no richer than his victim” can be specified as follows:

As you may guess, the first rule states: “If BUTLER KILLED AGATHA is true, Then Butler Hates Agatha is true (1)”. The second rules states: If BUTLER KILLED AGATHA is true, Then Butler Richer Than Agatha is false (0)”. You got the picture.  It is also important to understand that when the Rule Solver will process this table, it would not treat it as traditional single-hit or multi-hit decision tables. Instead, it will create a constraint satisfaction problem and will post the proper conditional constraints for ALL rules in such tables (the order of rules is not important).

The next rule “Charles hates noone that Agatha hates” can be represented in the following table:

Here is the next rule “Agatha hates everybody except the butler“:

The rules “The butler hates everyone not richer than Aunt Agatha” and “The butler hates everyone whom Agatha hates” can be naturally combined in  the following decision table:

The last explicit rule from the problem definition above states “Noone hates everyone“. It would be awkward to describe all possible combinations of who hates whom. So, instead we may define intermediate variables such as “Number of People Agatha Hates” as a sum of all hate-variables for each suspect:

Then we may simply state that these numbers should be strictly less than 3:

It  may seem that we have already defined all problem rules, at least those that were expressed explicitly. However, if we try to run the problem with only these rules, the results would be quite strange. You will see that Agatha could be richer than Agatha or while a Butler is richer than Charles we may get a result that at the same time Charles is richer than Butler as well. Why does it occur?

The reason is that like in many real-world problems, this problem has many intrinsic rules which we assume are true but haven’t been explicitly specified yet. For example, it is obvious that nobody should be richer than her/himself.  The fact that we use the names like “Agatha Richer Agatha” does not specify our actual understanding of this fact. So, we need to add the following 3 rules:

Another example of hidden rules is the fact that “If Agatha Richer Than Butler is TRUE” then the opposite statement “Butler Richer Than Agatha” should be FALSE. We need to specify all these rules explicitly as well. First I tried to represent them using all possible combinations of “Richer Than”-variables. Then I understood it would be much nicer to simply state that a sum of each “Richer Than”-pair should be equal exactly 1 (making them mutually exclusive).  Below is how I did it using the standard OpenRules template “ActionXoperYcompareZ”:

And finally, the fact that we use variables like “BUTLER KILLED AGATHA”, “CHARLES KILLED AGATHA”, and “AGATHA KILLED AGATHA” does not yet mean that somebody actually killed her – all these variables still could be false (equal to 0) at the same time. So, we need to explicitly specify that “Somebody Killed Agatha”.  To do it, I first defined a new variable “Number of Killers” as a sum of these 3 variables:

and then I stated that there should be one and only one killer:

After defining all extrinsic and all intrinsic rules, I copied all decision variables from all above decision tables and pasted them into the following Glossary table:

All those variables belong to a business concept which I called “Murder”. The domains of these variables (their possible values) are defined  from 0 to 1 (true or false) with an exception for intermediate variables for numbers of people defined from 0 to 3. All variables are unknowns of this problem.

Finally our decision “WhoKilledAgatha” should simply execute all decision tables defined above:

To execute this problem, I used an OpenRules Engine in the “Solve” mode (that selects Rule Solver as an execution engine). Here is a Java launcher for this problem:

It produced the following solution:

So, this solution points that Agatha killed herself and shows the values of all other variables: you may check that all rules have been satisfied.  This result could complete the description of my solution.

However, I also wanted to check that there are no other possible solutions when somebody else killed Agatha. So, I decided to ask Rule Solver to find not one but ALL possible solutions of this problem (let’s say up to 50 solutions). To do that, I made small change in the standard Java launcher by adding one line:

decision.put(“MaxSolutions”, “50”);

It generated 8 possible solutions – they all point to Agatha’s suicide and are described in this HTML file. It corresponds to the results found by Hakan using various CP programs.

I still was suspicious if somebody (e.g. Butler) could assist Agatha in committing suicide. So, I relaxed the above constraint “SomeoneKilledAgatha” to the following one:

allowing more than 1 killers. However, even with this constraint relaxation I received the same 8 solutions effectively clearing Butler and Charles from any suspicions in assisting Agatha to kill herself.

I hope this exercise demonstrates that traditional decision tables could be well suitable for representation of quite complex logical problems when they are executed by a powerful rule engine (with capabilities to consider all possible combinations of decision variables) such as our Rule Solver.