Harald Bögeholz | 21 Sep 08:29 2012

progress reporting in a backtracking algorithm

Dear Haskell Cafe,

I am playing around with a backtracking algorithm that can take quite a
while to compute all solutions to a problem.

I'd like to use Debug.Trace.trace to provisionally output something that
lets me estimate the total time it might take. But I just can't wrap my
head around it.

This is how I think I'd write it in a C-like language:

backtrack(int level, double position, double stepsize, misc...)
   // with variations = number of variations to try on this level
   double part = stepsize / variations // split time on this level

   for (i=0; i<variations; ++i)
      double current = position + part*i
      // do the actual work
      backtrack(level+1, current, part);
      if (level < not_too_much_detail)
         printf("progress: %f%%\n", current);

and start with backtrack(1, 0.0, 100.0).

And now for something completely Haskell:

(Continue reading)