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
_______________________________________________
Users-prolog mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/users-prolog
