Don't check the constraint with [0, 0] separately

Now that it checks the maximum versions only first, it is fairly rare that
this case will succeed.
Only check for satisfiability when generating the hint

This makes the hint code run much faster, and use less memory (because it
never uses the pseudo-boolean stuff). Fixes #703.