I built a Sudoku puzzle solver and builder a few years back, at the time when it became popular. Generating all possible combinations is quite simple, the difficulty lies in modeling simply the way to list the rules that make some authorized (or others forbidden). I think that an approach similar to the eight queens problem on a chess board should probably work. Interesting challenge, it is just a pity I don't have enough time to try anything before at least a few hours, possibly nor before tomorrow.