Really fun problem. Pretty sure this would be easy to encode as an exact cover problem, and then just use Knuth's dancing links. Just got into the office, so probably not going to have time to try today, but will try and make an attempt at it this evening. (After I do the advent problem for today, of course. :) )

The prolog version already posted looks fun, too. Curious if anyone has already done this as an exact cover.