The New Sudoku Players' Forum

[champagne]

Hi, champagne!

I'll try to-day to produce a 32 bits version of sk_bruteforce. If the changes needed are limited to the BF128 class, it should be easy.

I am waiting for your result. Hope, producing a 32-bit version of sk_bruteforce will be not complicated.

as written above, it's done, changes in BF128 were enough to compile in X86 mode with Microsoft Visual Studio. I don't have the tools to test gcc 32 bits

Do you mean new benchmark file, having 163-symbol strings of such form: puzzle + ";" + solution (81+1+81 symbols)?
Serg

Yes, If you know the first solution, you can use it to save time in the guess sequence. What I do is to start with the "false" in a bi-value cell. The first solution shows a multiple solutions puzzle.

[Mathimagics]

.
Hi champagne!

In the header comments for JCZSolver.c we find:

Code: Select all


   Subsequently updated by user champagne for 128 bit registers and speed optimization.
   Key insights include the pairing of ApplySingleOrEmptyCells and GuessBiValueInCell

   Converted back to 32 bit data with further speed optimizations by JasonLion.


Is it possible to obtain a version that uses 128-bit registers?

Is the "sk_bruteforce" discussed above effectively the same thing (with further improvements)?

I'm doing a little benchmark investigation (in another context) of my own, and would like to include this.

[champagne]

.
Hi champagne!

In the header comments for JCZSolver.c we find:

Code: Select all


   Subsequently updated by user champagne for 128 bit registers and speed optimization.
   Key insights include the pairing of ApplySingleOrEmptyCells and GuessBiValueInCell

   Converted back to 32 bit data with further speed optimizations by JasonLion.


Is it possible to obtain a version that uses 128-bit registers?

Is the "sk_bruteforce" discussed above effectively the same thing (with further improvements)?

I'm doing a little benchmark investigation (in another context) of my own, and would like to include this.

I think that Jasonlion maintains a pure 32 bit version to use it on other chips (to be confirmed by him), I work specifically on Intel/Amd sets of instructions, but sk_bruteforce is in a similar frame. Reading the comments, I think that jasonlion changed the guess sequence to give priority to bi-value cells and bi-value "digits" as in my last version of code. If we except very hard puzzles, this covers nearly all brute solver uses. The last "average bonus" was to choose the bi value cell in the band with more unsolved cells.

[Mathimagics]

Thank you, champagne.

I have been filling in some of the gaps in my knowledge by reviewing the history of this thread, and am now satisfied that JCZSolver is the most suitable for my purposes, and that no other version is necessary for my current investigation.

May I add my (retrospective) congratulations to those of Serg, to all involved in the development of this software: Zhou, Champagne, Jason. Nice work, gentlemen!

And for fsss2, Mladen (and blue), well done you too!

BTW, it is an interesting experience to go back to the OP, and consider the initial reactions to Zhou's first posts … what a long journey since then!

Best regards to all!
MM

[Serg]

Hi, champagne!

as written above, it's done, changes in BF128 were enough to compile in X86 mode with Microsoft Visual Studio. I don't have the tools to test gcc 32 bits

Could you send this solver to me? If it is possible, it would be nice to see simple progam with call example too.

Do you mean new benchmark file, having 163-symbol strings of such form: puzzle + ";" + solution (81+1+81 symbols)?
Serg

Yes, If you know the first solution, you can use it to save time in the guess sequence. What I do is to start with the "false" in a bi-value cell. The first solution shows a multiple solutions puzzle.

I prepare benchmark file with puzzle+solution pairs. You can download it from http://sites.google.com/site/sergsudoku/benchmark_1st_sol.zip.

Serg

[champagne]

Could you send this solver to me? If it is possible, it would be nice to see simple progam with call example too.

I prepare benchmark file with puzzle+solution pairs. You can download it ...

Serg

Hi Serg,

I have the file. I guess that you first create the sotlution, then check if ii is valid in specific condition. This is a typic situation where you can use a tailor made process.
I am busy to-day, but I should find the time to transfer the specific guess process, verify the gcc compability and test it.
I'll then prepare a zip file to download unless you have another channel to exchange data.
BTW, we can have part of our discussion in pm to avoid pollution of the thread
chanpagne

[emerentius_]

Hi emerentius,
I have seen something wrong in the "One digit guess"
I'll do more checks to-day before the fix of the code

EDIT: fix done, I did not run the regressive test on hardest puuzzles after the last code change. There was an error.
I also increased to be safe the size of the "one digit solutions" table. (a problem in the 17 clues search, may be linked to the other error).
The repository is ok,

The problem is still present after those changes. Have you tested the output of the program when compiled with gcc or could you otherwise reproduce the error I've reported?

I've setup automatic builds for my own test program (using my Rust solver). This way, you can compare speeds on your own computer without compiling Rust.
Builds: https://github.com/Emerentius/sudoku-cli/releases

There are various commands (--help lists them), but the input format is always files with the typical 81 long sudokus on a line with an optional comment after it.
The following command checks and counts uniquely solvable, invalid and multi-solution sudokus

Code: Select all

rudoku solve --stat <FILES...>

[champagne]

Hi emerentius
I down loaded your sources sudoku_cli_0.5.0
and tried first to see if the las changes were there.

Total failure, I can't see in your code the correspondance with the original version.
Cand you help telling where is the source code corresponding to the zhou solver in your files

I'll go back to your problem through the results later, but without a readable version or the source, I feel in a bad position to comment.

[emerentius_]

What do you mean by "last changes"? This is based on my Rust adaptation of jczsolve which contains a couple of modifications. The two most important differences are the avoidance of a check that is badly predictable and a different guessing heuristic when no bivalue cell is found. I wrote about these changes in more detail a few pages prior to this. A couple % improvement stem from various micro-optimisations. Superficially, the code will look quite different and you're likely to have additional problems reading it because you presumably don't know the Rust language.

The solver's source code is here: https://github.com/Emerentius/sudoku/blob/master/src/solver.rs

You said you've made a few changes to improve performance. I'm curious how big the impact is on various kinds of sudokus but I can't test it because it miscompiles (and because you haven't given any numbers). If you compare some cases on your machine we can at least roughly guess how big the change is relative to jczsolve10 and to my version. If I understand correctly, the main changes you made affect the guessing heuristics. Do you still have the if-check that we talked about on page 20? That has shown to badly impact the branch predictor.

The command I gave searches for up to 2 solutions (without extracting the solutions). The files are read into RAM beforehand. Parsing + solving is part of the measured times.

[champagne]

Hi emerentius,
I had a look to your code. Even if the process is similar, you changed nearly all the coding, and I know nothing about your Rust language.
Difficult in such conditions to comment on your problem. I even don't know where the compilation fails.

I am using microsoft compiler. Mladen worked hard with me to have a full Linux compatibility, and I think that we now have it. He knows and uses both compilers, he could help.

Regarding performances, I tried to revise the "if" alone, with no significant effect. I gave up.
I changed with a significant improvement (a relative 20% from memory) the guess sequence. I tested various cases. I wrote how I think dangerous to conclude on a performance improvement ratio with limited benchmarks. Moreover, I don't want to spend that much time to compare all possible tools and infrastructures. I am interested in having something performing well in my own infrastruture.

All this to say that I share my experience, but have no willingness to have the "best product".

In your specific case, I have no idea so far on how I can understand where is your difficulty and help to solve it.

[emerentius_]

I had a look to your code. Even if the process is similar, you changed nearly all the coding, and I know nothing about your Rust language.
Difficult in such conditions to comment on your problem. I even don't know where the compilation fails.

I am using microsoft compiler. Mladen worked hard with me to have a full Linux compatibility, and I think that we now have it. He knows and uses both compilers, he could help.

The compilation failure has nothing to do with the Rust code. sk_bforce is broken when compiled on linux with optimizations. I compiled it with

Code: Select all

g++ main.cpp sk_bforce.cpp sk_bitfields.cpp sk_t.cpp -O2 -o sk_bforce

which succeeds without errors. But if I use it, all sudokus are counted as invalid.

[champagne]

The compilation failure has nothing to do with the Rust code. sk_bforce is broken when compiled on linux with optimizations. I compiled it with

Code: Select all

g++ main.cpp sk_bforce.cpp sk_bitfields.cpp sk_t.cpp -O2 -o sk_bforce

which succeeds without errors. But if I use it, all sudokus are counted as invalid.

I would be happy to see the source compiled here this could help

[emerentius_]

It's the code from your repo: https://github.com/GPenet/SK_BFORCE2/tree/5eadfedbd93dd2080715757016baf51fa3523d21

I haven't made any changes.

[champagne]

It's the code from your repo: https://github.com/GPenet/SK_BFORCE2/tree/5eadfedbd93dd2080715757016baf51fa3523d21

I haven't made any changes.

to be on the safe side, I would prefer to see your download. I don't know when you did it

[emerentius_]

It is that exact commit that I permalinked. I have the changes you made two weeks ago, but they didn't change the issue.

Code: Select all

$ git pull
Already up-to-date.