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 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/c8951ca1eaf83ce9de43f0483740ce339f4...
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 (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 */
