SyntaxHighlighter

July 22, 2012

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

July 15, 2012

SWI-Prolog SyntaxHighlighter Brush

My last blog post about a Sudoku solver written in SWI-Prolog motivated me to create a custom brush for the JavaScript SyntaxHighlighter, which helps creating code blocks with syntax highlighting on any website (of course, Java Script has to be run though).

So it does for Blogger and here's how:

Install SyntaxHighlighter On Blogger


Go to www.blogger.com, login with your account and select the blog in which you want to use SyntaxHighlighter. Then click on Layout --> Add a Gadget --> HTML/JavaScript give it a title and paste in this Code into the Content:

<!-- Include required JS files -->
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js"></script>

<!--    At least one brush, here we choose JS. You need to include a brush for every language you want to highlight-->

<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushBash.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJScript.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCpp.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPython.js"></script>
<script type="text/javascript" src="http://dl.dropbox.com/u/84194941/SyntaxHighlighter/shBrushSWIProlog.js"></script>

<!-- Include *at least* the core style and default theme -->
<link href="http://alexgorbatchev.com/pub/sh/current/styles/shCore.css" rel="stylesheet" type="text/css" />
<link href="http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css" rel="stylesheet" type="text/css" />

<!-- Finally, to actually run the highlighter, you need to include this JS on your page -->
<script type="text/javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.defaults['tab-size'] = 4;
SyntaxHighlighter.all()

</script>

This is my current configuration which adds support for highlighing JavaScript, Bash, C++, Python and SWI-Prolog (for more brushes see here).

Highlight Code


There are two possitilies to highlight code now, as described here. I decided to use the <pre>-tag, so the HTML of my post looks like this:
<pre class="brush: swipl">:- 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)

</pre>

The actual source code for this custom brush can be found here:
http://dl.dropbox.com/u/84194941/SyntaxHighlighter/shBrushSWIProlog.js

July 12, 2012

Adventures In Declarative Programming: Sudoku Solver

Declarative Programming


... in contrast to Imperative Programming (like C/C++, Python, Java, ...) doesn't care about the exact way of solving a problem. In Imperative Programming you define how a problem has to be solved. In Declarative Programming you simply describe what the problem is and 'the language' does the actual solving for you.
Since this is not that easy to understand if you never did it yourself before, I want to show you an example right away.

Solving Every Sudoku With 15 Lines Of Code


Of course lines of code is not a good measure to take, but it should just express that it's sometimes much easier to describe a problem than solving it step by step.
Before I'll show you the actual code I want to tell you a few things about the programming language used.

Prolog


Prolog is a logic programming language and basically consist of rules and facts. A Prolog program therefore is some kind of knowledge base, which you can query to get solutions to your problems.
So, in order to solve every Sudoku puzzle we just have to describe the rules of this game. Not that hard, eh? Great, let's do this.

Sudoku Solver In Prolog


:- 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)

This program is actually that easy, that you can even find it in the SWI-Prolog manual. Note that this example only works with SWI-Prolog and not with other Prolog implementations, because it uses the SWI-Prolog CLPFD library (Constraint Logic Programming over Finite Domains).

This is already the whole solver. It's quite easy to see that an imperative solution to this problem would be far more complex. In this blog post I'm explaining how the Sudoku solver actually works: Prolog Sudoku Solver Explained

Solving A Sudoku Puzzle


In order to solve a Sudoku puzzle now we have to query our program. An example query looks like this:

 Puzzle = [  
   [8,_,_,_,_,_,_,_,_],  
   [_,_,3,6,_,_,_,_,_],  
   [_,7,_,_,9,_,2,_,_],  
   [_,5,_,_,_,7,_,_,_],  
   [_,_,_,_,4,5,7,_,_],  
   [_,_,_,1,_,_,_,3,_],  
   [_,_,1,_,_,_,_,6,8],  
   [_,_,8,5,_,_,_,1,_],  
   [_,9,_,_,_,_,4,_,_]  
   ],  
   Puzzle = [A,B,C,D,E,F,G,H,I],  
   sudoku([A,B,C,D,E,F,G,H,I]).  

The only reason I splitted the whole Puzzle up into single rows (A,B,C, ...) is to generate a nicer output. We can also wrap the call of the predicate 'sudoku' into 'time' so we can see how long the solving actually takes.

If you want to try it out yourself and play around with it, just install SWI-Prolog and copy the program into a file. Then launch the SWI-Prolog interpreter from a terminal with our program as the input file and type in our query:

 user@host> swipl -f sudoku.pro  
 % library(error) compiled into error 0.00 sec, 79 clauses  
 % library(lists) compiled into lists 0.00 sec, 178 clauses  
 % library(occurs) compiled into occurs 0.00 sec, 15 clauses  
 % library(assoc) compiled into assoc 0.00 sec, 98 clauses  
 % library(pairs) compiled into pairs 0.00 sec, 23 clauses  
 % library(clpfd) compiled into clpfd 0.08 sec, 2,724 clauses  
 % /path/to/sudoku.pro compiled 0.08 sec, 2,739 clauses  
 ?- Puzzle = [  
 |  [8,_,_,_,_,_,_,_,_],  
 |  [_,_,3,6,_,_,_,_,_],  
 |  [_,7,_,_,9,_,2,_,_],  
 |  [_,5,_,_,_,7,_,_,_],  
 |  [_,_,_,_,4,5,7,_,_],  
 |  [_,_,_,1,_,_,_,3,_],  
 |  [_,_,1,_,_,_,_,6,8],  
 |  [_,_,8,5,_,_,_,1,_],  
 |  [_,9,_,_,_,_,4,_,_]  
 |  ],  
 |  Puzzle = [A,B,C,D,E,F,G,H,I],  
 |  time(sudoku([A,B,C,D,E,F,G,H,I])).
% 934,447 inferences, 0.154 CPU in 0.155 seconds (100% CPU, 6051414 Lips)
 Puzzle = [[8, 1, 2, 7, 5, 3, 6, 4|...], [9, 4, 3, 6, 8, 2, 1|...], [6, 7, 5, 4, 9, 1|...], [1, 5, 4, 2, 3|...], [3, 6, 9, 8|...], [2, 8, 7|...], [5, 2|...], [4|...], [...|...]],  
 A = [8, 1, 2, 7, 5, 3, 6, 4, 9],  
 B = [9, 4, 3, 6, 8, 2, 1, 7, 5],  
 C = [6, 7, 5, 4, 9, 1, 2, 8, 3],  
 D = [1, 5, 4, 2, 3, 7, 8, 9, 6],  
 E = [3, 6, 9, 8, 4, 5, 7, 2, 1],  
 F = [2, 8, 7, 1, 6, 9, 5, 3, 4],  
 G = [5, 2, 1, 9, 7, 4, 3, 6, 8],  
 H = [4, 3, 8, 5, 2, 6, 9, 1, 7],  
 I = [7, 9, 6, 3, 1, 8, 4, 5, 2] .  
(Executed on an Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz and 4GB of RAM)

Solving this Sudoku puzzle takes 0.155 seconds on my laptop which is fast enough for most purposes (the first number 934,447 are the logical inferences during the solving and Lips are Logical Inferences Per Second).

Conclusion


I hope this article made you curious about new programming languages and Prolog specifically.

As a general tutorial on Prolog I can suggest Learn Prolog Now. There are lots of other good books and tutorials out there though. Happy coding!



Discussion on Reddit: r/coding

July 8, 2012

Try Something New For 30 Days

My brother recently showed me this TED Talk from Matt Cutts in which he talks about trying out something new for 30 days.

Matt Cutts inspired me to do my own 30 day challenge, which will start tomorrow. Instead of having just one habbit added/subtracted I decided to bring several new things to my life and subtract one. I'm not sure whether this is the real idea behind these challenges, but I'll give it a shot and see whether it works for me.

The interesting thing about such challenges is that according to science a human needs about 21 days to form a new habit. Matt Cutts also said that the harder the challenge, the more unlikely it is that the habit will stick.

My Goals

  • no TV
  • 3 times jogging a week
  • 0.5 - 1 Unit Udacity a day
  • 1 hour learning Lisp a day
We'll see...

July 4, 2012

Hello, World!


So, here I am now. I finished high school and I'm ready to start studying at a university. Only two more things are in my way: Summer holidays and military/civilian service.

I spent the last few weeks watching TV, cooking and eating,  playing Gothic I-III and League Of Legends, reading articles at HackerNews, occasional jogging, swimming and having fun with friends at the weekends. This is what my life is all about now? Fuck you, holidays.

This is really frustrating me on a rational level. I know I could do so much more things with the time I have, but emotionally I'm fine with basically doing nothing.

That's why I decided to start blogging.

Hello, Blogging-World!


This is not my first attempt to create a blog, but I really want to give it another try after I read Publish What You Learn.

I'm unsure what I should expect from my blog and the experiences I'll make and I really don't think my blog will get that famous. But I'm sure that I'll learn new things during that adventure - not only about the topics I will blog about, but also about writing and the english language in general (which is not my native language, as you probably already noticed).

One day I'd love to have a small group of people who frequently read my blog and with discussions going on after every post I make. So, if you want to make a small boy's dream come true, just leave comments, give me feedback, help me improve my blog and start discussions!