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:
- The square in the middle is a magic square (all rows,columns, and digonals add up the same).
- Both diagonals of the board can’t have repeated numbers.
- 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
one-value communicate what’s
the state of the world and decide to try other values.