[Haskell-cafe] Code Review: Sudoku solver

[Daniel Fischer]

Am Samstag, 8. April 2006 10:21 schrieb Chris Kuklewicz:
> Daniel Fischer wrote:
> > But, lo and behold, I  also tried how plain Array fared in comparison to
> > DiffArray and ... reduced the running time to under ten minutes (a little
> > above for the list version), 5% GC time without -AxM, 1.2% with -A8M.
> >
> > And I thought, DiffArrays were supposed to be fast!
>
> No.  DiffArray's are faster for the usual imperative single threaded usage
>
> pattern.  The haddock documentation explains:

Well, it's single threaded for 31,309 of the puzzles and hasn't much branching 
for most of the others.
I hoped that when guessing was necessary, a copy was made to be used for the 
other branches, but apparently I couldn't persuade the compiler to do that.

> > Diff arrays have an immutable interface, but rely on internal updates in
> > place to provide fast functional update operator //.
> >
> > When the // operator is applied to a diff array, its contents are
> > physically updated in place. The old array silently changes its
> > representation without changing the visible behavior: it stores a link to
> > the new current array along with the difference to be applied to get the
> > old contents.
> >
> > So if a diff array is used in a single-threaded style, i.e. after //
> > application the old version is no longer used, a'!'i takes O(1) time and
> > a // d takes O(length d). Accessing elements of older versions gradually
> > becomes slower.
> >
> > Updating an array which is not current makes a physical copy. The
> > resulting array is unlinked from the old family. So you can obtain a
> > version which is guaranteed to be current and thus have fast element
> > access by a // [].
>
> I assume the usage in a Sudoku solver involves a non-trivial amount of
> back-tracking.  So as the solver backs up and goes forward again it ends up
> being much more work than having used a plain Array.

I tried to keep backtracking to a minimum, and in most cases that minimum is 
reached.
>
> And as was pointed out by someone else on this list: to be thread safe the
> DiffArray uses MVar's (with locking) instead of IOVars.
>
> But I expect the main problem is that a DiffArray is simply not the right
> mutable data structure for the job.

Should I try an MArray? 
And what's more promising, IOArray or STArray?
>
> I have had the flu this week, so I did not finish cleaning up my port of

So did I, hope you're well again.

> Knuth's mutable dancing links based Sudoku solver.  But it uses a much more
> lightweight way to alter a mutable data structure both going forward and
> backwards while backtracking.  And I can use STRef's to build it, instead
> of MVars.

Cheers,
Daniel
-- 

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
	-- Blair P. Houghton