Coding N Stuff

In this chapter, we are going to build a small prolog program to solve a very common and simple puzzle, known as the magic square. To keep it simple, we are going to use only a 3×3 square, although the same solution applies to any possible size. If you have been following this tutorial, you may remember the takeout function defined in the previous chapter. We are going to need it, so if you are planning to follow the examples, you can start by copying it to a new prolog file.

So, lets start by analyzing the problem. A 3×3 magic square, is basically a 3×3 grid filled with distinct numbers from 1 to 9, which sums on every row and every column is 15. What we are looking for is a function that given a certain unfinished grid, would give us the solution (or possible solutions), or false in case there is no solution. For the sake of simplicity, we are going to represent a grid by a list of 9 numbers. It would be more logical to use a list composed by three lists of numbers, but that would make the solution a bit more complicated, so for the purpose of this tutorial we are going to stick with the nine numbers list. A possible structure for the main function would be:

solve(Puzzle, Result) :-
               generate_grid(Puzzle, Result),
               is_correct(Result).

Looks simple huh? So lets start by the simplest task, the is_correct function which validates a possible solution:

is_correct([A,B,C,D,E,F,G,H,I]) :-
               15 is A+B+C, 15 is D+E+F, 15 is G+H+I,
               15 is A+D+G, 15 is B+E+H, 15 is C+F+I.

No special magic here, given a list of nine elements, it just compares every possible row and column of our virtual grid with 15. A query to this function will only evaluate to true if the solution is correct. We started from the finish, so lets continue backwards, lets create the generate_grid function, which given a certain unfinished grid, generates a finished one just filling the holes without testing the solution (that is the job of the is_correct function). This is a preliminary sketch:

generate_grid([],Result,Result).
generate_grid(NumbersList, P, Result) :-
               takeout(N, NumbersList, NewNumbersList),
               generate_grid(NewNumbersList, [N|P], Result).

Now just take a look to a possible usage in a SWI console session:

4 ?- generate_grid([1, 2, 3, 4, 5, 6, 7, 8, 9], [], Grid).
Grid = [9, 8, 7, 6, 5, 4, 3, 2, 1] ;
Grid = [8, 9, 7, 6, 5, 4, 3, 2, 1] ;
Grid = [9, 7, 8, 6, 5, 4, 3, 2, 1] ;
Grid = [7, 9, 8, 6, 5, 4, 3, 2, 1] ;
Grid = [8, 7, 9, 6, 5, 4, 3, 2, 1] ;
Grid = [7, 8, 9, 6, 5, 4, 3, 2, 1] ;
Grid = [9, 8, 6, 7, 5, 4, 3, 2, 1] ;
Grid = [8, 9, 6, 7, 5, 4, 3, 2, 1] .

We could have continued and every imaginary grid would be generated. You may think that this is a very simplistic approach, because we are passing the possible numbers in a list, and you’re right, but this has some advantages that I’m not going to discuss for now. Also, the function is not very friendly, because we have to pass the list of numbers as well as  an empty list just to get the result. That’s true, but this function will be for internal use only, anyway, I’ll show you how to “hide” those extra arguments in a moment. Now lets analyze it. We have two distinct signatures for the function. We’ll skip to second one before explaining the first one.

The first argument is as discussed before a list of possible numbers to fill the grid with. The second argument is a placeholder list, we’ll use it to hold the numbers taken from the first list. The last argument is the pretended result. The first line of the function body is a call to the takeout function. Besides serving to remove items from a list, this function has many other usages, one of them is if we only provide the middle argument (the list), the first argument will be filled with an item from the list and the second argument with the remaining list, we can use this “feature” to retrieve all possible combination of taken item / stripped list. That’s what we’re doing on the generate_grid function, we provide the NumberList, and we get N (an item from the list), and NewNumbersList (the stripped list). Next we have a recursive call to generate_grid, with the NewNumbersList, a new placeholder list composed by the taken number as head and the current placeholder as tail, and again the pretended result as arguments.

Finally, when all numbers are taken out the number list we get an empty list, so the recursive call will match the first signature, that expects an empty list as the first argument, and will match the passed placeholder to the pretended result.

But this is not what we really want, what we really need is a function that gets an unfinished grid and completes it. So lets modify the  generate_grid function:

generate_grid([],[], Result,Result).
generate_grid(NumbersList, [Cell|Tail], P, Result) :-
               Cell == u ->
                    (
                      takeout(N, NumbersList, NewNumbersList),
                      generate_grid(NewNumbersList, Tail, [N|P], Result)
                    ); (
                      takeout(Cell, NumbersList, NewNumbersList),
                      generate_grid(NewNumbersList, Tail, [Cell|P], Result)
                    ).

Here’s a sample usage:

2 ?- generate_grid([1, 2, 3, 4, 5, 6, 7, 8, 9], [u, u, 4, u, 5, u, u, 2, u], [], Grid).
Grid = [9, 2, 8, 7, 5, 6, 4, 3, 1] ;
Grid = [8, 2, 9, 7, 5, 6, 4, 3, 1] ;
Grid = [9, 2, 7, 8, 5, 6, 4, 3, 1] ;
Grid = [7, 2, 9, 8, 5, 6, 4, 3, 1] ;
Grid = [8, 2, 7, 9, 5, 6, 4, 3, 1] ;
Grid = [7, 2, 8, 9, 5, 6, 4, 3, 1] ;
Grid = [9, 2, 8, 6, 5, 7, 4, 3, 1] .

We just pass the unfinished grid as an argument, with the empty cells marked with an u atom. Note that the numbers passed in the unfinished grid are always present. But it appears that the result list is in reverse order, for example number 4 is the third one from the left in the unfinished grid, but is the third from the right in the results. This happens because we’re “prepending ” and not appending the values in the placeholder. We can build a prepend function, but I think it will be more easy and performant to build a reverse function and just reverse the result. I’m not going to explain it, if you understood the previous examples, this one should be pretty straightforward. Here it is:

reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W).
reverse([],X,X).

And now a sample usage:

3 ?- reverse([1, 2, 3], [], Reversed).
Reversed = [3, 2, 1].

Once again that ugly placeholder. Lets hide it then:

reverse(L, R) :- reverse(L, [], R).
reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W).
reverse([],X,X).

We just add a new function signature which only expects two arguments and then makes a recursive call with the correct number of arguments. Simple huh? Now we just need to make some retouches on the first signature of the generate_grid function to make it reverse the final result:

generate_grid([],[], P,Result) :- reverse(P, [], Result).

Lets add a new signature to hide the extra arguments:

generate_grid(Unfinished, Result) :- generate_grid([1, 2, 3, 4, 5, 6, 7, 8, 9], Unfinished, [], Result).

And a sample usage:

7 ?- generate_grid([u, u, 4, u, 5, u, u, 2, u], Grid).
Grid = [1, 3, 4, 6, 5, 7, 8, 2, 9] ;
Grid = [1, 3, 4, 6, 5, 7, 9, 2, 8] ;
Grid = [1, 3, 4, 6, 5, 8, 7, 2, 9] ;
Grid = [1, 3, 4, 6, 5, 8, 9, 2, 7] ;
Grid = [1, 3, 4, 6, 5, 9, 7, 2, 8] ;
Grid = [1, 3, 4, 6, 5, 9, 8, 2, 7] ;
Grid = [1, 3, 4, 7, 5, 6, 8, 2, 9] ;
Grid = [1, 3, 4, 7, 5, 6, 9, 2, 8] ;
Grid = [1, 3, 4, 7, 5, 8, 6, 2, 9] ;
Grid = [1, 3, 4, 7, 5, 8, 9, 2, 6] ;
Grid = [1, 3, 4, 7, 5, 9, 6, 2, 8] ;
Grid = [1, 3, 4, 7, 5, 9, 8, 2, 6] ;
Grid = [1, 3, 4, 8, 5, 6, 7, 2, 9] ;
Grid = [1, 3, 4, 8, 5, 6, 9, 2, 7] ;
Grid = [1, 3, 4, 8, 5, 7, 6, 2, 9] .

So here’s the entire code for the final solution:

takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).
 
reverse(L, R) :- reverse(L, [], R).
reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W).
reverse([],X,X).
 
solve(Puzzle, Result) :-
               generate_grid(Puzzle, Result),
               is_correct(Result).
 
generate_grid(Unfinished, Result) :- generate_grid([1, 2, 3, 4, 5, 6, 7, 8, 9], Unfinished, [], Result).
generate_grid([],[], P,Result) :- reverse(P, [], Result).
generate_grid(NumbersList, [Cell|Tail], P, Result) :-
               Cell == u ->
                    (
                      takeout(N, NumbersList, NewNumbersList),
                      generate_grid(NewNumbersList, Tail, [N|P], Result)
                    ); (
                      takeout(Cell, NumbersList, NewNumbersList),
                      generate_grid(NewNumbersList, Tail, [Cell|P], Result)
                    ).
 
is_correct([A,B,C,D,E,F,G,H,I]) :-
               15 is A+B+C, 15 is D+E+F, 15 is G+H+I,
               15 is A+D+G, 15 is B+E+H, 15 is C+F+I.

And a sample solved puzzle:

11 ?- solve([8, u, u, u, 5, u, u, u, u], Result).
Result = [8, 1, 6, 3, 5, 7, 4, 9, 2] ;
Result = [8, 3, 4, 1, 5, 9, 6, 7, 2] ;
false.
 
%this one has two solutions
 
12 ?- solve([u, 8, u, u, 7, u, u, u, u], Result).
false
 
%this one does not have a solution

Now you may be asking, how the hell did prolog knew the correct answer. Well, it didn’t, it just tried every possibilities until it found a match. And where did we instruct it to do it? We didn’t… When prolog evaluates an expression, and it sees that expression has more than one possible result, if later in the program some other expression fails, it goes back to the multi result expression and tries another possible result, until it gets to finish the execution with all expressions evaluated to true, or until every possible combinations have been tried with no success. That’s what happens with the solve function. The generate_grid function has many possible results. Prolog tries one, and continues to the is_correct function. If the result is not correct, prolog goes back and tries another possible solution from the generate_grid function. As soon it finds a solution that passes the is_correct validation, that is assumed to be the final result.

This is kind of a brute force artificial intelligence. A perfect solution would introduce some kind of mid term validation, or some more fancy logic, but I’ll leave that for the next chapters.

Cheers

This is the continuation of my introductory tutorial on prolog. Here I’m going to explain how we can use lists (commonly known as arrays) in prolog, and also make my best efforts to explain how functors (functions) work. Prolog can be a very tricky beast to understand for programmers who are used to more traditional languages, so, if you fit in that category, be prepared because there will be some stuff here that will require a good amount of thinking.

If you ever worked with lisp, everything regarding lists here should make sense almost immediately. The list constructor is as in most language, a pair of square brackets containing zero or more items separated by commas. But there is no such thing as retrieving an element from a list by its index, like some_list[i], all you are give to know in a list is its head and its tail, represented by [H|T]. Confused? Not in a couple of minutes. Consider the following simplistic list:

[1, 2, 3]

Here, head is the number 1, and tail is [2,3]. The head is always the first element of the list, and the tail is the remaining of the list. We can continue here saying that the head of [2,3] is 2, and the tail is [3] which as a head and tail of 3 and [] respectively. So as you can see,  the tail is always a list, even if it only contains one or zero elements. But an empty list does not contain neither a head or a tail. Consider the following functors borrowed from lisp:

car([H|T], H).
cdr([H|T], T).

Take car for example. What we got here is something that says, given a list in the first argument, the second argument must match its head to get a positive answer. So, given the way prolog works, we can use it in many ways. Here’s a sample SWI session after consulting a file containing those definitions:

1 ?- car([a, b, c], a).
true.
 
2 ?- car([a, b, c], z).
true.
 
3 ?- car([1, 2, 3], H).
H = 1.
 
4 ?- car([H | [2, 3]], 1).
H = 1.

The first query is simple, we’re just matching a list to what we think is it’s head. Obviously the answer is true. The second query is the same, except that we provide an invalid head, so, the answer is false. In the third, we provide a list, but an unknown value as tail, a variable (if you skipped the first part, a variable always starts in upper case, while a lower case word is known as an atom, and works almost like a string but without the quotes). So, what prolog does, in order to evaluate the functor to true, is to match the variable to the head of the list, as declared on the functor prototype. The last query works almost like the former, except that this time we have an unknown head in the list, but we provide it in the second argument of the function, so prolog does the math and shows us what we’re looking for. Of course those examples are a bit useless, but they’re just for demonstration.

Many prolog implementations ship with some functions to deal with lists, but others don’t, so let’s build some of them. First, lets create a member function to evaluate if a certain value belongs to a list:

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

Those are two distinct functors (or functions) with the same name. Prolog always starts by evaluating the first, if it fails, it fallbacks to the next with the same name, and so on… The first one in our example means something like: given a value and a list whose head equals that value and whose tail we don’t care (an underscore is known in prolog as a don’t care variable, meaning that we want something there, but we don’t care what it is), because there is no body, evaluate to true. The second definition means: given a value, and a list whose head we don’t care (we already tested the situation where the value and the head of the list match in the first definition) and a known tail, the result is another call (a recursive call) to member, using the value and the tail as arguments. This is hard to explain, but take a look of whats happening under the hoods when we make a call to member(3, [1, 2, 3, 4]):

%try the first definition:
member(3, [1|_]).
%false, fallback to the second
member(3, [_|[2, 3, 4]).
%call member(3, [2, 3, 4]).
 
%try the first definition:
member(3, [2|_]).
%false, fallback to the second
member(3, [_|[3, 4]).
%call member(3, [3, 4]).
 
%try the first definition:
member(3, [3|_]).
%true, end of recursion, true is the final answer

Uff, prolog can be tricky to understand, but try to explain it

Next stop is a function that takes a value out of a list. This is all about recursion too, so take your time to analyze it:

takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

So let me try to explain this. Once again we have two functions with the same name, you already know the fallback rule. The first definition means: Given a value X as the first argument and a list composed by a head matching X and a tail matching the third argument R evaluate to true, we’ll usually use the third argument as a result, so, we can rephrase that to given a value X and a list whose head is X the result will be the list tail. The second definition is again a recursive definition, and is even harder to explain: given a value X, and a list with head F and tail R, the result will be a list composed by a head matching F and a tail S, which is retrieved in the recursive call with arguments X (the value to take), R (the tail of the subject list, we don’t need the head because we already know it doesn’t match with X) and S (the result to be appended to the previous call result).

Now I managed to confuse myself Here’s another scheme representing a call to takeout(3, [1, 2, 3, 4], R):

%try the first definition
takeout(3, [1 | [2, 3, 4]], R).
%false, try the second
takeout(3, [1 | [2, 3, 4]], [1 | S]).
%S is the third argument of calling takeout(3, [2, 3, 4], S).
%so the result will be a list composed by 1 as head and S as tail
 
%try the first definition
takeout(3, [2 | [3, 4]], R).
%false, try the second
takeout(3, [2 | [3, 4]], [2 | S]).
%S is the third argument of calling takeout(3, [3, 4], S).
%so the result will be a list composed by 2 as head and S as tail
 
%try the first definition
takeout(3, [3 | [4]], R).
%it's a match, the result is [4], which is the tail of the previous call,
$and so on, ending with a final result of [1, 2, 4]

Finally, let me just explain one thing. What happens if either the member or the takeout function have arguments that can’t be unmatched? That’s easy, remember that an empty list does not have a head or a tail. Both function have recursive calls, that reduce the list one element at a time. If the arguments are unmatched, what happens is that we’ll end up with a call using an empty list, both all the function signatures expect lists with heads and tails, so, prolog won’t find any matching definition based on that arguments and it will fail with a false.

This finalizes this second part, and what’s probably the most difficult post I ever had to write. And I still got a feeling that I couldn’t manage to make myself clear. Next chapter will give a first look on artificial intelligence, we’ll create a prolog program to solve a simple puzzle. See you then.

Cheers