David Eppstein has made a stab at trying to rate the difficulty of a Sudoku for humans in: "Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku" http://arxiv.org/abs/cs.DS/0507053. I think that the key to understanding this is in looking for algorithms whose space is very limited. I believe that a well-trained human is willing to do a fair amount of computation as long as the number of bits he has to remember in his short term memory isn't too large (this is assuming that the only things that are allowed to be written down and the deduced numbers to be put in a cell). I've found that translating a Sudoku to a satisfiability problem and then giving it to any one of the good SAT solvers yields a solution in under 1 second (often much less). But all of them use far more storage than a human would be willing to use. -- Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor@idaccr.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin