At a glance, this feels like a good case for an exact cover algorithm. Would be neat to see how that compares, here.