Getting Query Metrics

[Bill Woessner]

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

--
Bill Woessner

The problem with eating German food is that, an hour later, you're
hungry for power.


_______________________________________________
Users-prolog mailing list
Users-prolog@...
http://lists.gnu.org/mailman/listinfo/users-prolog

[Daniel Diaz-3]

Bill,

That's a difficult problem and with no general answer: computers
executed code very quickly, a lot of this code is really stupid wrt to
human reasoning. Then, even if you can ask a program "how hard" it
worked the answer is maybe not really relevant. However, to ask "how
hard" a program worked, obvious things are execution time (see
statistics in gprolog) and/or counting the number of backtracking
performed by your program. There is no predefined way to do this in
gprolog but it is easy to add code to count backtracking using a global
variable (see g_assign/2). In addition, if your sudoky program uses FD
constraints you could be interested in the backtracks(B) option of the
built-in predicate fd_labeling (at then end of the labeling B will be
unified by the number of performed backtrackings).

Hope this helps.

Daniel

Bill Woessner a écrit :
> 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
>
>  


--
Ce message a ete verifie par MailScanner
pour des virus ou des polluriels et rien de
suspect n'a ete trouve.



_______________________________________________
Users-prolog mailing list
Users-prolog@...
http://lists.gnu.org/mailman/listinfo/users-prolog

[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
>
>  
>

_______________________________________________
Users-prolog mailing list
Users-prolog@...
http://lists.gnu.org/mailman/listinfo/users-prolog