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