Index ¦ Archives ¦ RSS

CSP

Estimated read time: 1 minutes

CSP, as in Constraint satisfaction problem. A while back I wrote a custom sudoku solver in Erlang, and now I hit something similar. Of course, since then I learned that there are nice CSP engines, so this time I did not try to write my own. :)

First, I checked out python-constraint, and then I sticked with it, as it fulfilled my needs.

So, the problem. Here is a Christmas tree:

/pic/csp.t.png

The tree has 4 chains, each one contains 7 items. A few ones already has a number. The exercise: number the empty items with numbers between 1 and 7 so that:

  • Each chain contains the numbers 1..7 exactly once.

  • All the horizontal and diagonal lines cannot contain the same number twice.

A possible solution is here. If you get less or more than one solution, you did something wrong. :) (I’m not pasting here the output of the script to leave some exercise for the readers. ;) )

Note
As an experiment this time I draw the image using TikZ. Based on these ideas I converted the source to PNG using tikz2png.

© Miklos Vajna. Built using Pelican. Theme by Giulio Fidente on github.