The New Sudoku Players' Forum

by **dobrichev** » Mon Jun 20, 2016 10:47 am

A task for neighborhood search for new 17-given puzzles at {-3/+3} from the known 49157 ones finished with no new puzzles found.

by **champagne** » Tue Jun 21, 2016 10:59 am

I have an ongoing scan of the 27+6+3 field with the same goal, but with little hope that a new 17 will come. The end of the task is not expected before 3 months.

I am also working on a new process to scan the catalog an to try to establish if we have the full list of 17.

I am currently finishing a morph of the catalog in an appropriate form for what I intend to code.
After that I'll be ready to open a thread explaining in details what is planned and showing some statistics giving some credibility to the idea, but the final code will not be ready before several weeks and the feasibility of the project will only be seen at that moment.

by **champagne** » Tue Jun 21, 2016 2:23 pm

Mladen, one question

How long did it take to run that vicinity search

by **dobrichev** » Tue Jun 21, 2016 2:52 pm

The search took about 49 CPU years. It has been started at the beginning of 2015 and with some gaps several machines did the job.
The source code is here - https://github.com/dobrichev/sudoku14plus3

by **champagne** » Tue Jun 21, 2016 2:58 pm

Just to compare, It seems to me that the proof that no 16 exists took about 3 second per solution grid, which is

5472730538*3 /3600 /24 /365= 521 core.years.

by **coloin** » Thu Jun 23, 2016 2:50 pm

Well done ... no mean feat.

Currently I am background generating box9plus13s ...... in a while i will apply the gridchecker removeredunant command ....
If any new 4plus13s appear i will let you know !!

3 more box9-plus 12s found [152 total]
currently 4 million ED box9-plus13s .....

Mladen - coding a gridchecker {-1+1} on these but leave the central box would be a useful function for me to let rip with ...

C

by **champagne** » Sun Jul 03, 2016 11:50 pm

champagne wrote:Just to compare, It seems to me that the proof that no 16 exists took about 3 second per solution grid, which is

5472730538*3 /3600 /24 /365= 521 core.years.

I refreshed that value.

In Gary McGuire's article, it is written

computation actually took only about 800 processor-years

What is missing is the processor speed.
So the average run time per grid seems to be between 4 and 5 seconds using a processor likely in the range 3-4 Ghz.

Blue tried to extend the Gary McGuire process to the search of 17 clue puzzles. In a pm, he announced an average 20 seconds per solution grid, which seems very low compared to the above data for the proof that no 16 exists.

by **coloin** » Sat Oct 21, 2017 8:52 am

Having done a full {-3+3} ... maybe a partial {-4+4} or greater is possible.
Perhaps with recent work we should only consider looking for puzzles which have maximum 6 clues in a band ... {665,665}

This maybe could be done quickly ? by considering the clues in 1 band [ of six] only.
A very quick option would be to iterate all the clues in a [horizontal] band within the 3 clue [vertical] mini-row .... [this works surprisingly well with larger puzzles !]

But also a option would be to do a full {-n+n] within the gangster band
The clues in the band have 3 options - this keeps the untouched double gangster 54-clue bands solvable with the 12 or 11 clues there.
Adding clues to the band - the first clue has to be in one of the rows [9 loci]
The second clue has to be in a different row [ 9 loci again]

or perhaps even simpler by combining the { known } 5 or 6 clues which solve the gangster band

Of course one will only find a new puzzle - if there actually is one !

by **champagne** » Sat Oct 21, 2017 9:14 am

dobrichev wrote:The search took about 49 CPU years. It has been started at the beginning of 2015 and with some gaps several machines did the job.

Hi coloin,

just to keep in mind order of magnitude

Assuming a one second per solution grid in something derived of the blue's process, the entire scan would be about 174 CPU years.
On the other side, the gap from +- 3 to +- 4 is huge.

And an average one second per solution grid seems to-day achievable. The last improvement that I described in another thread seems to work very well in "bad cases", the last threat for a good average run time. I'll know more in 2 or 3 days.

by **coloin** » Sat Oct 21, 2017 9:33 am

Well ... its a partial search within the band.
And its a long shot ....
but as in your thread , keeping the gangster / [ and therefore the 54 clue double band is potentially solvable] means that for each puzzle we are actually only searching an additional 60 grids per 665,665 puzzle
[~10 ED bands per gangster and 6 bands to consider]

The New Sudoku Players' Forum

No new 17s within {-3+3}

No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}

Re: No new 17s within {-3+3}