The New Sudoku Players' Forum

[zhouyundong_2012]

It is difficult to remember so many interface, how to change this condition? I found a problem that is the interface name is not very readable.

[zhouyundong_2012]

zhouyundong_2012,

Using two lookups into a larger shrink table uses fewer instructions, but results in more cache misses. Cache misses are expensive, and almost exactly cancel out the advantages of fewer instructions. Given they are about the same speed, using the smaller table saves memory and leaves more of the cache available to whatever other code is running that is calling the solver.

Has anybody had done test of this? Cut 2 sects or cut 3 sects.

[emerentius_]

I congratulate you on your achievement with JCZsolve. It's an amazing piece of work.

I have a request. Could you, jason, champagne and zhouyundong, make the insights found in the making of JCZsolve available to others?
There is currently no license given for the code other than the informal one by zhouyundong when he first posted his code. Because there is no license given by all authors, it is in my understanding illegal to use the code for anything including personal use, non-commercial use or research. That actually includes you, the authors, too, except for maybe zhouyundong because of his informal license.

I would love to incorporate the JCZsolver algorithm into my own sudoku library and make my code available under a free software license, the AGPLv3, but I can't because of copyright. Now technically there is no copyright on algorithms but you can only find out the details of the algorithm by reading the implementation on which there is copyright. That puts any re-implementation of the algorithm on questionable legal ground as one may reproduce implementation details that don't directly follow from the algorithm.
The AGPLv3 gives everyone the right to use, modify and redistribute the software however they see fit under the restriction that any software derived from it has to be free software itself and preserve those rights and restrictions, meaning in practice that it also has to be licensed under AGPLv3. If you're worried about commercial exploitation of your work, the AGPLv3 does allow you to sell software but this has proven to be a difficult business model because anyone who buys it may then turn around and distribute it freely to anyone who will then be allowed to distribute it, too.

It would be great if you could put your work under a free software license so that people can use your work. It would be ideal for my purposes if that license is compatible with the AGPLv3. If you don't want to do that, then I would ask for explicit permission to build my own program from yours. Your rights over your program would of course not be inhibited in any way. If you don't wish to to do that either I would have to do a clean-room implementation. That is, I would need to find someone who could write a specification of the algorithm from your code and then write my program from that specification. This way I could re-implement the algorithm without violating your copyright. It would be a lot of unnecessary work.
I'm programming in Rust and I will have to structure my code quite a lot differently than your C program to make it idiomatic Rust code. I can't just copy-paste it in place.

I know copyright and licensing are not subjects anyone likes to spend their time with, but I ask that you take the time to think about it so others may benefit from your work. If you give me permission to write my implementation from your source code and put it under the AGPLv3 I could also write down a specification of how the solver works myself. That may be useful for others who want to implement or improve upon it.

[JasonLion]

I agree to offer my contributions to JCZsolve under the AGPLv3 license.

"the insights found in the making of JCZsolve" is a complex subject, a fair bit of which is covered elsewhere in this topic.

[zhouyundong_2012]

You can use it anywhere, no license.

[dobrichev]

You can use it anywhere, no license.

This is how the real men work. Congratulations!

[champagne]

My own contribution can be freely used as well.
I have been advised to add some general licensing terms to prevent anybody to lock the code, what I did long ago in some releases of code, but generally speaking, this is "open source" code. The frame is derived from zhouyundong_2012 solver and part of the changes are derived from mladen Dobrichev's work.

BTW After some intensive work on the 17 clues search, I am trying to do small changes in the frame derived from this experience to speed up the process, if something works, I could come back in February with fresh ideas.

[champagne]

Trying to re use some findings made in the 17 search in the brute force, I faced huge bench marking difficulties.

To make it simple, the current brute force is highly sensitive to the morph processed. The main reason is quite simple to catch. The first guess is usually a bi-value cell, and if no bi-value cell is available, a digit bi-value.

The effect of the first(s) guess can vary in such a way that the final call to the inner loop Update() can be in a ration 1:2 1:3.

This is still true along the full path, but the first guess have the biggest effect.

I suspect that this is true for other brute force programs used in the benchmarks.

I am trying to digest the tests made on several puzzles, with as first consequence that I have to revise what I considered as "promising choices".

If what I have in mind is right, the use of benchmarks must be done very carefully.

If I got properly the hidden reason of some results, the minimal lexical canonical form is likely a relatively good morph for the JCZSolve code. Reversely, my canonical form is not.

It can be reverse using another brute force program.

A sample file having only one of these morph is highly biased and the situation would be worse using in a benchmark a small number of puzzles with a big repetition factor.

The rules to optimize the first guesses are unclear, but generally speaking, in JCZSolve, it seems better to start with a brute force killing more candidates, and, in the case of a digit bi-value (no cell bi-value available) , with a bi-value producing cells-bivalues.

[emerentius_]

Thanks everyone for allowing me to use your code. I've finished a working port to Rust which is at this point still almost completely 1-to-1 translated. Lots of garbage still lying around that I'm going to clean up before I merge this into master. For now it's available under this temporary branch. Solver performance seems to be close to 100% of the C implementation. I've avoided globals so that the library is thread safe.

The solution extraction function had some strange behaviour on performance in my tests where I could improve speed by up to ~50% on some easy sudokus but had almost no change on others.
I've changed the extraction routine to the one below which extracts the correct digits directly instead of testing on average 5 for each cell. It uses 1 small lookup table instead of 2 larger ones which I suspect were causing cache eviction in some cases.

Code: Select all

static void
ExtractSolution(char *solution)                   // Extract solution as a character string
{
   for (int band = 0; band < 27; ++band) {
      int mask = g->bands[band];
      int digit = band / 3;
      int baseCell = (band % 3) * 27;
      while (mask) {
         int lowestBit = mask & -mask;
         int cellOffset = BitPos(lowestBit);
         solution[baseCell + cellOffset] = '1' + digit;
         mask ^= lowestBit;
      }
   }
   solution[81]=0;
   }

[champagne]

The solution extraction function had some strange behaviour on performance in my tests where I could improve speed by up to ~50% on some easy sudokus but had almost no change on others.

I am slightly estonished to see the solution extraction as a problem.

In most cases, the user does not care about the results, only by the count of solutions (cancelling the task if the count is >1).
In some cases (UA collector on my side for example) the solution is needed, but in a specific context and a tailor made extraction can be done.

Can you tell more about the fact that you need the solution.

btw, to avoid cache problems due to lookup tables, the intrinsic bit functions can be used bit scan......

[JasonLion]

btw, to avoid cache problems due to lookup tables, the intrinsic bit functions can be used bit scan......

The intrinsic's can be just awful if you aren't careful to set all the compiler flags just so.

And even when you get the compiler to use the correct instructions I can still sometimes beat their time with my our code if the instruction scheduling works out just right,

The lookup table can be very fast as long as you don't overfill the cache.

[champagne]

btw, to avoid cache problems due to lookup tables, the intrinsic bit functions can be used bit scan......

The intrinsic's can be just awful if you aren't careful to set all the compiler flags just so.

And even when you get the compiler to use the correct instructions I can still sometimes beat their time with my our code if the instruction scheduling works out just right,

The lookup table can be very fast as long as you don't overfill the cache.

Hi Jasonlion,

As I wrote earlier, where we are, improving the code is not easy and depending very much on the file of puzzles tested (and likely processor used).

Regarding intrinsics, all cheks I did on the generated code show that using microsoft visual studio with the "intrinsic" option the expected instruction comes. But it can be that a look up table works better than a bit scan. One problem with the cache issue is that tests done on a stand alone brute force can lead to false conclusions if the brute force, as usual, is part of a bigger program.

[zhouyundong_2012]

Do you want to research bit coin solver?If you want, do you want join? I have an idea and have written one.

[zhouyundong_2012]

No body interest in bitcoin solver?
I want to find a people to work together, who must keep the code and algrithom as a secret.

[zhouyundong_2012]

I made a large progress on the senond step of the solver of bit coin SHA256 today.
and I have made a serial speedup on the first step.
To solve SHA256, only 2 steps in my solver.
So I can say: Almostly, I crack the simple one question of SHA256.