Prolog Solver for Sudoku
I decided to work on a few algorithms I had implemented in Prolog that solve the famous sudoku puzzle. The Internet has several sudoku solvers implemented in Prolog but I decided to share some things I made during college and add a few new things to those old implementations.
As of the publishing of this post I have uploaded only the first sudoku solvel that is very basic and ineficient to Github. You can find it here.
But before posting about the first solver, I’ll post about Prolog in general, or rather, why I like Prolog.
When people start learning programming they generally start with a language that has an imperative paradigm. And imperative paradigm basically means that you are giving orders to the machine, like declare this variable, call this function, jump to this part of the code if a certain condition if true, etc. We start knowing the basics of this paradigm with a single language and, with time, we are ready to move to another language. We quickly see that the features of this new language are pretty much the same as the features from the old language. There are variables, functions, cycles, maybe even classes, etc. The big differences are there but the basis of the thing is mostly the same.
But what happens when you stumble upon a paradigm that is almost completely different? Suddenly you no longer declare variables and call functions. You write rules that are either True or False according to other rules. You don’t write an algorithm that gives a solution based on an input, you write which solution is True for each input.
This is Declarative Programming. Prolog is a language that follows the Declarative Paradigm which name is an abbreviation of Programmation en Logique, French for Programming in Logic.
During graduation I had a course called Declarative Programming where we just studied this new paradigm using Prolog. We would start with small problems and small programs and moved to the most complex things. The final project during that year was an implementation of the Go board game all in Prolog. This course at first was very complex. Trying to understand how the language worked and how it solved things and learning about the unification algorithm was hard at first, but eventually I was able to think in a different way when working with Prolog and solving problems became so much easier in some contexts.
Later during graduation I had a course on Artificial Intelligence. In this course we implemented many algorithms to solve a few problems, all in Prolog. It was during this course that I was able to truly appreciate how powerful and interesting this language was. The way a person things when solving a new problem is so different and yet so much better then the imperative way.
Of course, Prolog isn’t without a few problems, which are:
- It may be very hard to make this language efficient. You may end up having the program execute millions of useless lines of code if the rules are not well written.
- It’s just not a trivial language. For most cases a person can read a tutorial on a language, library or something else and in a few hours they start understanding the thing. Understanding this new paradigm and how Prolog works is simply hard. Some people will look at it and decide that the strange language is just not worth their time.
- Prolog is barely used outside academical and educational contexts. It’s rare to find commercial applications of Prolog, it’s not that they don’t exist, it’s just rare. This makes people not wanting to learn the language or work with it outside of class.
All this, among some other problems. Despite all this I believe that it is a language worth exploring because:
- It’s just interesting. It’s paradigm makes you think in a different way. You are able to look at problems from another prespective. If that is not a good point when solving problems, then I don’t know what is.
- Problems are solved in few lines of code. You just work with a handful of rules and you are able to work with trees, graphs, matrices, and do all sorts of complex computations. You don’t need to extra lines of code that define all you data structures, just a few rules that logically describe what you want.
- Abstraction is good. Like it is said in the previous point, you don’t waste time defining data structures. You don’t really work on the level of variables and classes and objects. You work on a higher level almost an abstract level. You can concentrate on the structure of the formal models instead of thinking in the structure of the implemented one.
Given this, let’s develop in Prolog!