Brute Force

Thinking some more about the Logic Games project, my first attempt is going to be brute force. Each of the statements in the logic game text can be converted into a series of Boolean rules (rules whose conditions either evaluate to true or false), and then I can create a rule engine to iteratively generate facts until the question has been answered.

Here's an example, taken from another LSAT question:

A piano instructor will schedule exactly one lesson for each of six students - Grace, Henry, Janet, Steve, Tom and Una - one lesson per day for six consecutive days. The schedule must conform to the following conditions:
  1. Henry's lesson is later in the schedule than Janet's lesson
  2. Una's lesson is later in the schedule than Steve's lesson
  3. Steve's lesson is exactly three days after Grace's lesson
  4. Janet's lesson is on the first day or else the third day
If Janet's lesson is scheduled for the first day, the the lesson for which of the following students must be scheduled on the sixth day - Grace, Henry, Steve, Tom or Una?
From this, we can generate a large number of Boolean rules to describe the problem. These rules will take the form of if ... then ... statements. Taking a look at the first condition - Henry's lesson is later in the schedule than Janet's lesson - we can derive the following rules:
  • If Janet is in the fifth position, then Henry is in the sixth position.
  • If Janet is in the fourth position, then Henry is NOT in the third position
  • If Janet is in the fourth position, then Henry is NOT in the second position
  • If Janet is in the fourth position, then Henry is NOT in the first position
  • If Janet is in the third position, then Henry is NOT in the second position
  • If Janet is in the third position, then Henry is NOT in the first position
  • If Janet is in the second position, then Henry is NOT in the first position
  • If Henry is in the second position, then Janet is in the first position
  • If Henry is in the third position, then Janet is NOT in the fourth position
  • If Henry is in the third position, then Janet is NOT in the fifth position
  • If Henry is in the third position, then Janet is NOT in the sixth position
  • If Henry is in the fourth position, then Janet is NOT in the fifth position
  • If Henry is in the fourth position, then Janet is NOT in the sixth position
  • If Henry is in the fifth position, then Janet is NOT in the sixth position
In addition, we can derive two facts from the first condition:
  • Janet is NOT in the sixth position
  • Henry is NOT in the first position
Then there are three types of additional rules that are implied for all combinations of person/position:
  • If person A is in position X, then persons B, C, D, E, and F are NOT in position X
  • If person A is in position X, the person A is not in any of the other positions
  • If person A is NOT in positions 1, 2, 3, 4, or 5, then person A is in position 6
So, for example, we would have a set of rules for Henry like this:
  • If Henry is in position 1, then Grace is NOT in position 1
  • If Henry is in position 1, then Janet is NOT in position 1
  • If Henry is in position 1, then Steve is NOT in position 1
  • etc...
And
  • If Henry is in position 1, then Henry is NOT in position 2
  • If Henry is in position 1, then Henry is NOT in position 3
  • If Henry is in position 1, then Henry is NOT in position 4
  • etc...
And
  • If Henry is NOT in position 1, and Henry is NOT in position 2, and Henry is NOT in position 3, and Henry is NOT in position 4, and Henry is NOT in position 5, then Henry is in position 6
  • etc...
Once you have generated all of the rules, the way that the algorithm will work is to iterate over the rules deriving new facts. We start off with 1 fact: Janet is in position 1. So as we iterate over the rules, we can fire at least 10 additional rules that will derive new facts: Grace is NOT in position 1, Henry is NOT in position 1, Steve is NOT in position 1, Tom is NOT in position 1, Una is NOT in position 1, Janet is NOT in position 2, Janet is NOT in position 3, Janet is NOT in position 4, Janet is NOT in position 5, Janet is NOT in position 6.

After you make a pass across every rule, you start over at the top, testing each rule again given the facts that we derived from the previous pass, then continue until you have gathered enough facts to answer the question (in this case, Una is the correct answer).

Because this is a brute force approach, we get a lot of rules to test, so the algorithm will need to keep track of which rules have already been fired (i.e. which rules have a known answer), and on each iteration, only test the unfired rules.

Now, there is still a lot of hard manual work to do to solve this problem - for each condition, we have to manually break it up into a series of Boolean rules. So, in the long run, I will want to at least make some sort of DSL to allow me to put in the conditions in a more-or-less English syntax, and let the system generate all the rules for me. But let's call that phase 2 :-) For now, I want to focus on building the rule engine. I am looking through the book Constructing Intelligent Agents Using Java by Joseph and Jennifer Bigus. The fourth chapter, Reasoning Systems, outlines a rule inference engine that I am planning on using as a model for mine. Their engine does a lot of stuff that I don't need for mine, like accounting for fuzzy logic, so mine will be a lot simpler. Also, I'll be working in Ruby rather than Java, and I think that the dynamic nature of Ruby will also simplify the code quite a bit. So it isn't exactly a port of the Java code to Ruby, I'm just using it as a good starting point.

I hope to get started over the long weekend, and I'll stick my code up on Github.