[Haskell-cafe] progress reporting in a backtracking algorithm

[Harald Bögeholz]

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:

I have a function

step :: State -> Index -> [State]

that on a certain level tries all allowable varaiants and returns a list
of those that can be further pursued on deeper levels.

Then solving the problem involves applying the step on all levels
(whicht are indexed by some array indices here):

solve :: Problem -> [State]
solve problem = foldM step start grid
    where start = stateFromProblem problem
          grid = indices (sLines start)

I am totally at loss at how I could accomplish some kind of progress
reporting in this lazily evaluated (I hope) backtracking scheme.

If anybody would like to review the full code (about 80 lines total vor
the solver, not counting I/O), this is where I am right now:

https://github.com/ctbo/slitherlink/tree/c8951ca1eaf83ce9de43f0483740ce339f4134ae

and this is the branch I am working on right now:

https://github.com/ctbo/slitherlink/tree/2lines

Or is there maybe a totally different and better way to approach this
kind of tree search in Haskell? I'm eager to learn.


Thanks for your attention
Harald

-- 
Harald Bögeholz    <bo at ct.de> (PGP key available from servers)
Redaktion c't      Tel.: +49 511 5352-300  Fax: +49 511 5352-417
                   http://www.ct.de/

                   int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
                   main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a)
                   while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
                                                          (Arndt/Haenel)

                   Affe Apfel Vergaser

/* Heise Zeitschriften Verlag GmbH & Co. KG * Karl-Wiechert-Allee 10 *
   30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
   Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
   Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
   60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */