4

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

false
  • 10,264
  • 13
  • 101
  • 209
Dieter
  • 2,499
  • 1
  • 23
  • 41
  • gprofile could help you, browse the manual – CapelliC May 30 '14 at 15:31
  • gprofile? is it the same as profile/3? – Dieter May 30 '14 at 15:36
  • 2
    profile/1, sorry I didn't remeber well – CapelliC May 30 '14 at 15:39
  • and this will return me the amount of backtracks? because that is what I need – Dieter May 30 '14 at 15:40
  • should open a GUI where there are REDO count – CapelliC May 30 '14 at 15:41
  • It doesn't really satisfy my answer. Because the REDO isn't the amount of backtracks, but the amount of times that a clause executes something again. – Dieter May 30 '14 at 16:08
  • 2
    You can take the number of inferences shown by statistics as a pretty good architecture independent and reproducible approximation for efficiency, should CPU-time be not good enough for you. – false May 30 '14 at 16:33
  • a REDO should happens just as a consequence of backtracking... – CapelliC May 30 '14 at 16:42
  • 1
    @Dieter when Prolog goes back to execute a clause again (REDO) to try to find another solution that's what backtracking is. – lurker May 30 '14 at 16:42
  • @Lurker, you're correct and not correct :) because of the reason that i'm using chr, i think that i've a lot of false calls and redo's for this reason. But both, CapelliC and you, where helpful – Dieter May 30 '14 at 18:17

1 Answers1

2

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
Community
  • 1
  • 1
SND
  • 1,552
  • 2
  • 16
  • 29