[Haskell-cafe] Code Review: Sudoku solver

[Daniel Fischer]

Am Samstag, 8. April 2006 20:28 schrieb Chris Kuklewicz:
> I have finished my cleanup of the dancing links based solver for Sudoku.
>
> I don't have time to compare performance with the other programs that have
> been posted recently, or to do more profiling of my code.

Your dancing links:

ckSud +RTS -sstderr -H32M -A8M < sudoku17 > Solutions.txt
ckSud +RTS -sstderr -H32M -A8M
62,941,602,892 bytes allocated in the heap
330,404,632 bytes copied during GC
    465,944 bytes maximum residency (41 sample(s))

       2023 collections in generation 0 ( 15.60s)
         41 collections in generation 1 (  0.30s)

         32 Mb total memory in use

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time  734.59s  (781.93s elapsed)
  GC    time   15.90s  ( 16.73s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time  750.49s  (798.66s elapsed)

  %GC time       2.1%  (2.1% elapsed)

  Alloc rate    85,682,629 bytes per MUT second

  Productivity  97.9% of total user, 92.0% of total elapsed

Without -HxM, -AxM:

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time  597.47s  (915.94s elapsed)
  GC    time  912.65s  (1363.63s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time  1510.12s  (2279.57s elapsed)

My version using EnumSet (with the faster 'size'):

sudokus +RTS -sstderr > Solutions
sudokus +RTS -sstderr
82,190,535,600 bytes allocated in the heap
771,054,072 bytes copied during GC
    153,512 bytes maximum residency (394 sample(s))

     286104 collections in generation 0 ( 33.98s)
        394 collections in generation 1 (  0.35s)

          2 Mb total memory in use

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time  482.51s  (1105.12s elapsed)
  GC    time   34.33s  ( 79.90s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time  516.84s  (1185.02s elapsed)

  %GC time       6.6%  (6.7% elapsed)

  Alloc rate    170,339,548 bytes per MUT second

  Productivity  93.4% of total user, 40.7% of total elapsed

Nice that original Haskell code can beat a translation from C.

However:
setSud ../puzzle3992 +RTS -sstderr
628|743|159
395|261|478
174|589|632
---+---+---
832|195|764
746|328|591
951|674|283
---+---+---
213|956|847
469|817|325
587|432|916
===========
888,672,920 bytes allocated in the heap
  3,352,784 bytes copied during GC
     45,648 bytes maximum residency (1 sample(s))

       3287 collections in generation 0 (  0.21s)
          1 collections in generation 1 (  0.00s)

          2 Mb total memory in use

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    4.77s  (  4.77s elapsed)
  GC    time    0.21s  (  0.22s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    4.98s  (  4.99s elapsed)

  %GC time       4.2%  (4.4% elapsed)

  Alloc rate    186,304,595 bytes per MUT second

  Productivity  95.8% of total user, 95.6% of total elapsed

But
ckSud +RTS -sstderr < oneBad
ckSud +RTS -sstderr
(1,"673941852148256379295378461534167928826594713917832546351729684762483195489615237")
(2,"683941752179258463245376918534167829826594371917832546351729684762483195498615237")
(3,"829143657361785492547629381678954213934271568215836974152468739486397125793512846")
(4,"713642958825917436649835127594781362378264519261593784136478295482359671957126843")
(5,"763942158425817936189635427594781362378264519216593784631478295842359671957126843")
(6,"269743158371865924458921637945137286836492571712658349597386412683214795124579863")
(7,"269743158371865924485921637943157286856492371712638549597386412638214795124579863")
(8,"628743159395261478174589632832195764746328591951674283213956847469817325587432916")
(9,"983541762761328945524679813679483251835162497142957638457816329296735184318294576")
(10,"578942361923165748614837925867491532235786194149253876796514283452378619381629457")
(11,"938145762127396854654872931873629145546713289291584673415967328369258417782431596")
(12,"792548361531672894846931572657384129483129657219756438965817243174263985328495716")
(13,"738249561296517483154386927673192854981654372425873619547928136319765248862431795")
(14,"957842361386719452124653879598364127673281945412975638845137296231596784769428513")
(15,"598241367673958124421736985254873691317692548986415732742169853165384279839527416")
 25,708,036 bytes allocated in the heap
  9,097,220 bytes copied during GC
    329,648 bytes maximum residency (5 sample(s))

         97 collections in generation 0 (  0.42s)
          5 collections in generation 1 (  0.04s)

          2 Mb total memory in use

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.23s  (  0.23s elapsed)
  GC    time    0.46s  (  0.46s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.69s  (  0.69s elapsed)

  %GC time      66.7%  (66.7% elapsed)

  Alloc rate    111,774,069 bytes per MUT second

  Productivity  33.3% of total user, 33.3% of total elapsed

The infamous puzzle 3992 is the eighth in oneBad, so the links dance rings 
around me for that.
I wonder where the dancing links run into difficulties.
I'll see whether I can grok (that does mean understand, doesn't it?) your 
programme one of these days.

>
> For those who will say "It is ugly, imperative, and ugly!" please remember
> this is a conversion of Knuth's c-code, which depended on five non-trivial
> goto jumps because he did not have tail recursion.  And the whole point of
> the algorithm are the imperative unlink & relink routines acting on a
> sparse binary matrix.
>
> This does not use any clever logic, but it does pick the tightest
> constraint at every step.  This means if there is only one obvious
> possibility for a position/row/column/block then it will immediately act on
> it.
>
> The literate source file is attached.
>
> [ My clever logic solver may eventually be cleaned up as well. ]

I really would like to see that.

Cheers, 
Daniel

-- 

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