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

One comment on “Week 3 Day 3 – Solving a sudoku with Prolog

  1. Hi,
    I tried this solution on a few puzzles but I found that it only works on easy ones. If a puzzle needs more advanced steps (hidden singles, naked pairs, pointing pairs, etc), it fails.

    Here is a positive and a negative example. Both puzzles have exactly one solution. They only differ in one digit, which makes the first one solvable by this program.

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

    Solution = [8,3,5,4,1,6,9,2,7,2,9,6,8,5,7,4,3,1,4,1,7,2,9,3,6,5,8,5,6,9,1,3,4,7,8,2,1,2,3,6,7,8,5,4,9,7,4,8,5,2,9,1,6,3,6,5,2,7,8,1,3,9,4,9,8,1,3,4,5,2,7,6,3,7,4,9,6,2,8,1,5]

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

    Solution = [8,_#16(2..3),_#37(3:5),4,_#71(1:5),6,9,_#126(1..3),7,_#160(2:6:9),_#181(2..3:6..7:9),_#202(3:5..7),_#223(1..3:7..8),_#244(1:5:8..9),_#265(1:3:5:7..8),4,_#299(1..3),_#320(1..2:8),_#341(2:4:9),1,_#375(3..4:7),_#396(2..3:7..8),_#417(8..9),_#438(3:7..8),6,5,_#485(2:8),5,_#519(2:6),9,_#553(1:6),3,_#587(1:4),7,8,_#634(2:4),_#655(1..2:6),_#676(2..3:6),_#697(3:6),_#718(1:6:8),7,_#752(1:4:8),5,_#794(2:4),_#815(2:4:9),7,4,8,5,2,9,1,6,3,_#985(4:6),5,2,_#1032(1:6..8),_#1053(1:4:6:8),_#1074(1:4:7..8),3,9,_#1129(1:4:6),_#1150(4:6:9),_#1171(6..9),1,_#1205(3:6..8),_#1226(4..6:8),_#1247(3..5:7..8),2,_#1289(4:7),_#1310(4:6),3,_#1344(6..7),_#1365(4:6..7),9,_#1399(1:4:6),2,8,_#1454(1:4:7),5]

    yes

    Do you have any idea how to modify the code to be able to solve all puzzles?

    Thanks,
    Daniel

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s