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 emerentius_ » Sun Jun 24, 2018 10:25 pm

dobrichev wrote:And that did not stop you from licensing the code without even mentioning the original author and other contributors?

I don't see what relation cryptic names, of which there was no shortage of, have to anything, really. I can add a contribution header to the file of course, but it's not like I've been passing off other people's work as my own. The library in that repo has roundabout 0 users, was never advertised anywhere (yet) and only mentioned here where it's clear to anyone that the solver was a collaborative work of several people.
emerentius_
 
Posts: 23
Joined: 09 January 2018

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

Postby Patrice » Thu Jan 03, 2019 1:31 pm

Hello guys,
Did you publish a new version of JCZsolve ?
I found V1.0 as attached file in JasonLion post
3-77us-solver-2-8g-cpu-testcase-17sodoku-t30470-219.html

but i did not noticed something new meanwhile a lot of discussions on improvements

Happy new year 2019 !
Patrice
 
Posts: 1934
Joined: 07 November 2010
Location: Paris France

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

Postby champagne » Thu Jan 03, 2019 6:21 pm

Patrice wrote:Hello guys,
Did you publish a new version of JCZsolve ?
I found V1.0 as attached file in JasonLion post
3-77us-solver-2-8g-cpu-testcase-17sodoku-t30470-219.html

but i did not noticed something new meanwhile a lot of discussions on improvements

Happy new year 2019 !


Hi Patrice,

Where we are, it's not easy to produce a better code. I failed in several attempts to do it.
I am testing for the 17 clues search with the 656 clues/stack distribution new ideas. This is for the time being in a 2 bands (6 rows) mode with a known solution grid, but the same strategy can be applied in a slightly different way in the general case.

I hope to test this on the beach side in the southern hemisphere end of January beginning of February. I'll come back here if the results are good.
champagne
2017 Supporter
 
Posts: 6792
Joined: 02 August 2007
Location: France Brittany

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

Postby emerentius_ » Fri Jan 04, 2019 1:08 am

Patrice wrote:Did you publish a new version of JCZsolve ?


All the improvements I talked about are implemented in the Rust version of the solver which is part of my sudoku library on github. Like I wrote on the last page of this thread, it's 10-20% faster than the version you've linked on any collection I've tested.

If you're looking for source code of the solver, that's in the linked repository. If you want a binary, I have the code for one here, but it requires a rust compiler of course.
emerentius_
 
Posts: 23
Joined: 09 January 2018

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

Postby champagne » Tue Jan 08, 2019 12:43 pm

Patrice wrote:Hello guys,
Did you publish a new version of JCZsolve ?
I found V1.0 as attached file in JasonLion post
3-77us-solver-2-8g-cpu-testcase-17sodoku-t30470-219.html

but i did not noticed something new meanwhile a lot of discussions on improvements

Happy new year 2019 !


Hi Patrice,
back to this post.

One key question is "why do you need a fast brute force solver".
We can immediately discard the check that a given puzzle posted here or there is valid. This will not be a critical step.

The classical cases are

is this puzzle "valid" (one and only one solution)
is this puzzle minimal.

In the second case most of the sub puzzles will not have a unique solution
In the first cases, a huge majority of puzzles will have many solutions, most of the rest will have no solution.

In fact, a valid puzzle is a rarity for guys working in this field. BTW, a valid puzzle is a kind of worst case for a brute force (may be just followed by a puzzle with no solution )

Most of the "primary benchmarks" are done on valid puzzles files. This can tell you if the order of magnitude of the average run time is correct, but is in general totally misleading to define the best tool for a given task.

It happens that in my 17 clues search improvements I was at the point where the general brute force plays a role. So, I am working on the topic.

I forgot another key point. Most of the puzzles, if valid, are in the range "very easy" to "SE rating <8.0".
A brute force performing well must be highly efficient for such puzzles.

zhouyundong_2012's code performs very well in this area, so don't expect an improvement deviating much out of this code unless a new very efficient idea comes out.

And the benchmark to use is very difficult to assess, the users will have to rely on an acceptable code and make their own judgement depending on the problem to solve.

.
champagne
2017 Supporter
 
Posts: 6792
Joined: 02 August 2007
Location: France Brittany

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

Postby champagne » Wed Jan 30, 2019 11:14 am

I promised to produce a new variant of the brute force if I had something of interest.
I already stated that benchmarking of the brute force with small improvements is difficult, however, my feeling is that this version is significantly faster than the previous one.

The original code is located within my new skmpp2 frame, I prepared a stand alone version with (at least in the brute force files) only the necessary code to run a basic brute force;

In this variant, the best improvement is IMO the selection of the bi-value cell to apply.
I introduced also a quite new way to guess, all “one digit” potential solutions.

I suspect that we have still here some room for improvement, but I have to focus on the 17 clues search for the next weeks.

The code is stored in a specific repository here

And I prepared comments on this variant available here

Normally, this code can work with LINUX, but I only verified than gcc can compile it.
champagne
2017 Supporter
 
Posts: 6792
Joined: 02 August 2007
Location: France Brittany

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

Postby Mathimagics » Wed Jan 30, 2019 1:14 pm

Hi champagne.

Your link to "comments on this variant" appears to be broken.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1088
Joined: 27 May 2015

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

Postby champagne » Wed Jan 30, 2019 4:59 pm

Mathimagics wrote:Hi champagne.

Your link to "comments on this variant" appears to be broken.


I reach it clicking on the url. Don't know what is wrong on your side.
champagne
2017 Supporter
 
Posts: 6792
Joined: 02 August 2007
Location: France Brittany

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

Postby Mathimagics » Wed Jan 30, 2019 7:15 pm

MS Edge still reports "Unable to reach this or 23 other pages". But all my other tabs are functioning ok.

Can somebody else try and reach that link please?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1088
Joined: 27 May 2015

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

Postby m_b_metcalf » Wed Jan 30, 2019 7:33 pm

Mathimagics wrote:MS Edge still reports "Unable to reach this or 23 other pages". But all my other tabs are functioning ok.

Can somebody else try and reach that link please?

Gladly - works perfectly, with Edge!
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9625
Joined: 15 May 2006
Location: Berlin

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

Postby tarek » Wed Jan 30, 2019 8:38 pm

m_b_metcalf wrote:
Mathimagics wrote:MS Edge still reports "Unable to reach this or 23 other pages". But all my other tabs are functioning ok.

Can somebody else try and reach that link please?

Gladly - works perfectly, with Edge!

All good here too
User avatar
tarek
 
Posts: 2895
Joined: 05 January 2006

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

Postby Mathimagics » Wed Jan 30, 2019 9:09 pm

.
Maybe it's not me, but my ISP. Could that website somehow have wound up on a block list? Here in OZ the neo-con lot running the place require ISP's to get on board the "let's stop people getting onto Pirate Bay" bus …. then they tell us "small government is good government". Good grief ...

I can't test this theory immediately, my VPN is only installed on the old PC, but I will soon rectify that hopefully ....

I can think of no other explanation right now

[EDIT] Aha, I was right! 8-)

What is it with these people … :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1088
Joined: 27 May 2015

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

Postby champagne » Thu Jan 31, 2019 3:33 am

Mathimagics wrote:.
Maybe it's not me, but my ISP. Could that website somehow have wound up on a block list? Here in OZ the neo-con lot running the place require ISP's to get on board the "let's stop people getting onto Pirate Bay" bus …. then they tell us "small government is good government". Good grief ...

I can't test this theory immediately, my VPN is only installed on the old PC, but I will soon rectify that hopefully ....

I can think of no other explanation right now

[EDIT] Aha, I was right! 8-)

What is it with these people … :?


I don't see clearly if you can read it or not now.
This is a set of documentation produced using an old version (2003) of microsoft publisher, an easy way for me to work.
If you can't read it, we should face the same problem with next documents that I am preparing for the thread recently open.
(skmpp2 repository)

In this case, what would you suggest?


And sorry for readers, I am aware of the weakness of my english. I do my best, and I can easily adjust the wording if I am warned of unclear or missing points.
champagne
2017 Supporter
 
Posts: 6792
Joined: 02 August 2007
Location: France Brittany

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

Postby Mathimagics » Thu Jan 31, 2019 4:37 am

.
I am sorry, champagne, there is nothing wrong with your link, or your document.

It's me who failed to make my meaning clear. From this part of the world, Australia, that website (gpenet.pagesperso-orange.fr) appears to blocked!

When I click on the link, there is a long, long delay, then I finally get the "Unable to reach that page" window. It is not just my PC, my daughter tried it too and failed to connect.

But if I go through my VPN service, it's fine, I can connect. This can only be explained by a blocking of that site - for some inconceivable reason, it is on our official "forbidden website list". Yes, we do have such a thing.

You may have trouble understanding how this can happen in a modern democracy (and so do I). It sounds more like North Korea, right? :?

There is legislation in place here that requires ISP service providers to do site blocking of government-nominated websites. The aim of this legislation was to protect poor little media corporations from the evils of torrent services, where people (apparently) download movies and stuff from sites like Pirate Bay, etc.

Why is that website on the block list? God knows! Some idiot from a media corporation went crazy with the block lists? Maybe because he hates anything French?? Maybe there's a torrent service with a similar name? :cry:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1088
Joined: 27 May 2015

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

Postby champagne » Thu Jan 31, 2019 5:06 am

Mathimagics wrote:.
that website (gpenet.pagesperso-orange.fr) appears to blocked!
You may have trouble understanding how this can happen in a modern democracy (and so do I). It sounds more like North Korea, right? :?

Sorry Mathimagics.

orange is the main web supplier in France. (former state phone company)
pagesperso-orange.fr is used by many clients as host for private small websites.

It can be that the entire site pagesperso-orange.fr is black listed in Australia. I have doubts that my private adress could be locked. I have nothing out of the sudoku field in these pages. I faced the problem years ago in US for mails. One of the US mail hosting company black listed orange due to the number of spams coming through this channel.

Unhappily, I can't do anything
champagne
2017 Supporter
 
Posts: 6792
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Software

cron