SyntaxHighlighter

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

7 comments:

  1. I find declarative program quite interesting. I'm surprised that it was actually able to find the solution so quickly.

    I wonder if there is any way to introduce declarative concepts in imperative programming. The enginer/compiler are completely different beasts however.

    ReplyDelete
    Replies
    1. There are Foreign Language Interfaces for different languages, which allow you to write and query Prolog programs from your imperative language.

      For example for C++ or Java:
      http://www.swi-prolog.org/pldoc/package/pl2cpp.html
      http://www.swi-prolog.org/packages/jpl/

      Delete
    2. As I read a few of your blog posts, this seems not to be quite what you were thinking about. You're going a level higher on the actual design of the programming language as it seems - quite interesting blog.

      Delete
  2. That's interesting !! ... but i think i need another example to understand the way i should think and solve problems with Prolog, so i am trying to solve Akari/light up puzzle .. but before that am trying to check if a grid of it represent a solution using Prolog, Can you help me please with it.

    ReplyDelete
  3. That's pretty great!

    However, I was unable to reproduce the result. Possibly something changed in the language or library? Getting "false" for the example now. Same if I replace all cells with "_". Just FYI—don't feel compelled to fix it.

    ReplyDelete
    Replies
    1. It works fine for me. Note that the code above is missing a dot at the end of the blocks predicate, if you just copy and pasted the whole thing.

      Delete