[Haskell-cafe] Code Review: Sudoku solver

[Daniel Fischer]

Am Freitag, 7. April 2006 01:50 schrieben Sie:
> On Apr 6, 2006, at 6:05 PM, Daniel Fischer wrote:
> > I've also written a version using David F. Place's EnumSet instead
> > of [Int],
> > that takes less MUT time, but more GC time, so is slower on the
> > 36,628 test,
> > but faster for a single puzzle.
>
> That's a curious result.  Did you compile with optimization?  It

I considered that curious, too.
Everything was compiled with -O2 (does -O3 give better results?, would adding 
-optc-On improve performance? I'll try).
What makes it even weirder is that the EnumSet-version does indeed allocate 
fewer bytes and performs fewer garbage collections (small difference, 
though).
But I got consistent results, when running on a large number of puzzles, the 
list-version's faster gc'ing led to shorter overall run times.
The same held when compiled with -O3 -optc-O3, however, I've been stupid,
my excuse is that I was ill this week, the list version spent 46.5% gc'ing and 
the set version 53.5%, which is not really cricket, so today I used -AxM,
x <- [10,16,32,64], all reducing GC time to reasonable 0.5 - 2%. That, plus a 
few polishings, reduced the running time to about 16 minutes for EnumSet, a 
little more for lists. 

But, lo and behold, I  also tried how plai 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!

> should compile into primitive bit-twiddling operations and do no
> allocating at all.  I'd be curious to see how fast my solver works on

Well, since I've wrapped the sets in the Entry datatype, I wouldn't expect 
that, switching from Poss (singleton k) to Def k costs.
I tried making Board a DiffArray (Int,Int) (Set Int), but then I had the 
problem that either I lost the information gained by placing & forbidding for 
those positions where the number of possibilities dropped to one by 
inference, or had to scan the grid and re-place every now and then, both 
resulting in poor performance.

> the 36,628 test.  I'm afraid to run my ancient limping powerbook in
> such a tight loop for that long.  It gets too hot!
>
> If you'd find it amusing to give it a whirl, I'd love to know the
> result.

I ran your incrsud on the first fifteen 17-hint puzzles, took over 20s, so I 
decided against the full 36,628 test. Extrapolation makes me believe it'd 
take thirteen to fourteen hours.
The really big thing is to include the "if there is only one place to put a 
number in a row/column/cell, then put it there" inference step. Further 
inference has smaller impact (but the group-inference bought me a 20% 
speedup, which isn't bad, is it?).
But using Array instead of DiffArray gave almost 40%, that's impressive.

Attached is the fastest version I have, oddly, compiled with -O2 it's faster 
than with -O3 -optc-O3 (on my computer), how come?

setUni +RTS -A8M -sstderr
True
99,859,933,904 bytes allocated in the heap
104,713,900 bytes copied during GC
    150,260 bytes maximum residency (72 sample(s))

      11558 collections in generation 0 (  6.83s)
         72 collections in generation 1 (  0.16s)

         13 Mb total memory in use

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time  554.68s  (568.29s elapsed)
  GC    time    6.99s  (  7.22s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time  561.67s  (575.51s elapsed)

  %GC time       1.2%  (1.3% elapsed)

  Alloc rate    180,031,610 bytes per MUT second

  Productivity  98.8% of total user, 96.4% of total elapsed

an average of 0.015s per 17-hint puzzle, cool!

Cheers,
Daniel

>
> --------------------------------
> David F. Place
> mailto:d at vidplace.com

-- 

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
	-- Blair P. Houghton
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SudokuSet.hs
Type: text/x-haskell
Size: 13960 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060408/25180f2d/SudokuSet.bin