« Back to posts

Seven Languages: Week 3 (Prolog) - Day 3

06 Aug 2012

Day 3 tackled some bigger examples: solving sudoku and the eight queens problem. In today’s post however, I’m going to go a bit off the rails and talk a bit about how logic programming can be beneficial in more practical ways.

(This article is part of a series of posts I am doing about my journey through the exercises of the book Seven Languages In Seven Weeks. The article previous to this one is Week 3 (Prolog) - Day 2. For an overview see the Seven Languages project page.)


Datalog is a subset of Prolog oriented towards querying that was designed to be embeddable in other languages. Many languages have datalog engines, such as Java, Python, Clojure and Racket. It has become more well-known recently for being the query language of choice for Datomic, a promising new distributed database. Michael Fogus is even giving a talk at this upcoming Strange Loop about “The Reemergence of Datalog”.

Constraint Programming

Every time in these past examples when I use the Prolog library clp(fd) (which stands for Constraint Logic Programming over a Finite Domain), I’m doing constraint programming. A lot of the time it is mixed in with logic programming, but it doesn’t have to be: there are constraint programming libraries for a lot of other languages. It can be really beneficial to know how to use even if you never write a line of Prolog.

In fact, the prolog solution to sudoku below owes a lot of its conciseness to constraint programming. Sudoku solver implementations in other languages that have a constraint programming library can be about the same length! Another property of solutions using constraints is that they are usually a lot faster than an equivalent logic programming only solution.

Other logic languages

Prolog is the most widely used logic language, but it isn’t the only one. Here are a few other interesting ones that caught my eye.

  • Mercury is a functional logic programming language that shares Prolog’s syntax but has a strong static type system.
  • Curry is a functional logic programming language based on Haskell. It has constraint programming support built in.
  • Oz is a dynamically typed multi-paradigm language. The (reportedly excellent) book Concepts, Techniques, and Models of Computer Programming uses Oz as its language of choice.

Logic libraries

Surprisingly, you can get logic programming functionality in library form as well! These libraries are less common than constraint programming libraries, I could only find a few:

  • Scheme: Kanren, miniKanren and cKanren. Kanren is the original implementation, miniKanren is a simplified implementation (~300 lines) for ease of teaching, and cKanren modifies miniKanren to support constraint logic programming.
  • Clojure: core.logic. This library was actually based off of miniKanren originally, and cKanren functionality is currently in progress.
  • C++: LC++

Highlights from exercises

The exercises in this chapter were pretty interesting, but also pretty exhausting for a newbie to logic programming. I ended up with two implementations of a sudoku solver. The second one was about a fifth the size of the first and I learned a ton in the process of writing it. I think my implementation is fairly readable, so if you’re interested please feel free to scroll down to the formatted solutions and take a look.

That’s not what I’ll be highlighting here though. I’ll be pitting a Prolog solution against a solution from a regular (i.e. not logical) programming language that uses a constraint programming library. Since next week is Scala, I’ll arbitrarily pick Scala as the language and JaCoP as the constraint programming library. This is a light comparison done for my own fun and enlightenment, it isn’t meant to be comprehensive.

Since I’m just a beginner with logic and constraint programming, it would be meaningless to compare implementations I wrote myself; the properties of the solutions would have more to do with my limitations than the languages they’re written in. So for these examples I will be leaning on more experienced minds.


This Prolog solution is taken from the clp(fd) documentation.

:- use_module(library(clpfd)).

sudoku(Rows) :-
        length(Rows, 9), maplist(length_(9), 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).

length_(L, Ls) :- length(Ls, L).

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

Scala + JaCoP

This Scala solution is taken from Hakan Kjellerstrand’s scalaJaCoP page. Here is a direct link to the file itself.

import scalaJaCoP._

object Sudoku extends App with jacop {
  val n = 9
  val reg = 3

  // data
  val problem = ... // omitted

  val x = List.tabulate(n)(i=> 
                  new IntVar("x("+i+","+j+")", 1, n)))

  // constraints

  // fill with the hints
  for(i <- 0 until n) {
    for(j <- 0 until n) {
      if (problem(i)(j) > 0) {
        x(i)(j) #= problem(i)(j)
  // rows and columns
  for(i <- 0 until n) {
    alldifferent( Array.tabulate(n)(j=> x(i)(j)) )
    alldifferent( Array.tabulate(n)(j=> x(j)(i)) ) 

  // blocks
  for(i <- 0 until reg; j <- 0 until reg) {
    alldifferent(  (for{ r <- i*reg until i*reg+reg;
                        c <- j*reg until j*reg+reg
                     } yield x(r)(c)).toArray

   // search
  val result = satisfyAll(search(x.flatten, max_regret, indomain_max), printIt) 

  def printIt() { ... } // omitted

For brevity I’m omitting how the Prolog solution is queried and how the Scala solution is printed. I want to keep the focus on the interesting parts of these programs. For the full source code, check the links above or the benchmark source code on github.



The Prolog program is just over half as long at 13 lines instead of 25 for Scala (not counting comments or whitespace). Although this is definitely a win for Prolog, the Scala version is still far shorter than any Sudoku solvers that don’t take advantage of constraint programming.


Ah, the most subjective benchmark! This one is hard for me to judge fairly, since I’ve spent a lot of time inside of Prolog recently, and none using Scala or JaCoP. That said, even trying to account for my bias I think the Prolog solution has a big advantage here. It reads a lot more declaratively than the Scala solution and doesn’t have to worry about as many details.

Given my bias I would be very interested to hear feedback on this topic. Which solution did you think was more readable?


Now we are into interesting territory. Prolog has a few decades’ headstart on JaCoP, but JaCoP has the speed of the highly optimized JVM behind it. Let’s see who comes out on top!

Disclaimer: I acknowledge that benchmarking is an easy thing to do incorrectly. I’ve made the source code for these benchmarks available on github and included instructions to allow you to (hopefully!) easily replicate my results. Please feel free to double check what I’ve done, I am more than happy to receive feedback telling me I am wrong. Contributions using other libraries or languages are also welcome.


SWI-Prolog managed to solve the sample sudoku problem in an average of 78 milliseconds on my machine.

JaCoP managed to solve the sample sudoku problem in an average of 95 milliseconds on my machine.

The Scala version takes 1.2 times the amount of time the Prolog version takes. Honestly, this was an unexpected result for me; I would have guessed JaCoP had the edge. Regardless, they are both pretty damn fast solutions for not a lot of effort. Both win here.


Given the close results, there is only one clear conclusion I can draw from this comparison: Scala + JaCoP can roughly match the expressiveness and speed of a Prolog solution, at least for Sudoku. But that’s boring! If I may hypothesize, I would guess that: for a large class of problems, constraint programming libraries can give you most of the benefits of a logic programming solution while only sacrificing a little bit of declarative conciseness and elegance.

Good news for the working programmer who doesn’t feel he has time to learn Prolog!

More constraint programming examples

Hakan Kjellerstrand has a fantastic collection of problems solved using many different constraint programming libraries. It is a great resource and can be fun to compare different implementations of the same problem.

Full Code Listing

Here is a nicely formatted version of my solutions to the exercises from Day 3 of Prolog. The home of the following code is on github with the other exercises.


1. Prolog has some input/output features as well. Find print predicates that print out variables.
There's 'write'. I'll paste my minInList function in here and make it write each element of the list while it checks them. Aha, 'format' and 'writef' are very nice too.
min(A,B,B) :- B < A.
min(A,B,A) :- A < B.

minInList([X|XS], M) :- minInList(XS, M1), min(X, M1, M), format('~a, ', X).
minInList([X], X) :- format('~a, ', X).
2. Find a way to use the print predicates to print only successful solutions. How do they work?
To answer this one... I guess I want to use a rule that can have multiple correct answers. I'll take an example from the book.
different(red, green). different(red, blue).
different(green, red). different(green, blue).
different(blue, red). different(blue, green).

coloring(Alabama, Mississippi, Georgia, Tennessee, Florida) :-
    different(Mississippi, Tennessee),
    different(Mississippi, Alabama),
    different(Alabama, Tennessee),
    different(Alabama, Mississippi),
    different(Alabama, Georgia),
    different(Alabama, Florida),
    different(Georgia, Florida),
    different(Georgia, Tennessee),
    format('~a, ~a, ~a, ~a, ~a', [Alabama, Mississippi, Georgia, Tennessee, Florida]).
Well, that will only print successful solutions, but I kind of feel like I've missed the point. All this will do is repeat the information that you already receive. Oh well, if I figure it out I'll come back to it.


1. Modify the Sudoku solver to work on six-by-six puzzles (squares are 3x2) and 9x9 puzzles)
I wrote a long awful version of this first, then cheated to write a better one. I looked at this sudoku solver (found in the clp(fd) documentation), understood how it worked, then closed it and wrote my own. This is the version that you see below. I also chose to do just 9x9.
:- use_module(library(clpfd)).

sudoku(Rows) :-
    % split into rows
    Rows = [A, B, C, D, E, F, G, H, I],
    % and columns
    transpose(Rows, Columns), 

    % some bounds checking
    append(Rows, FlattenedRows), FlattenedRows ins 1..9,
    length(Rows, 9),
    length(Columns, 9),

    % all rows valid
    maplist(all_distinct, Rows),

    % all columns valid
    maplist(all_distinct, Columns),

    % all blocks valid
    valid_blocks(A, B, C),
    valid_blocks(D, E, F),
    valid_blocks(G, H, I),


valid_blocks([], [], []).  
valid_blocks([A1, A2, A3 | As], [B1, B2, B3 | Bs], [C1, C2, C3 | Cs]) :-
    maplist(all_distinct, [A1, A2, A3, B1, B2, B3, C1, C2, C3]),
    valid_blocks(As, Bs, Cs).

problem(1, [[_,_,_,_,_,_,_,_,_],                                   

% can test with:
% ?- problem(1, Board), sudoku(Board).
2. Make the Sudoku solver print prettier solutions.
prettier_print(Puzzle) :- prettier_print(0, Puzzle).

prettier_print(0, Puzzle) :- 
    prettier_print(1, Puzzle).
prettier_print(4, Puzzle) :- 
    prettier_print(5, Puzzle).
prettier_print(8, Puzzle) :- 
    prettier_print(9, Puzzle).
prettier_print(12, []) :- 

prettier_print(N, [Col1, Col2, Col3, Col4, Col5, Col6, Col7, Col8, Col9 | Puzzle]) :- 
    member(N, [1,2,3,5,6,7,9,10,11]),
    %N =\= 0, N =\= 4, N =\= 8, N =\= 13,
    % note to self about above: remember, prolog's pattern matching isn't
    % like pattern matching in other languages

    format('│ ~d ~d ~d │ ~d ~d ~d │ ~d ~d ~d │~n', [Col1, Col2, Col3, Col4, Col5, Col6, Col7, Col8, Col9]), 
    succ(N, N1),
    prettier_print(N1, Puzzle).
?- problem(1, Board), sudoku(Board).

│ 9 8 7 │ 6 5 4 │ 3 2 1 │
│ 2 4 6 │ 1 7 3 │ 9 8 5 │
│ 3 5 1 │ 9 2 8 │ 7 4 6 │
│ 1 2 8 │ 5 3 7 │ 6 9 4 │
│ 6 3 4 │ 8 9 2 │ 1 5 7 │
│ 7 9 5 │ 4 6 1 │ 8 3 2 │
│ 5 1 9 │ 2 8 6 │ 4 7 3 │
│ 4 7 2 │ 3 1 9 │ 5 6 8 │
│ 8 6 3 │ 7 4 5 │ 2 1 9 │
3. Solve the Eight Queens problem by taking a list of queens. Rather than a tuple, represent each queen with an integer, from 1-8. Get the row of a queen by its position in the list and the column by the value in the list.
...I think I'm just going to leave this one. I'd like to move on to Scala at this point

Next in this series: Day 1 of Scala.

blog comments powered by Disqus
Content by Nick Knowlson: Google+