The Logic of Logic

My son came to me the other day and said, "Dad, I need help with a math problem." The problem went like this:

• We're going out to dinner taking 1-6 grandparents, 1-10 parents and/or 1-40 children

• Grandparents cost $3 for dinner, parents $2 and children $0.50

• There must be 20 total people at dinner and it must cost $20

• How many grandparents, parents and children are going to dinner?

The reason this problem is interesting is because there are 3 variables, but only 2 equations:

1. grandparents * 3 + parents * 2 + children * .5 = 20

2. grandparents + parents + children = 20

Being a coder, I sat down to write the program to enumerate all possible solutions:

class Program {
  static void Main(string[] args) {
    for( int grandparents = 1; grandparents < 7; ++grandparents ) {
      for( int parents = 1; parents < 11; ++parents ) {
        for( int children = 2; children < 41; children += 2 ) {
          double dollars = grandparents * 3 + parents * 2 + children * .50;
          int people = grandparents + parents + children;
          if( dollars == 20 && people == 20 ) {
            Console.WriteLine("grand parents= {0}, parents= {1}, kids= {2}",
                              grandparents, parents, children);
          }
        }
      }
    }
  }
}

Running this program saves my son the time to figure out the solution through tedious trial-and-error (plus, he didn't even have to write the program, since I did that part -- tricky little bastard, isn't he?!?) by producing the following output:

grand parents= 1, parents= 5, kids= 14

That was all well and good 'til Alex, a friend of mine, boiled the problem down to a single-statement Prolog program for me (although this program doesn't capture the range of values the variables can take on):

people_at_the_meal(Grandparents, Parents, Children) :-
  Grandparents * 3 + Parents * 2 + Children * 0.5 = 20,
  Grandparents + Parents + Children = 20. 

Then I went on to regale Alex about the time my grandmother asked me to schedule her tennis tournament for her on my computer. She had requirements like, "everyone has to place everyone else at least once" and "you have to lose twice to be out of the tournament" and "nobody can play twice in a row" (it's not good politics for a computer program to kill old ladies...). My grandmother's problem statement doesn't fit the traditional algorithmic statements that I'm used to using computers for, nor was I ever able to re-form the problem in those terms (it's not like my grandma was ever going to leave me a bunch of money anyway...). Alex completely understood and informed me that the NBA has the same problem (with slightly sprier players) and they use logic programs to solve it. In fact, in his experience, these problems happen all the time in the business world.

Constraint Logic Programs (CLPs) break down into constants, variables over ranges and relations of truth, which together make up the constraints in a logic system. In my son's case, the constants are the numbers, e.g. 3, 20, etc, the variables are the number of people of each type and the relations form the constraints, e.g. the sum of all people must be 20. The CLP "solver" (in Alex's parlance) provides the logic over a particular "domain" (real numbers in our case) and knows how to do all the iteration and forward and backward chaining to solve the people_at_the_meal problem. A different solver would be able to solve my grandmother's and the NBA's scheduling problem.

It was only after most of this discussion that I realized that I recognized the syntax that Alex had produced: it was Prolog, a CLP language I had blocked. I had taken a Prolog course in it in college and absolutely hated it, but not because of the things that allowed me to solve these kinds of problems: that was great. The things I hated were all of the algorithmic things that I needed to be able to do that Prolog was terrible at, e.g. take input, product output, suck in facts from data external to the system (like the NBA player roster), etc. CLPs themselves are damn cool.