The New Sudoku Players' Forum

[zhouyundong_2012]

OK!
How about speed of the new version?

[zhouyundong_2012]

I want to post my complete code and explaination to here.(include GT/LT,Extra,Jigsaw,Sum),but I have no net harddisk to upload.

[JasonLion]

Files from zhouyundong_2012:
斗智数独_1.0.0.rar
WinLib.rar

[zhouyundong_2012]

Can you run the software? Maybe some pictures is better to reader to use it.

[JasonLion]

I put together a small archive with the next to last version of zhouyundong_2012's solver, converted over to standard C code and repackaged with a standard interface that makes calling form other software very easy.

http://forum.enjoysudoku.com/software/ZSolver1.0.zip

Zhouyundong_2012's solver is amazingly fast, better than JSolve and other state of the art brute force solvers across a variety of puzzle types.

top1465 (20 times)
JSolve 1.37
ZSolve 1.05

multipuzz
JSolve 9.12
ZSolve 4.29

top50000
JSolve 0.79
ZSolve 0.44

Tarek_Pearly6000
JSolve 1.03
ZSolve 0.70

sudoku17
JSolve 0.60
ZSolve 0.28

[GouinJP]

I put together a small archive with the next to last version of zhouyundong_2012's solver, converted over to standard C code and repackaged with a standard interface that makes calling form other software very easy.

http://forum.enjoysudoku.com/software/ZSolver1.0.zip

Zhouyundong_2012's solver is amazingly fast, better than JSolve and other state of the art brute force solvers across a variety of puzzle types.

It's true. Really fast.

Congratulations to Zhou and thanks to JasonLion

[zhouyundong_2012]

Do you think this program is worth to study for student?
Do you think this program can be written into book for chapter bitset?

[zhouyundong_2012]

I invent a program arithmatic "astable node", abbr is Astode.
It can solve Chinese Chess Composition For Continue Check.
The traversal depth is 600.The speed is fastest in the past 5 years.

[dobrichev]

Hi,

I compiled Zsolver and yes, it is really fast. Congratulations to Zhou Yun Dong!

Here are my timings

Code: Select all

         17   20x1468   50k   500K gen
Zsorver  0.484  1.468   0.687   1.953
ZsolverO 0.593  1.874   0.859   2.093
Jsolve12 0.781  1.687   1.046   1.843
fsss     0.718  1.562   1.062   1.343


Interestingly, ZsolverO is exactly the same code but compiled with aggressive optimizations which obviously are killing the performance in this case.

Do you think this program is worth to study for student?
Do you think this program can be written into book for chapter bitset?

Not in this form. On first sight bitset operations are exploited, but maybe also parallelism is done (single instruction processes 3 values packaged in a 32-bit word simultaneously, right?) Some explanation is welcome. I personally failed in reverse engineering the logic for the first one hour.
So, writing a detailed explanation is a good task for a student.

Cheers,
MD

[zhouyundong_2012]

I have written a Explaintion which has some picture figure what is Palace,Chute, Initialization,Column Exclude, Double Column Exlcude,Single Grid Exclude methods in Excel form in Chinese,but difficult write in English.

I have also written a Software which called ChineseChess crack and generation.It is the fastest software and has gen function based on the fastest crack speed, in that field.
I have rewritten it in bitset mode,get rid of most "while","for",it is improved 20% at least.
I have rewritten it in algorithmic layer, it is improved another revolutionaly.
They say that I made the most and incomparable contribution in ChineseChess Continuous Check composition.

[zhouyundong_2012]

Any improvement?

[GouinJP]

Any improvement?

Difficult to do faster than your program!

I use it everyday. Thank you very much Zhou.

JPS
.

[dukuso2]

how long did it take, how much work was it

[dukuso2]

walking through this thread ... (omitting the source codes)

zhouyundong_2012 wrote:

> I will improve my GT/LT Solver.
> Cross Method, but it is slower
> Method: SingleGrid, SingleRow, SingleColumn, DoubleColumn, UniqRow, Guess and Rollback
> The code is very "Simple" and very easy to comprehense.
> My source code is very readable, short , very easy to comprehense.
> If I post my source code here, all improvement belongs to me , ok?
> Do you love this program?
> 3 files: sd.h Tbl.cpp sd.cpp. This version posted on 2012/3/14 is the last version.
>I have also made a visible software,it includes Killer, GT/LT, Extra, and Mix of them.

JasonLion wrote:
:I have been slowly working my way through the source code. zhouyundong_2012 uses an array
: of int where each element holds one chute (three rows) of basically pencil marks for a single
: digit. I say "basically pencil marks" because I think placed digits are also set. The solver
: appears to use locked candidates (perhaps incompletely) and hidden singles.
: I haven't seen anything that appears to be doing naked singles, and I can't quite figure out
: if it really does column-block locked candidates, or only does row-block locked candidates.
: The row-block locked candidates code is very very short and fast, quite entertaining reading
: for bit twiddling wonks like me.

> I did not do column-block locked canididate. I think column-block can't work well.)
> I have written an doc to explain the details of this solver.But it is written in Chinese.

: software/ZSolver1.0.zip


---------------------------------------------------------

I get the impression that these are not improvements of the solving algorithm
but rather a more advanced "adaption" to the processor specifics.
While the best solving algorithm is more or less clear now and no
further improvements are expected.

right ?

[JasonLion]

For me, the elegance of zhouyundong_2012's code lies in how tightly integrated everything is into one "piece". Data structure and algorithm are matched together to achieve an amazing level of minimalism. For example, the data structure used lends it's self very neatly to row/column locked candidates, which come essentially for free through minor adaptations of portions of the hidden singles code. Meanwhile column/block locked candidates were left out, apparently because they don't fit as neatly with the data structure and would thus lower the overall efficiency.

At this point I have tried almost a dozen tweaks to the code to see if I could improve anything, but every change I have come up with makes it less efficient. If there is any way to go faster, it is almost certainly going to need to use an entirely different approach.