They must be non-obvious to an expert in the field.

In theory that's a strictly tighter constraint than non-obvious, although it's impossible to actually implement.

However, independent invention isn't necessarily a proof that the particular patent should not have been granted.

Often, it is not the solution but its problem space that's obvious. There tends to be a finite domain of reasonable solutions, and solutions converge to that domain.

In which case you probably want some sort of thicket busting legislation.