Prolog Sudoku Solver Explained

Note: This is a follow-up blog post on Adventures In Declarative Programming: Sudoku Solver.

Prolog

The main language used in logic programming is Prolog, which name is derived from "PROgramming in LOGic". And that's exactly what it does: It allows you to program in terms of logic. The funny thing is that it doesn't actually solve problems really logical, as you'll see in this post.

Prolog was at first invented for computional linguists to do natural language processing, but its applications spreaded far over time. An extract from Wikipedia: "[...] theorem proving, expert systems, games, automated answering systems, ontologies and sophisticated control systems."

Therefore, Prolog can nowadays be seen as a high-level tool for solving logical problems (to what natural language understanding can be narrowed down too).

Knowledge Base

In Prolog you're describing your problem in terms of relations, which consist of facts and rules. Facts and rules together build up a knowledge base, which can be queried to get results to your problem.

That's how a simple knowledge base could look like:

human(socrates).         % facts about who is human
human(aristotle).
human(plato).

god(zeus).               % and who is a god
god(apollo).

mortal(X) :- human(X).   % a logical assertion (rule) that X is mortal if X is human

In this example we can see five facts and one rule. Some sample queries could look like this:

user@host> swipl -f kb.pro
% /path/to/kb.pro compiled 0.00 sec, 8 clauses
?- human(plato).      % is plato a human?
true.

?- god(X).            % who is a god?
X = zeus ;
X = apollo.

?- mortal(socrates).  % is socrates mortal?
true.

?- mortal(zeus).      % is zeus mortal?
false.

?- mortal(Y).         % who is mortal?
Y = socrates ;
Y = aristotle ;
Y = plato.

Prolog can answer our queries by using unification and proof search (including backtracking).

Unification

In the example above Prolog unified X with zeus and apollo and Y with socrates, aristotle and plato. But what exactly does this mean?

Prolog knows three types of terms:

• Constants: Either atoms (plato) or numbers (42).
• Variables: Always start with an uppercase letter (X, Head, A42, ...)
• Complex terms: Have the form functor(term_1, ..., term_n).

plato and plato unfiy because they are the same atom; 42 and 42 unify because they are the same number; X and X unify because they are the same variable; human(plato) and human(plato) unify because they are the same complex term.

Constants and variables can unify if the variable has the same value as the atom or the number. god(zeus) and god(X) unify by assigning X the value zeus.

A precise definition of unification from the Learn Prolog Now tutorial:

1. If term1 and term2 are constants, then term1 and term2 unify if and only if they are the same atom, or the same number.
2. If term1 is a variable and term2 is any type of term, then term1 and term2 unify, and term1 is instantiated to term2 . Similarly, if term2 is a variable and term1 is any type of term, then term1 and term2 unify, and term2 is instantiated to term1 . (So if they are both variables, they’re both instantiated to each other, and we say that they share values.)
3. If term1 and term2 are complex terms, then they unify if and only if:
1. They have the same functor and arity (number of arguments a complex term takes), and
2. all their corresponding arguments unify, and
3. the variable instantiations are compatible. (For example, it is not possible to instantiate variable X to mia when unifying one pair of arguments, and to instantiate X to vincent when unifying another pair of arguments .)
4. Two terms unify if and only if it follows from the previous three clauses that they unify.

Proof Search

If we remember our knowledge base about humans and gods again and especially the rule mortal(X) :- human(X). we can try to understand how Prolog solves this.

Prolog knows that in order to solve mortal(X) it only has to unify human(X) with something. It looks into the knowledge base and search from top to bottom for possible unifications. As it encounters human(socrates) it has found a possible solution by unifying human(X) with human(socrates). Therefore X = socrates and that's our first answer (actually it's Y = socrates in our sample queries, because Y is the same as the X inside the rule). If we ask for another solution by pressing ; Prolog goes on in the knowledge base and finds the other humans.

Everytime Prolog unifies a variable with a term while doing proof search, it remembers this as a choice point. If Prolog finds out it made a mistake, it reverts back to the last choice point and tries to unify the variable with some other term. This process is called backtracking and is fundamental for finding solutions in Prolog.

Sudoku Solver

In one of my previous blog posts I wrote about a Sudoku Solver written in 15 lines of code using SWI-Prolog and the CLPFD library. Let's recall the code:

:- use_module(library(clpfd)).

sudoku(Rows) :-  
  append(Rows, Vs), Vs ins 1..9,
  maplist(all_distinct, Rows),
  transpose(Rows, Columns),     
  maplist(all_distinct, Columns),     
  Rows = [A,B,C,D,E,F,G,H,I],     
  blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),     
  maplist(label, Rows).      

blocks([], [], []).       
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-     
  all_distinct([A,B,C,D,E,F,G,H,I]),      
  blocks(Bs1, Bs2, Bs3)

Now, as you understand the basic concepts of Prolog, I can explain the Sudoku solver in greater detail to you. But before I do so one short note about a notation used in the following lines. Whenever there is a predicate name mentioned, it's followed with a / and a number, indicating its arity (number of arguments it takes).

Line 1: "Include" the library CLPFD (Constraint Logic Programming over Finite Domains). This library basically allows us to make use of the domains coming up on Line 4.

Line 3: The solving predicate sudoku(Rows) takes a list of list as argument.

Line 4: Use of 'append/2' to insert Domains into our lists. A domain is like a variable without a concrete value, but with a range of possible values: In this case 1 to 9 as ensured by 'ins/2' from the CLPFD.

Line 5: With 'maplist/2' we call the predicate 'all_distinct/1' from the CLPFD library on all lists inside the list Rows. 'all_distinct/1' makes sure that every value in the list just occures once, as forced by the rules of Sudoku.

Line 6: The next step is to 'transpose/2' the Rows into Columns, which is again part of the CLPFD library.

Line 7: Then we use 'all_distinct/1' again to make sure all numbers just occur once in the Columns.

Lines 8-9: Convert Rows in 3x3 Blocks and checks whether they are 'all_distinct' using our self-defined predicate 'blocks/3' (see Lines 12-15).

Line 10: Again usage of 'maplist/2' to call the predicate 'label/1' on our Rows. 'label/1' makes sure all the domains have one concrete value - just in case there are more than one solutions to the Sudoku puzzle given.

Line 12: A simple fact expressing that our predicate is true when it gets three empty lists as input. This is the escape point for the recursion following now. (Note that it's very important that this is defined before and not after Line 13, because Prolog will always use this complex term for 'blocks/3' as the first one, since it's reading the knowledge base from top to bottom.)

Line 13: Prolog will use this rule if 'blocks/3' is supplied with non-empty lists. By the use of the pipe ( | ) we split up the given rows into their first three elements and the rest (so called tail) we want to use later.

Line 14: Now we're having a 3x3 block consisting of  three elements from each row originally given to 'blocks/3' in 'sudoku' at Line 9. And again we're making sure that every number just occurs once in this 3x3 block by using 'all_distinct/1'.

Line 15: Going into recursion with the rest of the list (until they are splitted up to empty lists).

Most of the backtracking is probably happening inside 'all_distinct/1'. This is where Prolog unifies the variables inside the Rows, Columns and 3x3 blocks with the numbers from 1 to 9. Sometimes it just has to backtrack a few variables, sometimes just a few rows and maybe it even has to start all over again from the very beginning, when it made a mistake unifying the first variable.

If you look at Prolog from a more procedural perspective, it might not be always the most efficient or performant way to get to the solution, but it makes solving easy logical problems easy and solving hard logical problems possible. It's all about simplicity and clearness, which is very important in my opinion.

There are of course a lot of interesting algorithms out there to solve Sudoku puzzles, some of them being much more efficient than this one, but this solution is interesting too - maybe not that much from a procedural perspective, but from a perspective focused on clearness and simplicity.

Why Should I Learn Prolog?

Even though this might be clear to most programmers, I want to point it out.

Learning new programming languages make you a better programmer. And it especially does if learning a new language includes a new way of thinking - such as the declarative programming in Prolog.

As Paul Graham explained in his essay Beating The Averages, you will start thinking about problems from a new perspective. The more perspectives you have, from which you can look at a problem and the more languages you have, in which you can think about a problem, the better your solution will be.

If you haven't read Beating The Averages yet, I highly recommened to do so now (or at least the paragraph about The Blub Paradox).

Sources

http://www.amzi.com/articles/prolog_under_the_hood.htm
http://www.learnprolognow.org/



Discussion on Reddit: r/coding