Week 3 Day 3 – Solving a sudoku with Prolog

This is the thing i have been most looking forward to in Seven Languages in Seven Weeks! Prolog is exceptionally good at solving problems with well-defined constraints. A sudoku is perfect for Prolog.

You don’t have to write any any algorithm to tell Prolog how to solve a sudoku. You just have to give it the rules of the game:

  • A sudoku is a 9×9 grid.
  • It must only contain the numbers 1-9.
  • In each row, column and 3×3 square, every number must be different.

Amazingly enough, if you can explain to Prolog these contraints, it can solve the hardest sudoku in matter of milliseconds!

Starting small

We started with a 4×4 sudoku containing the numbers 1-4 because it’s easier to grasp. Just look how little code there is! sudoku/4×4.pl

I then moved to a 6×6 sudoku. It’s not a lot more code. The hardest thing is making sure you don’t make a typo. I got very good at selective vim find and replace in this exercise! sudoku/6×6.pl

I tried to write my own 6×6 sudoku puzzle for it to solve. I encountered something interesting: it’s not very easy to design a sudoku! I’d either get more than one possible solution:

| ?- sudoku([1,_,2,_,_,5,
             _,_,_,_,_,_,
             _,5,_,3,_,_,
             _,2,_,_,_,4,
             _,_,_,_,4,_,
             3,_,6,1,_,_], Solution).

Solution = [1,_#17(3:6),2,4,_#75(3:6),5,
            5,_#133(3:6),4,2,_#199(3:6),1,
            4,5,1,3,2,6,
            6,2,3,5,1,4,
            2,1,5,6,4,3,
            3,4,6,1,5,2]

Now i look at it again, it’s telling me, “I can either put a 3 or a 6 in these places”. Which is very cool. And not surprising that when i tried to use a 2 in one of those places i found i accidentally made an impossible puzzle:

| ?- sudoku([1,_,2,_,_,5,
             _,_,_,_,2,_,
             _,5,_,3,_,_,
             _,2,_,_,_,4,
             _,_,_,_,4,_,
             3,_,6,1,_,_], Solution).

no

Heheh. Good old “Prolog says no”! It’s really nice that Prolog can help you not only solve a sudoku, but design a valid one in the first place.

Well, in the end i came up with this. I supplied the numbers in pen, and Prolog worked out the answer that i’ve filled in with pencil.

Finally I got to the sudoku 9×9 solution: sudoku/9×9.pl

To test it, i took my sudoku puzzle book and fed it one of the “hard” puzzles. To my surprise, Prolog found two valid answers! In less than 1 millisecond!

End of the Prolog week

Prolog is very very cool for certain types of problems. It can be incredibly frustrating and unhelpful when you don’t phrase your requests just right, but when you see it crunch your data and answer complicated questions with ease, it’s very inspirational.

I am actually considering using Prolog in a project i’m working on at the moment where we need to do some analysis about similarity and relevance. If we can figure out the rules by which unrelated things may be similar to each other, Prolog may be just what we need to find the most relevant results!

In the end, just knowing a bit about some other languages means i am better placed to choose the most useful one in any given situation. That’s why i’m pleased i’m doing Seven Languages in Seven Weeks!

Advertisements

Week 3 Day 2 (continued) – Prolog finding the smallest element in a list

Finding the smallest in a list has a fairly similar solution to reversing a list. It’s a recursive rule with a join to get the answer. In this case, the join is not an append but a ‘smaller’ rule that i wrote especially to find the smaller of two numbers.

But let me not get too far ahead. The first thing i did was handle the case of a list with only one item.

smallest([Head|[]], Head).

That’s a fact. The smallest element in the list [9] is 9. This is also a termination case for the recursive rule.

So next i turned my attention to the smaller rule. I wrote it like this:

smaller(X, Y, What) :-
  (X < Y), What is X.

smaller(X, Y, What) :-
  (Y < X), What is Y.

In the meantime, Tom Crayford has shown me a beautifully elegant way to rewrite these rules:

smaller(X, Y, X) :-
  (X < Y).

smaller(X, Y, Y) :-
  (Y < X).

My brain b0rked a little when i saw that, but then i figured it out:

The smaller of X and Y is X if you can prove that X is less than Y.

I know, Tautology Club, right?!

I must also cater for “Which is the smaller of 3 and 3?” In this case, it doesn’t matter whether we respond with X or Y, they are the same anyway, so we come to this:

smaller(X, Y, X) :-
  (X =< Y).

smaller(X, Y, Y) :-
  (Y < X).

Finally, my rule to find the smallest. To find the smallest element of a list, you take the smaller of the first element or the smallest of the rest of the list.

smallest([Head|Tail], Answer) :-
  smallest(Tail, What),
  smaller(What, Head, Answer).

I pretended to be Prolog and ran this all by hand. It seemed to work. But back to everybody’s favourite Prolog error message: Prolog says no.

It turned out that i had written these facts and rules in the order i thought of them. I had a fact for smallest, two rules for smaller, and then a rule for smallest. And Pedantic Prolog doesn’t like that. I guess you have to put all the facts and rules together by name.

My final solution looks like this:

smaller(X, Y, X) :-
  (X =< Y).

smaller(X, Y, Y) :-
  (Y < X).

smallest([Head|[]], Head).

smallest([Head|Tail], Answer) :-
  smallest(Tail, What),
  smaller(What, Head, Answer).

I’m going to skip Day 2’s final exercise because i’ve seen Alberto’s solution and frankly it just scares me! If i don’t move on now i’ll never get to the Sudoku and i’ve been really looking forward to that!

Week 3 Day 2 – Solving the Prolog reverse list

Well, i’m finding this prolog exercise quite a challenge. I thought i’d walk through my thought process as i go.

First of all i tried something completely useless, i don’t even remember what, but i was very surprised when it seemed to work straight away! I had called the rule ‘reverse’ and i think there must already be a ‘reverse’ rule built in!

So then i tried this simple fact:

rev([], []).

And yay! It works! It successfully reverses an empty list!

| ?- rev([], What).

What = []

Now, a list with one item needs no reversing. So next i did this:

rev([Head|[]], [Head]).

We know that the list has one item because when we split it into head|tail the tail is empty.

| ?- rev([1], What).

What = [1]

Hooray! Next i tried this, trying to reverse two items:

rev([Head|[Head2|[]]], [Head2|Head]).

Trying it out:

| ?- rev([1,2], What).

What = [2|1]

Oooh, close! I just don’t need the line between them. I guess a comma should work.

rev([Head|[Head2|[]]], [Head2,Head]).

Moment of truth:

| ?- rev([1,2], What).

What = [2,1]

Okay! Shall we go one step further?

rev([Head|[Head2|[Head3|[]]]], [Head3,Head2,Head]).

Here goes:

| ?- rev([1,2,3], What).

What = [3,2,1]

Right, now can we generalize this for any size list?

First attempt:

rev([Head|Tail], [What|Head]) :-
  rev(Tail, What).

Try it out:

| ?- rev([1,2,3], What).

What = [[[[]|3]|2]|1]

Oooh! Well the numbers came out in the right order! We just have way too many lists going on there! Let’s try this:

rev([Head|Tail], What) :-
  rev(Tail, What).

Hmm, no, this is no good. It can’t store the result as it goes along:

| ?- rev([1,2,3], What).

What = []

Let me think logically. What i really want to do is this: If the list has more than two items, put the first one to the back and run the reverse with all but the first. Sort of like this:

rev([Head|Tail], append(rev(Tail, []), Head)).

But you can’t do that. That’s trying to be a fact, but i need it to be a rule.

I ran it through by hand, trying to extract the rules. Here’s what i came up with:

rev([Head|Tail], Answer) :-
  rev(Tail, What),
  append(What, Head, Answer).

But here’s the problem i had:

| ?- rev([1,2,3], What).

no

It’s this all-or-nothing thing about Prolog. If it can’t find a solution it just says no. There is no hint as to where i might have gone wrong.

This got me frustrated for a long time, but in the end i discovered the problem was with the Head parameter. Once you’ve split an array into Head and Tail, the Head is a single element, and append only works with arrays. So here is the final solution, both the facts and the rule.

rev([], []).
rev([Head|[]], [Head]).
rev([Head|Tail], Answer) :-
  rev(Tail, What),
  append(What, [Head], Answer).

And, what do you know, it works!

| ?- rev([], What).

What = []

| ?- rev([1], What).

What = [1]

| ?- rev([1,2], What).

What = [2,1]

| ?- rev([1,2,3,4,5], What).

What = [5,4,3,2,1]

What did i learn from this?

I learned that Prolog is very pedantic! It doesn’t give any clues if you don’t get your syntax right. It’s just “I tried to do what you asked, and it didn’t work!”

But i also learned a technique for solving these recursive problems. It’s called: “Write down the rule as you’d like to use it, put circles around the parts that need to be extracted, put them on the line below and replace with a variable”. It sort of makes sense to me but i don’t think i’d like to try and teach it to anyone else!

Whew, well the reverse list took me 3 days! Now i can get on with the next exercise! :)

Week 3 Day 1 – Getting started in Prolog

After all my difficulties getting Prolog installed on OSX, i set up a virtual machine with Ubuntu and got it installed straight away, no problem!

sudo apt-get install gprolog

So i think i will be doing my prolog learning in Ubuntu! :)

Yesterday was nice for me, but i don’t think i’ve had my Prolog Epiphany yet! In the exercises, the hardest thing was thinking of books, authors and musicians! My mind just went blank! :)

I set up a couple of knowledge bases, one of which was about musicians, instruments and genres. I set up a few facts about things i know. I made a rule for finding musicians who play guitar, and then a rule to connect genres and instruments, via the musicians. After that i could compile the world and query it in a few different ways.

If i’m honest, it really felt a bit like joining SQL tables, and didn’t feel very innovative. I’m looking forward to getting deeper into prolog and learning a lot more today :)

Week 3 – Installing Prolog in OSX

It’s fair to say, installing Prolog in OSX is a tad tricky.

I tried installing from homebrew.

$ brew search prolog
gnu-prolog  swi-prolog

I first tried gnu-prolog but it seems the version it tries to fetch no longer exists.

A quick look on wikipedia told me that there’s not much difference between gnu-prolog and swi-prolog so i thought i’d give the latter a try. However, that one stalls on “make check” and never seems to get to the end.

So then i thought i’d try the .dmg installer found on gprolog.org. All seemed well until i tried loading up a prolog file:

$ /opt/local/bin/gprolog
GNU Prolog 1.3.1
By Daniel Diaz
Copyright (C) 1999-2009 Daniel Diaz
| ?- ['friends'].
uncaught exception: error(system_error('error trying to execute pl2wam (maybe not found)'),consult/1)

Sooooo … i give up. Now i am downloading Ubuntu which i’m going to install into a virtual machine. I’ve heard it’s a lot easier to install for Ubuntu.

If anyone knows how to install Prolog for OSX please comment below for others’ benefit!