> and as soon as you try to add a couple of breakpoints the whole thing becomes NP-complete.

Sure, that's a given with the constraint satisfaction approach but NP-complete problems work just fine when N is small enough.