Constraint Programming with CL Screamer

I’ve been wanting to get into Lisp again and last week it came to my hands a problem that looked like a perfect case for giving CL another try.

The problem is about a very special sudoku with only 4 initial values. The sudoku has, of course special rules:

1. The square in the middle is a magic square (all rows,columns, and digonals add up the same).
2. Both diagonals of the board can’t have repeated numbers.
3. any cell can’t be the same number as any of it’s chess knight-distance peers.

The solution is here.

Anyway, I didn’t want to solve it by hand, so I started thinking how to do it, and remembered a few recent screamer posts I read, so I gave a shoot to it.

Here’s the simple solution for solving the magic square using Constraint Programming.

   (one-value
     (let ((a (an-integer-between 1 9))
           (b (an-integer-between 1 9))
           (c (an-integer-between 1 9))
           (d (an-integer-between 1 9))
           (e (an-integer-between 1 9))
           (f (an-integer-between 1 9))
           (g (an-integer-between 1 9))
           (h (an-integer-between 1 9))
           (i (an-integer-between 1 9)))
       (if (and (= (+ a b c) (+ d e f) (+ g h i)
                   (+ a d g) (+ b e h) (+ c f i)
                   (+ a e i) (+ g e c))
                (/=v a b c d e f g h i))
           (list a b c d e f g h i)
           (fail))))   ; => (2 7 6 9 5 1 4 3 8)

Very nice to use automatic backtracking for solving any kind of problem: The fail function, /=, and one-value communicate what’s the state of the world and decide to try other values.