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