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!
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!