The New Sudoku Players' Forum

[dobrichev]

Happy New Year!

mladen, did you have any success with one of the points you had in mind

No success.
More UA at startup would truncate the search space, the point where "consolidation" is made should be reconsidered, larger cliques should be processed.
Although the average time for 16s for McGure's code is ~3 seconds, the search for 16s in some non-random grids took 4 to 8 minutes. That with the original, unmodified code.

I still have no idea what can be done if the search for 17s is optimized even to 1 second per grid.

[champagne]

I still have no idea what can be done if the search for 17s is optimized even to 1 second per grid.

The proof of non existence of a 16 clue has been done with an average speed of 3 seconds per solution, but I agree that proving that the known file of 17 clues is (or not) complete is not so exciting.

I investigated with a poor success the possibility to use a reduced number of UA's.
I tested the full generation "as of" mac guire list of UAs for existing 17 and got the following results (on a small PC about 2.5 Ghz)

- an average speed of 20 to 30 puzzles per second (including one brute force call to find the solution but this is not a key point)
- a number of UA's per puzzle widely spread in the range 190-400 with a pick around 320 UAs.

This is not very positive to find quick filters.

I am locked for 2 weeks, but i intend to restart that topic later

[blue]

I doubt the 17s exhaustive search would take only 10x resources compared to 16s without further algorithm improvements. I have some points in mind.

This is true. The code to generate the puzzles, takes ~8 times as long for 17's, but the number of puzzles that it produces, goes up by a factor ~150, and the fraction of time spent in the solver, becomes significant (but not unreasonable). I tried something along the lines of what I suggested at the bottom of this post, but without "feedback", and was able to get the time per grid down to ~22 seconds -vs- 2.8 for 16's.

(...)

Blue, I tried to go to your link, "this post", but the page is not any more available. If you still have the text, it would be great to have it posted again somewhere in that forum.

Sorry, but I don't have the text.

It mentioned the fact that when a (17 clue) puzzle goes to the solver, it's almost certain that the puzzle will have two or more solutions.
Since that would mean that the test grid has an unavoidable set that isn't hit by any of the clues, it suggested that it might be a good idea to identify such a set, and somehow feed it back into the algorithm that's generating the puzzles.

When I wrote it, I hadn't taken a detailed look at the (checker16) code.
The idea of forcing another "known" UA set into the list that front end code was dealing with, was not practical (for many reasons).

[champagne]

It mentioned the fact that when a (17 clue) puzzle goes to the solver, it's almost certain that the puzzle will have two or more solutions.
Since that would mean that the test grid has an unavoidable set that isn't hit by any of the clues, it suggested that it might be a good idea to identify such a set, and somehow feed it back into the algorithm that's generating the puzzles.

When I wrote it, I hadn't taken a detailed look at the (checker16) code.
The idea of forcing another "known" UA set into the list that front end code was dealing with, was not practical (for many reasons).

Hi bkue,

I think that I see your point.

I am working in another direction, but with many question marks.

I started as I already wrote with a limited group of UA's, but with so many problems that I am back to the full set generated in the mac guire process.

To see what this means, I made a preliminary test these days on my travel PC (about 2.5 Ghz) trying in priority to see what was the count of UA's in the solution grids having a known 17 and in other grids?

I got the following count
column 1 slices of 10 UA's found (390 or more for the last row)
column 2 count for the known 17 (each 17 is first extended to the solution grid, so some solutions are redundant)
column 3 count for a lot of 1957314 (one chunk of my catalog data base with High minlex values)

Hidden Text: Show

Code: Select all


100      1
160      1
170 1 
180      1
190 10   3
200 19   9
210 49   28
220 94   61
230 247  115
240 448  274
250 735  534
260 1324 1150
270 1949 2272
280 2694 4387
290 3579 8336
300 4263 15169
310 4836 26545
320 5118 44941
330 5063 71174
340 4633 106110
350 3959 147176
360 3203 188254
370 2470 221588
380 1702 237240
390 2761 881945

Distributions are very different, but my only first reaction is that a quick filter could ignore all solutions with less than 300 UA's -may be more).

One negative point is that on my small PC, the search of UA's was done at about 30 solution grids per second.
I have to see
. first if my code is valid
. if this code can be improved.

Regarding the existence or not of 17 in the grid, I am working on what seems a new idea, partially derived from our experience in the 4+4+27 field.

Intead of starting with one clue per UA, I try one box per UA (with small UA's, this is generally 2 clues in a mini line.) I dont use the max clique, I process UA's startting with the lowest number of cells.

This changes significantly the number of permutations but raises new problems.
The process has some chances to be efficient if most of the permutations are killed due to the count passing 17 to reach a hint on each UA, what did not come with a reduced set of UA's
Reaching 17 with a grid having several solutions is still easy to handle, but must be a limited count. (due to the cost of the brute force)
The new problem is if the grid at the end has only one solution. Then finding how many clues are needed is requiring several brute force calls.

Still a lot of work on my side to tell if it is a good idea or not.