3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Programs which generate, solve, and analyze Sudoku puzzles

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sat Jan 07, 2017 2:24 pm

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
 
Posts: 139
Joined: 10 February 2012

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Fri May 05, 2017 9:47 am

JasonLion wrote: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.
zhouyundong_2012
 
Posts: 139
Joined: 10 February 2012

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby emerentius_ » Tue Jan 09, 2018 2:50 am

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.
emerentius_
 
Posts: 1
Joined: 09 January 2018

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby JasonLion » Wed Jan 10, 2018 3:21 pm

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.
User avatar
JasonLion
2017 Supporter
 
Posts: 628
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Thu Jan 11, 2018 10:05 am

You can use it anywhere, no license.
zhouyundong_2012
 
Posts: 139
Joined: 10 February 2012

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby dobrichev » Thu Jan 11, 2018 10:35 am

zhouyundong_2012 wrote:You can use it anywhere, no license.

This is how the real men work. Congratulations!
dobrichev
2016 Supporter
 
Posts: 1363
Joined: 24 May 2010

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby champagne » Fri Jan 12, 2018 4:15 am

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
2017 Supporter
 
Posts: 5753
Joined: 02 August 2007
Location: France Brittany

Benchmarking of the brute force issues

Postby champagne » Tue Jan 16, 2018 10:06 am

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.
champagne
2017 Supporter
 
Posts: 5753
Joined: 02 August 2007
Location: France Brittany

Previous

Return to Software