The Golfer Riddle

The famous golfer riddle - first published (as far as I know) by rule-celebrity Dr. Ernest Friedmann-Hill (creator of the JESS rule engine) in this online-article.

Here's the riddle:

You look at the blackboard. It’s one of those word puzzles, the logic kind. Mrs. Krabapple is waiting for you to solve it. You quickly scan what she's scrawled on the board with her crone’s hand:

  • A foursome of golfers is standing at a tee, in a line from left to right.
  • Each golfer wears different colored pants; one is wearing red pants.
  • The golfer to Fred’s immediate right is wearing blue pants.
  • Joe is second in line.
  • Bob is wearing plaid pants.
  • Tom isn’t in position one or four, and he isn’t wearing the hideous orange pants.

In what order will the four golfers play, and what color are each golfer’s pants?

You get the gist of it right away, but how on earth are you supposed to figure it out? There’s no formula to use, no analytic procedure for deriving a solution. Algebra was one thing, but this? Why weren’t you paying attention in class?

Rules to the rescue! A rule–based program can satisfy Mrs. Krabapple by efficiently finding the one combination of names, positions, and colors that fits all the constraints.

The Solution

Credits for this solution to JBoss-Rules - most of this example is contained in their distribution.

Short note: I implemented a solution to the golfer-riddle in Prolog using backward chaining... They look quite similar but the Prolog-version is a few lines shorter...

Basic Idea

We have two classes, Golfer and GolfingExample, the latter responsible for initializing the rule engine, reading the rules from a file, asserting the facts (here: Golfer-objects) to the working memory and invoking the engine.

  1. Create Golfer-objects for every possible combination of name, color and position.
  2. Let the rule engine select those which satisfy the riddle's conditions.

The Java Classes

Golfer.java

    public  class Golfer {
        private String name;
        private String color;
        private int position;

        public Golfer() {}

        public Golfer(String name,   String color, int position) {
            super();
            this.name = name;
            this.color = color;
            this.position = position;
        }

        public String getColor() {
                    return this.color; }

            public String getName() {
            return this.name;  }

            public int getPosition() {
            return this.position;  }        

    } // Golfer

Ok, that one is very straightforward, nothing special here, just a simple JavaBean.

GolfingExample.java

Now for our infrastructure-code, which has to control creation of Golfer-objects and invoke the rule engine.

public class GolfingExample {

   public static void main(final String[] args) throws Exception {

    // read the rules from file "golf.drl"
    final PackageBuilder builder = new PackageBuilder();
            builder.addPackageFromDrl( new InputStreamReader( 
            GolfingExample.class.getResourceAsStream( "golf.drl" ) ) );

    // create ruleBase and working memory
            final RuleBase ruleBase = RuleBaseFactory.newRuleBase();
            ruleBase.addPackage( builder.getPackage() );

            final StatefulSession session = ruleBase.newStatefulSession();

    // create all possible Golfer objects
            String[] names = new String[] { "Fred", "Joe", "Bob", "Tom" };
            String[] colors = new String[] { "red", "blue", "plaid", "orange" };
            int[] positions = new int[] { 1, 2, 3, 4 };

            for ( int n = 0; n < names.length; n++ ) {
               for ( int c = 0; c < colors.length; c++ ) {
                      for ( int p = 0; p < positions.length; p++ ) {
                      session.assertObject( 
                   new Golfer( names[n], colors[c], positions[p]) );
                      }                
               }            
            }

    // invoke the rule engine
            session.fireAllRules();
            session.dispose();

       } // main
} // GolfingExample

Now we have our Java-infrastructure in place and can start coding the rule file.

Developing the Golf Rules

Version Zero: Find Fred

Lets start with a very simple version of a rule file, just to find Fred:

File golf.drl(version 0):

rule "very simple golfer"
    when // there is a golfer named Fred
        g: Golfer( name == "Fred )
    then 
        System.out.println(  g.getName() + "   " + 
                        g.getPosition() + "   " + 
                        g.getColor() );  
end // very simple golfer

This rule makes our rule engine look for every Golfer object whose name-attribute == "Fred". Not suprisingly, given the large number of Golfer-objects we asserted in our GolfingExample, it finds the following:

Fred  orange   4
Fred  orange   3
Fred  orange   2
Fred  orange   1
Fred  plaid   4
Fred  plaid   3
Fred  plaid   2
Fred  plaid   1
Fred  blue   4
Fred  blue   3
Fred  blue   2
Fred  blue   1
Fred  red   4
Fred  red   3
Fred  red   2
Fred  red   1

These are all objects with name==Fred.

Version One: Find Fred and his Right Neighbour

Not let's add a second condition: The golfer to Fred's right is wearing blue. We do not know his name yet... For our convenience, we add a function named printTwoGolfers to our rule file, making it easier to print out our results!

Our rule now looks for pairs of golfers: Fred and the golfer to his right side (for whom the condition position==fredsPosition+1 holds).

File golf.drl(version 1)

package org.drools.examples;

import org.drools.examples.Golfer;

rule "golfer riddle version 1" 
       when 
        // a golfer named fred
            fred: Golfer( name == "Fred", 
                    $fredsPosition : position, $fredsColor : color  )

    // the golfer behind fred wears blue
            second: Golfer( name != "Fred", 
                    position == ( $fredsPosition + 1 ),
                    color == "blue", color != $fredsColor )
   then
    printTwoGolfers( fred, second );
end // rule version 1    


function void printTwoGolfers( Golfer first, Golfer g2 ) {
    System.out.println( 
       first.getName() + "-" + first.getPosition() + "-" + first.getColor() + ">>>" +
       g2.getName() + "-" + g2.getPosition() + "-" + g2.getColor() );
}

This version finds pairs of golfers where Fred is positioned before the second one.:

Fred-3-orange>>>Tom-4-blue
Fred-3-plaid>>>Tom-4-blue
Fred-3-red>>>Tom-4-blue
Fred-2-orange>>>Tom-3-blue
Fred-2-plaid>>>Tom-3-blue
Fred-2-red>>>Tom-3-blue
... 
(many lines deleted)
...
Fred-1-orange>>>Tom-2-blue
Fred-1-plaid>>>Tom-2-blue
Fred-1-orange>>>Joe-2-blue
Fred-1-plaid>>>Joe-2-blue
Fred-1-red>>>Joe-2-blue

Version Two: Add Joe to the Pair...

Another information we get from our riddle is that Joe is second in line. Lets add this condition to our rule, making the rule engine search for triplets of golfers:

File golf.drl(version 2)

package org.drools.examples;
import org.drools.examples.Golfer;

rule "Joe, Fred and his Neighbour" 
       when 
            // a golfer named fred
            fred: Golfer( name == "Fred", 
                        $fredsPosition : position, $fredsColor : color  )

    // Golfer behind Fred wears blue
            second: Golfer( $unknownsName : name != "Fred", 
                    $unknownsPosition :  position == ( $fredsPosition + 1 ),
                    $unknownsColor : color == "blue", color != $fredsColor )

            // Joe is second          
            joe: Golfer( name == "Joe", $joesPosition : position == 2, 
                    position != $fredsPosition,
                    $joesColor : color != $fredsColor )

    then
            printGolfer( fred ); System.out.print(">>");
            printGolfer( second );System.out.print(">>");
            printGolfer( joe );
            System.out.println();
end // rule version 2    


function void printGolfer( Golfer g ) {
    System.out.print( 
       g.getName() + "-" + g.getPosition() + "-" + g.getColor());
}

The result, nobody wonders any longer, finds triples:

Fred-3-plaid>>Tom-4-blue>>Joe-2-orange
Fred-3-orange>>Tom-4-blue>>Joe-2-plaid
Fred-3-orange>>Tom-4-blue>>Joe-2-blue
Fred-3-red>>Tom-4-blue>>Joe-2-orange
Fred-3-orange>>Tom-4-blue>>Joe-2-red
Fred-3-plaid>>Tom-4-blue>>Joe-2-blue
Fred-3-red>>Tom-4-blue>>Joe-2-plaid
... 
(many lines deleted)
...
Fred-1-plaid>>Joe-2-blue>>Joe-2-blue
Fred-1-plaid>>Joe-2-blue>>Joe-2-red
Fred-1-red>>Joe-2-blue>>Joe-2-blue

Hey - that's not what we wanted: Joe occurs twice within triples! Every golfer should occur only once...

The reason for this seemingly inconsistent behavior lies in our rule: both the variables joeand secondcan independently be instantiated to a golfer named joe. We could avoid this by adding a second rule - but our task was solving the riddle, not perfection :-)

The final version of golf.drl

rule "Golfer Riddle" 
    when
        // A golfer named Fred, 
        Golfer( name == "Fred", 
                $fredsPosition : position, $fredsColor : color  )

        // Der Golfer hinter Fred trägt blau
        Golfer( $unknownsName : name != "Fred", 
                $unknownsPosition :  position == ( $fredsPosition + 1 ),
                $unknownsColor : color == "blue", color != $fredsColor )

        // Joe steht an zweiter Stelle                
        Golfer( name == "Joe", $joesPosition : position == 2, 
                position != $fredsPosition,
                $joesColor : color != $fredsColor )

        // Bob traegt Karo        
        Golfer( name == "Bob", 
                name != $unknownsName,
                $bobsPosition : position != $fredsPosition,
                position != $unknownsPosition, position != $joesPosition,                                                  
                $bobsColor : color == "plaid",
                color != $fredsColor, color != $joesColor,
                color != $unknownsColor )

        // Tom ist nicht 1. oder 4., traegt kein Orange
        Golfer( $tomsName : name == "Tom", 
                $tomsPosition : position != 1, position != 4,
                position != $fredsPosition, position != $joesPosition, 
                position != $bobsPosition,                                
                $tomsColor : color != "orange", color != "blue",
                color != $fredsColor, color != $joesColor,
                color != $bobsColor )  

    then
        System.out.println( "Fred " + $fredsPosition + " " + $fredsColor );
        System.out.println( "Joe " + $joesPosition + " " + $joesColor );
        System.out.println( "Bob " + $bobsPosition + " " + $bobsColor );
        System.out.println( "Tom " + $tomsPosition + " " + $tomsColor );   
end    

This rule solves the riddle, but finds two (equal!) solutions - which I leave open for you to solve :-)

Fred 1 orange
Joe 2 blue
Bob 4 plaid
Tom 3 red
Fred 1 orange
Joe 2 blue
Bob 4 plaid
Tom 3 red