The New Sudoku Players' Forum

[Mathimagics]

I just wanted to note that Zsolver would also be trivial to adapt.

Indeed, I'm sure Jason's Zsolver would be easily adapted, and is equally admirable (a nod to the forum administrator ) , but I will stick with the fsss2 solver which I now understand, and has everything I need for various purposes I have in mind!

[Mathimagics]

.
Oh, and finally we have resolved the original question about that UA collection method (which was the original objective).

And yes, finally, we can confirm that dobrichev's original statement about this was absolutely spot on!

• if we guide the solver by making the full solution grid available

AND

• collect the unresolved cells at the point of the FIRST guess (*)

Then those cells indeed constitute a minimal UA ...

==============================================================================================
[ EDIT * ] The puzzles I have been testing are of course of a particular kind. I removed random clues from the full grid until the solution was no longer unique. Thus the puzzle at "UA collection" point were only 1 clue from resolution. In these cases it is not even necessary to provide the known solution grid.

The general case (eg as might apply in a HS enumeration) would presumably need the "known solution" to be given, AND the UA collection would need to be at the LAST guess.

I need to run some more tests, but I think this will turn out to be the case, just as Mladen predicted.

[Serg]

Hi, Mathimagics!
You said you are programming in traditional C language. But fsss2, as far as I know, is written in C++. Have you any problems during compiling fsss2 together with you code (in traditional C)? What compiler did you use to compile fsss2? (gcc, ...)

Serg

[dobrichev]

Hi Serg,

First of all, my congratulations on your empty box analysis of the sudoku with disjoint groups. Well done. As always.

fsss2 in its current version is strongly dependent on C++ language extensions. If you want to migrate it to pure C, I would recommend starting from some older version where maybe the only change would be replacing the structure assignments to memcpy().

If you have problems in mixing C with C++ code, then the general rule is that C++ almost entirely covers C w/o requiring any modifications in the C source code. (there are several exceptions in some exotic nuances of the protocols, but IMO it is unlikely for your code to be affected). In short - use a C++ compiler and compile your mixture of C and C++ code.

If you have troubles with particular compiler, let me know some details and I will try to do the fixes.

Note that fsss2 is stable only when solving a puzzle. There is a bunch of unfinished and untested functionalities which I don't recommend to use at the moment. Unless you want to contribute

Cheers,
MD

[Serg]

Hi, Mladen!

First of all, my congratulations on your empty box analysis of the sudoku with disjoint groups. Well done. As always.

Thanks!

It happened that I am using traditional C language in my sudoku studies. This language is powerful and transparent. Maybe C++ is powerful and transparent too. I am too lazy to study another powerful programming language, since I feel traditional C language is quite adequate in my sudoku studies.

So adapting fsss2 is too complicated for me. If Mathimagics adapted fsss2 for SudokuP solving (and for calling it from C environment), it would be nice opportunity for me to use fsss2 - naturally, if you do not mind my using fsss2.

Serg

[Mathimagics]

.
Hi Serg.

I am certainly no expert in C++, but I can save you some heartburn by giving you my dobrichev SudokuP solvers (fsss and fsss2). I will email them to you.

We can call C++ library from C by having the library export functions that do any necessary class instantiation, so caller does not see class-level stuff.

[Serg]

Hi, all!
I searched for fast SudokuP solver and found it. It was not so simple to get such solver for me because of my PC specific - such solver must be callable from traditional C and must run in 32-bit MS Windows environment. I'm grateful to Mathimagics, who adapted Mladen Dobrichev's fsss Sudoku solver for solving SudokuP puzzles and found the way to execute it in 32-bit MS Windows environment.

I've done benchmark tests for my SudokuP solver and modified fsss Sudoku solver (let me call it FSSSP). Benchmark contained 1000000 puzzles generated in exhaustive search project ("SudokuP Empty Boxes"). All of them had multiple solutions. My solver processed them at the rate 9300 puzzles/sec, but FSSSP processed them at the rate 52000 puzzles/sec (my PC rates). So, FSSSP is more than 5 times faster than my solver! Now I expect to get 2-3 times speeding up in my SudokuP exhaustive search projects.

Thanks to dobrichev and Mathimagics for their help!

Serg

[Mathimagics]

.
The credit is 99.99% due to dobrichev, I merely tinkered at the edges.

While I'm here, it's worth commenting on fsss2. It not only has very fast solving rates (for those of us with 64-bit systems that can exploit it), but is remarkably easy to adapt for Sudoku variants.

I have built fsss2 versions for SudokuP, SudokuPX, and SudokuX. I wrote a program that generates the header files for the 128-bit tables needed for each variant, and then simply compiled the result. The only code I had to change was the house bits assignment, to support > 32 houses, but that's a one-off modification.

I now have a version that solves Jigsaw's, where the tables can be created on the fly given a pattern string.

So hats off to you, Mladen, a nice piece of work indeed ...