Re: Getting Query Metrics

[Pierre Deransart]

Hi Bill,
from computer point of view, and for any sudoku of size square n, it is 
an NP-complete problem, very easely solved (in particular) with 
constraints solvers. It means that in practice, some backtracking will 
be necessary for some sudoku grids at some point, having to guess some 
value in some slot of the grid. So counting the number of resolution 
steps and of backtracks (number of unsuccessful guesses) may be a way to 
estimate some "algorithmic" complexity, i.e. the level of difficulty 
related to a particular algorithm (including a particular heuristic).

Now the question is whether you refer to human difficulty or computer 
complexity. There exists inumerous handbooks on "how to solve sudokus". 
The idea is to classify sets of rules (themselve classified as from 
"simple" like "Candidate line" until  more complex like "Swordfish" ...) 
which should be used gradually to solve more "difficult" grids 
(themselve classified as from "easy" until "expert"...). The level of 
difficulty depends thus of the kind of "difficult" rules which have been 
necessary to use. It is not clear how computer complexity and human 
difficulty are related. We just know two points:
-In general (for any n), there is no deterministic algorithm to solve a 
given grid, that is to say, given any set of deterministic rules (for 
human or computer), at some point, it will be necessary to "try and 
test" with the risk to have to backtrack. Whether there exists such set 
of deterministic rules which could be used for puzzles of any size, is 
an open question (related to NP completeness). As far as I know, the 
same question for grids of size 9 is also open. It is most likely to 
expect that such a set would be extremely boring to be used by human!
-It is also an open problem to generate a sudoku grid of a given level 
of difficulty from human point of view. (The most presently used 
automated methods generate grids and test them systematically until some 
"dificult" one is found).

There is a book http://njussien.e-constraints.net/sudoku/eng-index.html 
showing relationsships between sudoku, prolog and constraints, and a 
paper http://hal.inria.fr/inria-00085809/en/ unfortunately in French 
relating constraint models with levels of difficulty. You may find there 
many references.


Bill Woessner wrote:

> Is there any way to ask GProlog "how hard" it worked to satisfy a
> query?  I've got a really simple Sudoku solver and I've been testing
> it with various puzzles.  But I'd like to develop an objective notion
> of "how hard" a given puzzle is.
>
> Thanks in advance,
> Bill
>
>