Title: The Predicate Student: A Game of Six Integers

Author: webeditor

Date: 19 April 2010 08:57:00 +01:00 or Mon, 19 April 2010 08:57:00 +01:00

Summary: How easily can you solve puzzles? Nigel Eke applies some logic.

Body: 

Dum de dum de dum... boo doo, boo doo choo. Ah Countdown...

Thanks very much Richard Harris for bringing back memories of the Countdown TV show [Harris]. I too became fixated by this TV parlour game, back in the late nineties.

The mathematical section (finding an arithmetic formula using up to six blindly selected numbers to equate to a random goal) became another of my pet projects. Write a program which would be able to find an equation before Carol¹ did.

The approach taken was similar to Richard, but different enough that I thought it worth writing up so that Overload readers can make a comparison. The article also gives a taste of logic programming and, in particular, the logic programming language of Prolog. It is a very quick introduction though, and I would recommend The Art of Prolog [Sterling] for a definitive, and much more detailed, description of the language.

Prolog facts

The Prolog language is based around stating facts, and then making queries on those facts. The facts may be simple (yellow is a colour), or more complex (person A is the granddaughter of person B if one of A's parents is the child of B and A is female). The queries are used for finding unknowns, for example 'who is Elizabeth's father?' or 'let me know all descendants of Elizabeth who have fair hair and were born between 1800 and 1900'. This simple approach is remarkably powerful and expressive for a particular class of problems: those which require searching through many combinations of possible solutions.

Let us start with our first Prolog program - declaring one fact, but otherwise doing nothing:

      colour(yellow).  

yellow is called an atom. colour is known as a fact or a predicate. There are also built-in predicates, which we'll come across later. The name 'colour' selected here is chosen simply so that it does not clash with the built-in names.

How does this program get loaded and what does it mean to 'run' the program? All the examples here are demonstrated in a Prolog interpreter - SWI-Prolog [SwiProlog]. To load a program in SWI-Prolog from the file colour.pl we do the following:

      ?- [colour].  
      % colour compiled 0.00 sec, 492 bytes  
      true.  
 

Simple - and so is running the program:

      ?- colour(yellow).  
      true.  
 
      ?- colour(red).  
      false.  
 

Running the program is simply a matter of testing the stated facts or predicates. Additional facts can be declared dynamically, but we do not touch on this further here.

The first query confirms yellow is a colour by returning a true result. The second query, however, shows that red is not a colour - false was returned. This is because it has not been declared as a fact.

Let's expand the source file, as shown in Listing 1, to declare the fact that more than one colour exists, and make a query for all known colours (Listing 2).

    colour(yellow).  
    colour(cyan).  
    colour(magenta).  
    colour(red).  
    colour(green).  
    colour(blue).  

    ?- colour(X).  
    X = yellow ;  
    X = cyan ;  
    X = magenta ;  
    X = red ;  
    X = green ;  
    X = blue.  
 
    ?- colour(_).  
    true ;  
    true ;  
    true ;  
    true ;  
    true ;  
    true.  

The query colour(X). demonstrates the Prolog convention that variables start with an upper-case character. The output from this query shows X being bound to each of the possible facts.

In this instance we do not go on to use the variable, so it could also have been written as colour(_). However, it can only be determined that the query found six results, but not what the results are.

Deeper facts

The above examples provide an introduction to syntax and some of the terminology used in the language. The next example shows facts with more than one atom, e.g. mother(adam, allison), and conjoined predicates e.g.

      grandmother(Child, Grandmother) :-  
       parent(Child, X), mother(X, Grandmother).  

Let's take these one at a time.

mother(adam, allison) means the fact that 'The mother of Adam is Allison'. So why not write it this way - mother(allison, adam) - and read it as 'Allison is the mother of Adam'. Well, you can do that too, but not in the same program. It is important to use consistent semantics throughout. For the remainder of the family tree examples the semantic meaning behind relation(A, B) is 'B is the <relation> of A'.

So what about the statement:

      grandmother(Child, Grandmother) :-   
        parent(Child, X), mother(X, Grandmother).  

The :- means 'if' and the , is taken to mean 'and'. So the statement reads 'Grandmother is the grandmother of Child if someone (X) is the parent of the Child and Grandmother is the mother of that someone (X)'. This is known as a conjoined predicate.

To program the equivalent of 'or', e.g. the fact that a child's grandparent can be a grandmother or a grandfather, simply write each part of the 'or' as a separate statement.

      grandparent(Child, Grandparent) :-  
      grandmother(Child, Grandparent).  
      grandparent(Child, Grandparent) :-  
      grandfather(Child, Grandparent).  

Bounding along

One of the concepts in Prolog is binding. Variables get values bound to them. What do we mean by binding and being bound? A variable is either bound to a value, or it is not. The variable does not change its value once bound. At least, it does not change until Prolog wants to see if any further facts satisfy the predicate being queried. This happens when a predicate fails or a statement has been fully tested. At this point Prolog steps back through a tree of statement calls it has been recording, until such time it can start creating a new branch of the tree and bind the next value.

Consider the three simple facts:

      fact(1,a).  
      fact(2,b).  
      fact(3,c).  

The predicate can be tested with neither parameter bound, or with either one or both parameters bound (Listing 3). In the case where neither parameter is bound Prolog returns all facts. It initially returns the first fact, binding the variables to the values found in that fact. Once that search has been satisfied, i.e. all unbound variables have been bound to valid, self-consistent values, Prolog backtracks, and looks for the next fact that fits (indicated by the ; in Listing 3), and so on. Similarly for one bound parameter. However, this time, it is possible that none of the facts fit the bound part, in which case false is returned. Finally with both parameters bound, a fact is either found or not found, in which case the original values or false is returned respectively.

    ?- fact(A,B).  
    A = 1,  
    B = a ;  
    A = 2,  
    B = b ;  
    A = 3,  
    B = c.  
 
    ?- C=1,fact(C,D).  
    C = 1,  
    D = a.  
 
    ?- C=4,fact(C,D).  
    false.  
 
    ?- E=1,F=a,fact(E,F).   
    E = 1,   
    F = a.   
 
    ?- E=4,F=a,fact(E,F).   
    false.  

Making a query

You've already seen examples of queries. One was the explicit query for all colours (colour(X)). The other was less obvious and embedded in the fact:

      grandmother(Child, Grandmother) :-  
        parent(Child, X), mother(X, Grandmother).   

In this instance the query is to find X so that it satisfies the parent relationship to Child and Grandmother is the mother of X. The previous section on binding also shows simple queries being made with bound and unbound variables. Now another more complex, and less abstract, example is discussed around the subject of family trees.

Figure 1 shows a family tree, which is then defined in Listing 4 by declaring facts about the people, their genders and immediate relationships (only the first and last of each are shown for brevity). Listing 5 goes on to show the remaining relationship predicates.

Figure 1

    person(alf).  
    /* code removed */  
    person(chuck).   
 
    gender(alf, male).   
    /* code removed */  
    gender(chuck, male).   
 
    father(adam, alf).   
    /* code removed */  
    father(chuck, chris).   
 
    mother(adam, beatrice).   
    /* code removed */  
    mother(chuck, faith).  

    parent(Person, Parent) :- mother(Person, Parent).   
    parent(Person, Parent) :- father(Person, Parent).   
 
    daughter(Person, Daughter) :-  
     gender(Daughter, female),  
     parent(Daughter, Person).   
 
    son(Person, Son) :-  
      gender(Son, male),  
      parent(Son, Person).   
 
    child(Person, Child) :- parent(Child, Person).   
 
    grandmother(Person, Grandmother) :-  
      parent(Person, Parent),  
      mother(Parent, Grandmother).   
 
    grandfather(Person, Grandfather) :-  
      parent(Person, Parent),  
      father(Parent, Grandfather).   
 
    grandparent(Person, Grandparent) :-  
      grandmother(Person, Grandparent).   
    grandparent(Person, Grandparent) :-  
      grandfather(Person, Grandparent).   
 
    granddaughter(Person, Granddaughter) :-  
      gender(Granddaughter, female),  
      grandparent(Granddaughter, Person).   
 
    grandson(Person, Grandson) :-  
      gender(Grandson, male),  
      grandparent(Grandson, Person).   
 
    grandchild(Person, Grandchild) :-  
      grandparent(Grandchild, Person).

So what actually happens when a query is made? Prolog tries to bind any unbound variables in a valid and self-consistent combination of the given facts.

Listing 6 shows a query for all father / child relationships by binding valid combinations to the variables Father and Child.

    ?- father(Child, Father).   
    Child = adam,   
    Father = alf ;   
    Child = denise,   
    Father = clarie ;   
    Child = chris,   
    Father = clarie ;   
    Child = faith,   
    Father = ernie ;   
    Child = darlene,   
    Father = adam ;   
    Child = dawn,   
    Father = adam ;   
    Child = clint,   
    Father = chris ;   
    Child = chuck,   
    Father = chris.  

Listing 7 binds the variable P with the value chris before using the bound value in the father query. This is done twice, once to find his father and once to find his children. Note that P must be bound in each query explicitly.

    ?- P = chris, father(P, Father).   
    P = chris,   
    Father = clarie.   
 
    ?- P = chris, father(Child, P).   
    P = chris,   
    Child = clint ;   
    P = chris,   
    Child = chuck.  

So far we have only used the simple facts stated in Listing 4, but none of the relationships from Listing 5. The final examples of queries (Listing 8) show all Clint's grandparents, whether Dot is one of Clint's grandparents (which she is) or whether Alf is Clint's grandparent (which he isn't). As you can see, the more complex predicates are used in just the same way as the simpler facts.

    ?- P = clint, grandparent(P, Grandparent).   
    P = clint,   
    Grandparent = frida ;   
    P = clint,   
    Grandparent = dot ;   
    P = clint,   
    Grandparent = ernie ;   
    P = clint,   
    Grandparent = clarie.  
 
    ?- P = clint, G = dot, grandparent(P, G).   
    P = clint,   
    G = dot ;   
    false.   
 
    ?- P = clint, G = alf, grandparent(P, G).   
    false.  

You may have noticed the false following the Clint / Dot query. Why is this? Even though Dot is Clint's grandparent and it was even returned as a valid result. Remember though that grandparent is either a grandmother or a grandfather. So the first of the grandparent facts successfully returns that Dot is a grandparent, i.e. when performing the grandmother(Parent, Grandmother) part. But Prolog also goes on to try the second fact, which is determining if Dot is Clint's grandfather - which she isn't - hence the false.

Is this a problem? The answer to that is 'It depends'. It depends on the predicate and if we know whether we need to check the remaining predicate statements.

Cuts

In the case of the grandparent predicate we know that, if the first test proves true then there is no point in checking further cases. This is indicated by introducing a cut (!):

      grandparent(Person, Grandparent) :-  
        grandmother(Person, Grandparent), !.   
      grandparent(Person, Grandparent) :-  
        grandfather(Person, Grandparent).  

Now, when we check if Dot is Clint's grandmother, we get the one expected result:

      ?- P = clint, G = dot, grandparent(P, G).  
      P = clint,  
      G = dot.  

Tree hugging

As Prolog has been solving the queries given to it, it builds a tree of possible results. It is this tree building, walking and searching that makes it an ideal candidate language for the original problem - the Countdown equation finder.

The first search tree is to determine a list of all possible permutations of the six numbers. This is not just permutations on the six numbers, but also all combinations of five from the six, four from the six numbers and so on. (Not all six numbers need to be used when deriving an equation).

The program works through each of these permutations, building a tree representing an equation. Figure 2 depicts the trees for two equations ( 2 + (3 x 4) [a] and (2 + 3) x 4 [b] ). The root of each tree is an operator and the left and right branches are the operands. Once a tree is built, the program then tests to see if the equation equals the required goal.

Figure 2

Before we look at the actual program however, one final Prolog concept needs to be introduced - lists.

Lists

Prolog's list syntax uses the [ and ] characters to define the beginning and end of a list, with the pipe | character delimiting one or more initial elements and separating them from the remaining tail of the list. Also by convention [] is the empty list.

Three predicates are shown in the program (Listing 9), all of which take a list as an argument, but access it differently. The first just prints the object (it could in fact be any object). The second and third extract one and two head elements and print them separately before printing the remaining tail.

    fact(a).   
    fact(b).   
    fact(c).   
    fact(d).   
    fact(e).   
    fact(f).   
 
    print_list(Ls) :-   
      print(Ls),   
      print('\n').   
 
    print_head1_list([H|Ls]) :-   
      print(H),   
      print('\n'),   
      print(Ls),   
      print('\n').   
 
    print_head2_list([H1,H2|Ls]) :-   
      print(H1),   
      print('\n'),   
      print(H2),   
      print('\n'),   
      print(Ls),   
      print('\n').  

Listing 10 shows the output from calling these predicates with a simple list, including the results of calling the predicates with a list shorter than two elements.

    ?- Xs=[1,2,3,4,5,6], print_list(Xs).   
    [1, 2, 3, 4, 5, 6]   
    Xs = [1, 2, 3, 4, 5, 6].   
 
    ?- Xs=[1,2,3,4,5,6], print_head1_list(Xs).   
    1   
    [2, 3, 4, 5, 6]   
    Xs = [1, 2, 3, 4, 5, 6].  
 
    ?- Xs=[1,2,3,4,5,6], print_head2_list(Xs).   
    1   
    2   
    [3, 4, 5, 6]   
    Xs = [1, 2, 3, 4, 5, 6].   
 
    ?- Xs = [1], print_list(Xs).   
    [1]   
    Xs = [1].   
 
    ?- Xs = [1], print_head1_list(Xs).   
    1   
    []   
    Xs = [1].   
 
    ?- Xs = [1], print_head2_list(Xs).   
    false.   
 
    ?- findall(X, fact(X), Xs), print_head2_list(Xs).   
    a   
    b   
    [c, d, e, f]   
    Xs = [a, b, c, d, e, f].

Finally the built-in predicate findall is demonstrated, which finds argument one, satisfying the predicate (argument two), and returns them in a list (argument three). (For this example note the fact facts declared at the start of the program).

Countdown to Countdown

At last we have enough Prolog behind us to allow us to look at the Countdown program (Listing 11). The main two predicates that solve the problem are operation and findTree. That's seven statements, or eleven lines of code. This shows the power of Prolog for this type of problem solving.

    /* Helper function for subsets/2 */   
    subsets2(Xs, Xs).   
    subsets2(Xs, Ys) :- select(_, Xs, Ys).   
    subsets2(Xs, Ys) :- select(_, Xs, Y1s), subsets2(Y1s, Ys).   
 
    /* Find all subsets 0 of N, 1 of N .. N of N for the list Xs */   
    subsets(Xs, Xss) :-   
      findall(Ys, subsets2(Xs, Ys), Yss),   
      list_to_set(Yss, Xss).   
 
    /* Find value of each of the four arithmatical operations */   
    operation(O1, O2, V, ' + ') :- V is O1 + O2.   
    operation(O1, O2, V, ' - ') :- V is O1 - O2, V > 0.   
    operation(O1, O2, V, ' * ') :- not(O1 = 1), not(O2 = 1), V is O1 * O2.   
    operation(O1, O2, V, ' / ') :- not(O2 = 1), M is O1 mod O2, M = 0, V is O1 // O2.   
 
    /* Build equation trees from given list. If goal is bound then only trees which match the goal are deemed successful. */   
    findTree([], _, _) :- !, fail.   
    findTree([X|[]], value(X), X) :- !.   
    findTree(Xs, tree(O, TL, TR), V) :-   
      append(L, R, Xs),   
      not(compare(=, L, Xs)), findTree(L, TL, V1),   
      not(compare(=, R, Xs)), findTree(R, TR, V2),   
      operation(V1, V2, V, O).   
 
    /* Helper for building equation text. */   
    makeExpr(L, O, R, E) :-   
      concat('(', L, E1),   
      concat(E1, O, E2),   
      concat(E2, R, E3),   
      concat(E3, ')', E).   
 
    /* Return equation text for given operations tree. */   
    treeExpr(value(X), X).   
    treeExpr(tree(O, L, R), E) :-   
      treeExpr(L, Le),   
      treeExpr(R, Re),   
      makeExpr(Le, O, Re, E).   
 
    /* Helper function to sort lists of subsets of the choosen numbers based on list length. */   
    delta_length('<', Xs, Ys) :-   
      length(Xs, XL),   
      length(Ys, YL),   
      compare(<, XL, YL), !.   
    delta_length('>', _, _).   
 
    /* Main predicate. Expects Vn and Goal to be bound when called. */   
    countdown(V1, V2, V3, V4, V5, V6, Goal, E) :-   
      subsets([V1, V2, V3, V4, V5, V6], Xss),   
      predsort(delta_length, Xss, Yss),   
      member(Ys, Yss),   
      permutation(Ys, Y1s),   
      findTree(Y1s, T, Goal), !,   
      treeExpr(T, E).   
 
    countdown(_, _, _, _, _, _, _,  
      'It''s impossible').  

In summary, we have the following predicates which form the entire program:

• subsets and subsets² - finds all subsets of all combinations of 1 from 6, 2 from 6 through to all 6 numbers.
• operation - performs each of the four arithmetic operations permitted in the final equation.
• findTree - finds all possible equation trees.
• makeExpr and treeExpr - helper predicates to create the equation text to be output.
• delta_length - helper predicate to enable the shortest list of numbers to get checked first and give the most efficient equation, i.e. the one using the minimum number of numbers.
• countdown - the real goal of the game.

Countdown and lift-off

So how do each of these predicates work?

subsets2

subsets2 enables us to find subsets of a set. subsets2 should be seen as a 'private predicate' of subsets, and is not designed to be called by other predicates2.

The first statement simply states a set (Xs) is a subset of itself.

The second statement gets all subsets (Ys) of length N-1 from set Xs (length N). This is done with the help of the built-in predicate select, which selects a member (not used, hence _) from Xs, giving the remaining set Ys.

The final statement gets all subsets (Ys) of length N-n, where n > 1, from set Xs (length N). First we get all subsets (Y1s) of length N-1 from set Xs, as before, but then pass this result, recursively into subsets2, to get the subsets of Y1s. It is as result of this recursion that we generate duplication - which is removed in our subsets predicate.

subsets

Here we return a 'set of sets' (Xss). The 'set of sets' returned is actually the set of subsets of Xs.

findall is used to find a temporary list of subsets (Yss) of all Xs which match the predicate subset2. subsets2(Xs, Ys) binds each subset of Xs to Ys. findall takes each result Ys, and adds it to its result list Yss.

We know, because of way subsets2 is written, that the list Yss contains duplicate subsets. list_to_set is a built-in predicate that removes the duplicates in Yss, binding the result we are after to Xss.

operation

Each of of the four allowed mathematical operations are handled here, with operation(operand1, operand2, resultantValue, operatorString). The operands are always bound when this predicate is tested.

resultantValue gets bound to the result of the calculating the operation. There is one circumstance when resultantValue is already bound - which is discussed further when we look at the main countdown predicate.

The string representing the operation (operationString) is also bound on return from the predicate, in order to be used when printing out the final equation.

The minus operation dismisses negative results. Although they could be used as interim results in finding the final goal we know that a) the final goal will always be positive, and b) the operands can be re-arranged with the plus operator to achieve the same - and seemingly cleaner, as far as the final equation appears - result. So, for A - (-B) the equivalent A + B will also appear in the possible equation trees. Similarly for A + (-B), which becomes A - B, i.e. we never have to deal with a negative B value.

The multiplication operation dismisses the uninteresting operand one because 1 * N = N * 1 = N.

The division operation dismisses the uninteresting case where N / 1 = N. It also makes sure that the result is non-fractional.

findTree

This is the crux of the program. The part that does the real work in finding an equation to match the goal.

The format of the predicate is findTree(listOfOperands, tree, value). The listOfOperands is always bound when the predicate is tested. The tree will be a representation of the operation tree (see Figure 2). value gets bound to the value of the result of the tree's operations being applied.

The first statement dismisses the empty list of operands, by failing straight-away.

The second statement deals with the leaf of the tree. When there is only one element in the list of operands (determined by [X|[]]) the 'leaf' gets returned in the tree as value(X), and the actual value is clearly X.

The third statement deals with lists of more than one element, i.e. those where operations can be applied. Note that we know this predicates is being passed a list with more than one element, because the previous two statements used the cut (!), to indicate the zero-length and unary length cases have been fully dealt with.

We use the built-in predicate append to enable us to easily split the given list into left and right branches of the tree.

Given the statement append(As,Bs,Cs), if As and Bs were bound then Cs would be the concatenation of the previous two. However when Cs is bound (as in this case with Xs) and the others are not, append returns all the possibilities of As and Bs which, when concatenated, would form Cs.

Given two lists (L and R), we have operands that can go on to be used in the left branch and right branch of the expression tree respectively. After dismissing the case when L is Xs (R is empty), which would cause an infinite recursion, the left tree (TL) is built up. This is done as a recursive call on findTree, but this time just using part of the original list of operands. Similarly the right tree (TR) is also built up.

Finally, given the two sub-trees TL and TR, all operations can be applied on them, and we return their value V, and the string of the equation (O) that is represented by that operation being applied on the subtrees. This all gets magically bound to the result tree in the bound response tree(O, TL, TR).

makeExpr

This is used by treeExpr when the program comes to print out the final result. It concatenates a left expression string (L), operation string (O) and right expression string (R), together with wrapping brackets, to bind to a final expression, E.

treeExpr

This is called once the final result goal has been found, and will build up an expression string from the result tree. It takes the form treeExpr(treeOrLeaf, expressionString).

The first statement deals with the leaf case, where the value is simply represented in string form.

The second statement deals with the tree. It calls itself recursively to find the expression for the left and right branches of the tree (L and R respectively). It then calls makeExpr to form the final expression from the left branch's expression (Le), the operation (O) at the root of the tree, and the right branch's expression (Re).

delta_length

delta_length is used at the start of the program so that the smallest sets of numbers are initially checked to see if they can be used to form the goal. It provides the compare(Operator, Operand1, Operand2) interface that is required by the built-in predicate predsort (see later).

length(List, Length) is a built-in predicate that binds Length to the length of List.

compare is a built-in predicate that, in this case, enables us to check if Xs is shorter than Ys.

The second statement for delta_length always returns a greater than operator, even in the cases when the lists are the same length, i.e. we are not worried about sort order for equal length lists.

countdown

This predicate forms the control of the game. The first statement tries to match the given goal. The second statement is the catch-all, if there is no solution.

Taking the lines in the first statement one by one, the following is performed:

1. Generate a list of all subsets (Xss) of the list of the six numbers provided ([V1, V2, V3, V4, V5, V6]).
2. Sort the list of subsets into order based on the length of the subset. The sorted list is Yss.
3. Take each subset (Ys) in turn.
4. For each of the subsets (Ys) we look at every permutation of numbers (Y1s). Note that permutation is another built-in predicate. We look at permutations of numbers because the order of numbers in an expression is important, for example we need to try A / B and B / A.

5. Now find a tree whose value matches the supplied goal. This is the point mentioned earlier, where findTree is called with the already bound Goal value. This step of the predicate fails when the generated tree does not match the goal. Prolog then backtracks to try the next tree. Failing to match all those trees the next permutation is tried and, failing all permutations, the next subset of numbers.

   If we do find a tree, whose value matches the goal we know the end result has been found. We declare this with the cut (!), which stops the program from trying the 'It's impossible' statement.

6. Finally, having found an expression tree which will match the goal, the expression string is generated so that the result can be seen in a more readable form.

A final note

SWI-Prolog provides interfaces through to C programs. The original program provided a GUI interface enabling the user to enter the six numbers and goal, before calling the Prolog logic to find the equation.

The program was even sent to the TV program for a mention but, alas, they didn't want to replace Carol by a computer. But then again, who would?

Acknowledgements

With much thanks to Mingyuan Mu and Jacqui Alexander for proof reading this article, and to Ric Parkin and Richard Harris who provided valuable feedback.

References and further reading

[Harris] Harris, R., 'The Model Student: A Game of Six Integers [Part 1]', Overload 95, Feb 2010.

[Sterling] Sterling, L. & Shapiro, E., The Art of Prolog, MIT Press, 1986. ISBN 0-262-69105-1.

[SwiProlog] http://www.swi-prolog.org/

1 Carol Vorderman - Countdown, 1982-2008

2 As far as I'm aware, Prolog has no way to make predicates private.

Notes: 

More fields may be available via dynamicdata ..