The New Sudoku Players' Forum

[dobrichev]

Hi,
I am copying here few posts I initialy did in the former Sudoku Programmers forum, which seems to be dead from few weeks.

Fast Simple Sudoku Solver 2 has been released and C++ source is available at https://github.com/dobrichev/fsss2

It is entirely redesigned successor of fsss (https://sites.google.com/site/dobrichev/fsss/)

The new design exploits 128-bit arithmetic.

Currently it requires Intel® Streaming SIMD Extensions (Intel® SSE4) for packed integer 128-bit comparisons but could be compiled with minor modifications and less than 15% performance loss to Intel® Streaming SIMD Extensions 2 (Intel® SSE2).

The new solver is still immature, not well tested, and possibly has room for further optimizations.

Below is a time comparison between the old fsss, two alternatives of the fsss2, and the fastest known solver ZSolver.

Code: Select all

                                 17puz48826 1465x20   50000   Tarek  gen_puzzles 38puz540512 hard817681
                                                             Pearly       500000
                                                               6000

Solve       fsss v9.x                 0.299   0.699   0.457   0.612        0.319       4.847    120.447
up to the   fsss2 v0 no line-box      0.345   1.058   0.336   0.485        0.262       2.902     86.891
second      fsss2 v0 line-box         0.256   0.689   0.368   0.498        0.268       3.329     88.269
solution    ZSolver                   0.203   0.784   0.321   0.527        0.664       2.897     85.800

Solve       fsss v9.x                 0.351   0.764   0.354   0.330        0.311       3.523     65.587
up to the   fsss2 v0 no line-box      0.250   0.603   0.240   0.268        0.255       2.059     45.814
first       fsss2 v0 line-box         0.227   0.432   0.291   0.275        0.264       2.481     46.828
solution    ZSolver                   0.175   0.425   0.232   0.283        0.658       2.119     44.692


Times are in seconds, the testing platform is 64-bit Linux on Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz, the compiler is Intel® 64 C++ Compiler v14.0.0.

Comparison of the latest fsss2 and ZSolver, solving up to the second solution.

Code: Select all

   
      17puz48826 1465x20   50000   Tarek  gen_puzzles 38puz540512 hard817681
                                  Pearly       500000
                                    6000

fsss2      0.284   0.913   0.315   0.429        0.239       2.688     78.952
ZSolver    0.203   0.784   0.321   0.527        0.664       2.897     85.800

Time comparison of today's source code release of fsss2 to ZSolver, solving up to the second solution.
This release is compatible with GCC C++ compiler.

Code: Select all

      17puz48826 1465x20   50000   Tarek  gen_puzzles 38puz540512 hard817681
                                  Pearly       500000
                                    6000

fsss2      0.252   0.808   0.277   0.375        0.228       2.283     69.308
ZSolver    0.203   0.784   0.321   0.527        0.664       2.897     85.800

I am planning to post here any improvements related to this solver.

[dobrichev]

The solver has been involved in the high-clue search, comparisons of large amount of data produced by the independend old solver and this one has been done and no discrepancies (bugs) have been found. To me it is a stable, fast, thread-safe solver useful for resolving hard tasks on modern hardware.
Below are the timings for the current release. Two versions are still supported - one w/o line-box interactions processing (locked candidates), which gives better results for the hard and high-clues puzzles, and one with partial line-box interactions processing, which gives better results for the easy and/or low-clue puzzles.

Code: Select all

                                 17puz48826 1465x20   50000   Tarek  gen_puzzles 38puz540512 hard817681
                                                             Pearly       500000
                                                               6000

up to the   fsss2 no line-box         0.230   0.770   0.260   0.352        0.194       2.103     63.814
second      fsss2 line-box            0.186   0.558   0.296   0.365        0.210       2.507     65.722
solution    ZSolver                   0.203   0.784   0.321   0.527        0.664       2.897     85.800

up to the   fsss2 v0 no line-box      0.185   0.447   0.197   0.191        0.192       1.508     33.963
first       fsss2 v0 line-box         0.167   0.348   0.237   0.198        0.207       1.876     34.904
solution    ZSolver                   0.175   0.425   0.232   0.283        0.658       2.119     44.692


In today's update I added makefile in the repository. It works for GCC and Intel Compiler under 64-bit Linux.
So far there are no plans for migration to 32-bit OS.
It is possible some day the source to be made compatible with Microsoft Visual Studio for Windows. Any colaboration in this direction is welcome.
The solver is free.

[champagne]

It is possible some day the source to be made compatible with Microsoft Visual Studio for Windows. Any colaboration in this direction is welcome.
The solver is free.

Hi Mladen,
fss is in use in skfr under microsoft visual studio.

Do you have any reason to think that there could be problems with fss2

[dobrichev]

No, I have no reasons and hope it is matter of few hours to resolve the possible incompatibilities with MSVS.
The difference between fsss and fsss2 is that the first was born in 32-bit Windows environment and the second was born in Linux 64-bit environment.
There are several operations where 32-bits OS will definitely degrade the performance (the 64-bit operations must be split to series of 32-bits operations).
I have no suitable enviroment for fast edit/compile/test on Windows environment. The possible zero consumers refrain me to do any efforts in this direction.
Fsss2 doesn't use any OS specific functions. Possible problems are syntax discrepancies between Linux-oriented compilers and Windows-oriented ones. The C++ code wouldn't be a problem, but usage of compiler-specific intrinsinc functions for forcing the use of 128-bit registers would be.

[JasonLion]

I finally got fuss2 to compile on my Mac. The -flto command line option was causing strange problems. Once I removed that, everything started to work.

I was able to speed things up just a little, at least for my compiler. The calls to _mm_prefetch/__builtin_prefetch seemed to hurt, removing them improved things. I aslo switched findBiValueCell to start with the next digit after the last one examined in the previous call, instead of starting with 1 each time. Those two changes seemed to improve things by roughly 2%.

I tried compiling with clang, instead of gcc, but that slowed things down just a little bit.

Finally, I noticed that comparisons between fsss2 and ZSolver are not completely fair. The fsss2 file handling code is a little less general purpose and faster than the similar code in ZSolver. This code is not properly part of the solver, but is unavoidably included in the timings. The difference isn't enough to change the overall results in any significant way, but does bias the comparison by perhaps four percent in favor of fsss2.

[dobrichev]

Hi Jason,
Thank you for your interest in fsss2.

I finally got fuss2 to compile on my Mac. The -flto command line option was causing strange problems. Once I removed that, everything started to work.

This suggests that you are using old version of gcc. I use 4.8.2.

The calls to _mm_prefetch/__builtin_prefetch seemed to hurt, removing them improved things.

It is quite possible. And there is more fun.
There is one commented prefech for {-1,-1} constant. When uncommented, looking at disassembly, the same constant is put in a register out of the loop, making the prefetch obviously useless. Profile shows that about 1 second (from total 64 for the hardest sudokus) is spent for this prefetch. Nevertheless the overal performance IS improved, say by half second. Similar example is adding the trials counter - one global integer incremented before each guess. With the counter, execution is measurable better than w/o it.

For fsss2 compiler optimization is of very high importance. I tried to rewrite parts of the code in attempt to decrease the difference between compiler optimized and non-optimized versions and had very limited success. Zsolver is much better in this aspect.
I always compile with profile-guided optimization. But, for example, to achieve best results for hardest puzzles, profiling is done on 38-givens puzzles. Profiling over the same set of puzzles doesn't work as expected.

I aslo switched findBiValueCell to start with the next digit after the last one examined in the previous call, instead of starting with 1 each time. Those two changes seemed to improve things by roughly 2%.

Thank you for the effort. This was in my todo list and I expected more significant improvement.
Is "the next digit" the next cell position [0..80] or the next digit [0..8]?
Which version of source files you started with? After the update from this week, the logic for finding bi-values has been replaced with logic for finding the cells with less possible values which could include 2, 3, 4, or more values (Thanks to Blue). This in theory can change the improvement.

Finally, I noticed that comparisons between fsss2 and ZSolver are not completely fair...

Surely the comparison is inaccurate and biased. I still hope the error is within +/- 5%.