This paper makes two contributions to the study of problem solving methods. First, we extend the current theory on how to characterise problem-solving methods. We show that the current theory is not strong enough, and does not allow the characterisation of many natural problem-solving methods. Secondly, we show that characterisations of problem-solving methods should be stated in gradual terms, and not in terms of yes/no requirements. Such a gradual approach to characterising problem-solving methods allows methods to use domain knowledge that only partially fulfills the requirements, in which case the methods still produce useful, although suboptimal solutions. Problem-solving methods with such gradual behaviour can be applied and re-used in a wider set of circumstances than classically characterised methods.