The New Sudoku Players' Forum

[JasonLion]

On my machine, running PG26885 takes
ZSolve 0.389 secs
JSolve 0.652 secs.

That is checking for two solutions (the default).

[dobrichev]

For 10 copies of PG26855.txt up to the second solution here are my results

Code: Select all

JSolve  6.077 seconds
Zsolver 4.054 seconds (Jason's source)
fsss2   3.261 seconds
Zh64    3.075 seconds (Champagne's modification of Zsolver)


[rjamil]

Hi all,

Thanks for sharing timings of different programs.

Is it true that speed depends on algorithms/techniques?

My RJSolBit.CPP solves Sudoku puzzles with Naked/Hidden Singles/Tuples, Intersection Removals, Basic Fishes and Trial & Error techniques only.

Which combination/order of techniques are required to solve Sudoku puzzle faster than other programs?

R. Jamil
-----------------------------------------------------------------------
Always expect the worst and you'll never be disappointed.

[champagne]

Is it true that speed depends on algorithms/techniques?
Which combination/order of techniques are required to solve Sudoku puzzle faster than other programs?
R. Jamil

To reach the performance of the program listed by dobrichev, you have to look at the problem in a different way.

What are the things the native set of instructions of a computer can do.
what are the rules and the grid description that can use in the best way these instructions.
what are the C++ instructions translated nearly instruction for instruction in that native set

if you go in that direction, you'll see that the price to pay to detect naked or hidden pairs is already too high.

AFAIK, none of these programs use more than singles + guesses except for the zhou process using the property of a digit locked in a mini row / mini column.

choosing the best guess (again, how much do you pay to optimize the guess) is another key parameter

BTW, it took me weeks and a deep study of the fss2 code to reach an improvement of the original "Zhou" process.

[JasonLion]

All of the fastest programs use naked/hidden singles, locked candidates, and guessing with backtracking, or a sub-set of those. Beyond that, most of them also provide for various non-obvious optimizations, things like optimizing the cells used for guessing so that each guess eliminates as many potential solutions as possible, choosing to do either hidden or naked singles first, deciding to either abort the search or continue looking after discovering the first locked candidate, and on and on.

However, as champagne already pointed out, that only gets you part of the way. The choice of data structures, and the implications those structures have on how much work you can get done per machine instruction makes a huge difference. For example, the Zhou code only does row/block locked candidates and skips column/block locked candidates because column/block makes less progress towards a solution per machine instruction (given the data structures used) and so would slow down the overall process.

[rjamil]

Hi all,

AFAIK, none of these programs use more than singles + guesses except for the zhou process using the property of a digit locked in a mini row / mini column.

choosing the best guess (again, how much do you pay to optimize the guess) is another key parameter

All of the fastest programs use naked/hidden singles, locked candidates, and guessing with backtracking, or a sub-set of those. Beyond that, most of them also provide for various non-obvious optimizations, things like optimizing the cells used for guessing so that each guess eliminates as many potential solutions as possible, choosing to do either hidden or naked singles first, deciding to either abort the search or continue looking after discovering the first locked candidate, and on and on.

However, as champagne already pointed out, that only gets you part of the way. The choice of data structures, and the implications those structures have on how much work you can get done per machine instruction makes a huge difference. For example, the Zhou code only does row/block locked candidates and skips column/block locked candidates because column/block makes less progress towards a solution per machine instruction (given the data structures used) and so would slow down the overall process.

Many thanks for providing such a guideline. It gives me an impression that I have coded Naked/Hidden Tuples and Basic Fishes that slows down whole process of solving the Sudoku puzzle drastically.

I see only two download of my latest RJSolBit.CPP program up till now. Will some one please download, tweak, compile, test run and give suggestions as to how things make fast?

Note: My heuristic strategy is similar to this one answered by m09, dated Apr 13 '12 at 11:04, except in step 6, pick a sequential number instead of random. Rest seems same but in c++ i/o prolog language.

R. Jamil

[JasonLion-Admin]

R. Jamil, you have gotten way off topic for this thread, if you wish to continue this discussion please do so in a topic of your own.

Jason (speaking as an Admin)

[Serg]

Hi, 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.

I've just tried ZSolver 1.0 from your source. Nice results! I used before self-made solver in my exhaustive search projects. My program that did exhaustive search for valid puzzles run 6.3 times faster after replacing self-made solver by ZSolver (I checked Fractal Pattern)! Estimated time of doing exhaustive search for Fractal Pattern now (I checked one step of full search only) is 30 minutes (5-year old notebook having Intel Centrino 2-core CPU, procedure was running in single core mode).

I estimate 20 times higher speed for my programs used during "Investigation of one-crossing-free patterns" (40-patterns list of maximal patterns). Well, I see new possibilities with such powerful tool.

Congratulation to zhouyundong_2012 and thanks to JasonLion for his preparing the source of ZSolver!

Serg

[dobrichev]

Happy New Year!

It would be great if Zhouyundong_2012, JasonLion and Champagne collaborate and produce clear code (like Jason's ZSolver1.0.zip) that includes Champagne's improvements for earlier contradiction identification.
My observations on Champagne's mod suggested that there is small or no benefit from 64-bit data structures and the solver can be kept portable and 32-bit compatible.
Champagne's mod shows 25% improvement over a set of valid puzzles, see the above posts. Estimation for set of random mixture of valid and invalid puzzles is ~35% improvement over Jason's ZSolver1.0.zip.

[champagne]

Happy New Year!

It would be great if Zhouyundong_2012, JasonLion and Champagne collaborate and produce clear code (like Jason's ZSolver1.0.zip) that includes Champagne's improvements for earlier contradiction identification.
My observations on Champagne's mod suggested that there is small or no benefit from 64-bit data structures and the solver can be kept portable and 32-bit compatible.
Champagne's mod shows 25% improvement over a set of valid puzzles, see the above posts. Estimation for set of random mixture of valid and invalid puzzles is ~35% improvement over Jason's ZSolver1.0.zip.

Hi all and happy new year

We experienced many possibilities for the brute force.
As of to-day, I would say that 2 different programs are competing for the highest speed :

- a variant of fss form mladen dobrichev, the last known for me is fss2
- a variant of zhouyundong_2012's solver, the last one being the code I use in my programs. (in fact using some of fss2's functions)

The last versions have a code requiring a 64 bits processor, and even a recent one (I have problems with an old AMD 64 bits processor)

My first question would be : is it worth to invest in a 32 bit compatibility

I tested many variants of the zhouyundong_2012's solver. As writes mladen, the 32 bits lay out is difficult to improve.

However, I got a better result with the following changes:

relocating a digit pattern in a 128 bit field seen as 3x32 bits
keeping separate the 3 bits telling what are the rows unsolved and collecting them in a 3x32 bits area (3 digits per 32 bits field)

In that lay-out, I could introduce easily the search of cells having singles pairs or triplet, deriving the code found in fss2

At the end, the code differs from the zhouyundong_2012's solver mainly on 2 points:

In the initial process, a control of invalid puzzles has been added
The guess process gives a high priority to singles in cells and pairs in cells.

At that point, changing the code to run it in 32 bits mode is feasible, assuming this is of any value.

For my own use, I wrote an optimized version for the 27 + X + Y generation.

I know that my code is clear to me, but not necessary for others, so I would be prepared to work if necessary with a team to produce on request something easier to share.


Note: I uploaded some months ago a beta version of the last brute force, I identified meantime a bug in the "Is Minimal ?" process;

[JasonLion]

Back when I was working on my adaptation of zhouyundong's code, I found significant speed improvements (20%) when compiled for 32 bit rather than 64 bit. This was very much not what I was expecting, as nearly all applications speed up noticeably by simply compiling with the 64 bit compiler flag, with no other changes. This might not still be true for champagne's version, but I suspect it probably is.

The latest versions of fss2 require a modern x86 processor, and are incompatible with ARM CPUs. This has dampened my interest in the recent updates of fss as nearly everything I do is for ARM CPUs.

I'm fairly busy these days, but I did make one attempt to integrate champagne's improvements. However, I got lost in the code and didn't have time to fully untangle things. Zhouyundong's code is nearly impenetrable as it is, so that wasn't completely surprising.

[champagne]

The latest versions of fss2 require a modern x86 processor, and are incompatible with ARM CPUs. This has dampened my interest in the recent updates of fss as nearly everything I do is for ARM CPUs.

Hi JasonLion,

ARM cpu's is something quit new for me, but as already wrote, I have some problems with an old AMD cpu.

Part of the improvement in the last version of fss if linked to the 128 bits set of instructions, part is linked to the use of some instructions not usually available in C++ as

bitscanforward
popcount

as far as I can see, compatibility with AMD arises from the 128 bit set of instructions. More problems could come from the basic set of instructions in a ARM cpu.

But at the end, most of the cpu consumption is in the Update function and there, as you write, the 64 bit process does not bring any improvement

[Serg]

Hi, colleagues!
I am definitely interested in fastest sudoku solver, but I have several (very common) "constraints", preventing me to declare own wishes in clear form.

1. I am not experienced PC programmer. So, I cannot say what version (32/64 bit) of solver do I need. My PC environment:
CPU: Intel Core 2 Duo Processor T8300 (2.4 GHz) - 64 bit.
OS: Microsoft Windows XP Professional version 2002 SP3 (Is it 64-bit? I don't know.)
MinGW (I use "gcc" compiler, but again don't know is it 64-bit).

2. I need to integrate solver with my code. The simplest way of integration, to my mind, is including solver's source code to my programs. So, I need solver's source code. All my code is written in traditional C language (i.e. not C++), I (personally) need solver written in C. This is why I couldn't try Mladen's "fsss2" - it is written in C++.

3. My PC (notebook) is not new, but I have no possibility to buy new one just to get 20-50% gain of speed.

Serg

[tarek]

OS: Microsoft Windows XP Professional version 2002 SP3 (Is it 64-bit? I don't know.)
MinGW (I use "gcc" compiler, but again don't know is it 64-bit).

Wow Serg, I think that is a bit out of date!!!!

[JasonLion]

gcc supports both 32 bit and 64 bit, as do most other compilers. Likewise ZSolve works in both 32 bit and 64 bit modes. Newer compiler versions tend to default to 64 bit, older compiler versions tend to default to 32 bit. Both old and new compilers accept command line options to switch which mode to use. This isn't something you need to worry about unless you really want that last 15-20% of speed optimization and the solver accounts for most of your programs run time.