How can you count, the amount of backtracks in Prolog SWI or CHR Prolog SWI

Question

I'm creating several puzzle solvers in Prolog SWI with CHR (Constraint Handling Rules)

Everything works great but, I like to test which solver is best one. Therefore I like to find out, which solver uses the least amount of backtracks.

Is there a clever way to find out (or print out), the amount of backtracks that the solver had needed for solving a particular puzzle?

Logically, counting would help, but it doesn't --> backtracking ! <-- . Also, printing a new line on the screen isn't effective, because of SWI's GUI. You can't print more than +/- 50 lines and can't select properly

Answer 1

It is indeed not trivial to accomplish this, given Constraint Handling Rules maintain a 'constraint store' and execution of rules may add, rewrite or remove rules from this store at runtime. This changes the state of the program and makes it somewhat difficult to keep track of global states throughout execution.

However, since CHR is integrated in SWI, you can make use of the non-logical operation nb_setarg/3 to keep count of the backtracks.

Notes from the doc:

• Compatible with GNU-Prolog's setarg(A,T,V,false)

• This implementation is thread-safe, reentrant and capable of handling exceptions

EDIT

As regarding where to count the backtracks, this of course depends on your program, but will usually occur in the CHR constraint rule that defines the fail condition of your search, allowing it to 'branch' (= rewrite CHR rules). Every time a rewrite of the constraint store occurs during search, it represents a backtrack and you can increase a counter accordingly using the operation as defined above.

Consider a small, abstract example:

invalid_state ==> increment_backtracks, fail.
        guess <=> branch