David P Bird wrote:Excluding those that are designed for speed, a computer solvers should demonstrate methods which a human player could use to solve a puzzle preferably without using reams of paper. Surely this must put a huge constraint on the selection of computationally simple/efficient methods?
With a computer it's easy to iterate all the possibities using nested loops for example to find fish and multi-fish, but a human player would only explore these options via different routes if there was a clear indication that a promising pattern existed in a puzzle. A good example of this is puzzles with SK loops that produce multiple eliminations which are recognisable by experienced players.
Human solving emulation does indeed constrain things, but I am not sure how useful this constraint is in practice. Humans are very good at certain kinds of pattern matching in ways that computers are typically very bad at emulating. That lack of correspondence makes it difficult to "prune" the set of computer techniques you need to explore to develop equivalents to human solving techniques. Your example with SK loops is good. Humans seem to be good at looking at looking at a broad situation and zeroing in on a few specific points that are worth exploring further without exploring the entire
space of all possible methods. Our computer emulations of that ability tends to use approaches, for example exhaustive search, that on the surface would appear to be ruled out when considering only human style solving techniques.
Computational Complexity Theory
David P Bird wrote:Would you include some measure about the probabilty of success in the mix? If so the waters get very murky indeed.
does not take probabilities into account. It focuses on worst case performance, and essentially ignores average case and best case situations. There has been some relatively recent theoredical work on distinguishing typical case performance from worst case performance and trying to optimize for typical case instead of worst case, but that is technically outside the domain of computational complexity as I understand it. Obviously this focusing on real world situation performance is done all the time in practical situations, but it has proven to be very complex to deal with at a theoretical level.