The New Sudoku Players' Forum

by **dobrichev** » Thu Mar 27, 2014 8:51 pm

blue wrote:I get a much smaller pattern count, after VPTs ... ~38e9.

Yes, the right number is 128447994798305000 / 3359232 = 38 237 309 837

by **blue** » Fri Mar 28, 2014 1:25 am

Hi Mlad,

dobrichev wrote:The search possibly could be improved by
Checking whether "dead clues" entirely cover a known UA set
Checking for redundant clues at earlier stages
Partial reusing of the intermediate search results for "neghbour" grids - those that differ in permutation of digits within a single UA

Interesting ideas !

The first one is already part of Gary's code, to some extent. In the inner loops it's done fully. When the code chooses an unhit UA to use for placing the next clue, it finds one that has the smallest number of "live" cells, and the number is zero if it's a UA covered by "dead clues". When that's the case, nothing really happens in the next level of looping. In the outer loops, not every unhit UA is checked, but there are other layers "kicking in" at that point, that might make up the difference -- the code related to collections of 2-5 disjoint UA sets, none of which have been hit yet.

dobrichev wrote:I played with dynamic addition of UA after unsuccessful check for a single solution and found it unproductive. Large UA sets don't add value.

I tried a few things, and what I have now, I think is optimized for 18's. It makes the time for 16's go up to ~3 sec -vs-2.8 per grid, when it was set up for 17's.
I've been running it ~8 hours now -- 16's and 17's on two cores -- testing random grids. The statistics (for 17's) are settling down, and it looks like it's reducing the number of "direct" solver calls by a factor of ~320, at a cost of producing one minimal UA, each time a 2-solution puzzle passes the preliminary tests and goes to the solver.
[ It's been a while, but I remember being proud of how fast I could get the code that produces the minimal UA ].

What I have (depending on preprocessor settings), is this:

a layer between the code that produces puzzles for testing, and the solver.
- It maintains one or two queues of minimal UA sets
- The UA sets are produced when a final call to the solver, returns a 2nd solution
- For the most part, the queues fill up with a mix of size 12 and 13 UA's, and an occasional 14 or larger.
the queue lengths can be 128 or 256. With two queues, they're both the same size.
For 18's I had the 2x256 option.
one queue is a FIFO queue, and it's checked first, when new puzzles come in for testing.
the other queue (when there are two, ) is a prioroty queue, that collects everything booted out of the FIFO queue. When it needs to make room for a new one, it removes the "oldest of the largest sized UA's" first.
the code for each queue, works similar to Gary's code.
- it uses MMX instructions, revolving around masks of "unhit UA's"
- for each clue position, it has a mask of which of the known UA's are ~~hit~~ missed by clue.
- to check whether testing can be skipped for a puzzle, it starts with a "full mask" -- one bit set, for each known UA -- and loops over clue positions, clearing bits "en masse", for the UA's the hit by each clue. [ At the end, if the mask is non-zero, there's a (known) unhit UA, and the puzzle can be skipped ].
  It all happens very quickly -- 17 operations per puzzle usually.
- when a solver call returns a 2nd solution and a minimal UA are produced, one puzzle is bumped from the FIFO queue, if it's full, and the "hit masks" are updated accordingly. A similar thing happens in the 2nd queue, whenever something is bumped from the first queue.

Have fun with what ever you might try !

Best Regards,
Blue.

by **Serg** » Fri Mar 28, 2014 3:18 pm

Hi, Mladen!

dobrichev wrote:Yes, the right number is 128447994798305000 / 3359232 = 38 237 309 837

Maybe I missed something ...
There are 55,113,078,988 essentially different 17-clue patterns (see thread Number of non equivalent patterns having N clues).

There are 77 millions e-d 17-clue patterns, having 1 clue in one box and 2 clues per each remaining box (see the thread cited above). Though number of e-d 17-clue patterns, having 1 clue in one row and 2 clues per each remaining row, is probably different, but surely comparable witn 77 millions.
champagne, are you ready to search through 77 millions of patterns? (Distribution 122222222 is not the only possible distribution for 17-clue patterns.)

Serg

by **dobrichev** » Fri Mar 28, 2014 4:05 pm

Yes, you missed your post next to the referred one

Serg wrote:...I calculated (manually) low bound for number of e-d 17-clue patterns. I got low bound 3.8e10 (if I was not wrong in calculations). It does not contradict with your exact number of 17-clue patterns - 5.5e10 (appox.)...

More precise results are welcome of course. Thank you for the link.

So, the upper limit for the number of patterns is roughly ten times the number of the grids. I don't believe the reduction factor of "impossible" patterns is 10 or more, but finding it is an interesting challenge by itself.

by **champagne** » Fri Mar 28, 2014 6:19 pm

Serg wrote:There are 77 millions e-d 17-clue patterns, having 1 clue in one box and 2 clues per each remaining box (see the thread cited above). Though number of e-d 17-clue patterns, having 1 clue in one row and 2 clues per each remaining row, is probably different, but surely comparable with 77 millions.
champagne, are you ready to search through 77 millions of patterns? (Distribution 122222222 is not the only possible distribution for 17-clue patterns.)

Serg

Hi Serg,

First of all, I trust all the figures I red these days so I accept that this is not the right way for the general problem.

Regarding the 1222222.. distribution, a tiny corner of the field, I intended in fact to look at the patterns with not more than one given in a mini row/column .
As I wrote, I found only 2 such patterns in the existing file of 17 clues puzzles. This is a small subset of your 77 millions puzzles.

I'll try at least to count the number of patterns with 18 clues with the same property. This is not too hard and will give and idea of the size of the problem.

by **coloin** » Sat Mar 29, 2014 1:23 am

well .... interesting discussions

moving it in a different direction perhaps ....

i too have been thinking of the clues in box distributions

Code: Select all: 222222221 3.......0 3......00 3.......1 4.......0 4......00 4.......1 5.......0 5.......1 6........

Searching specifically for each distribution

One would need to explore the feasibility of each before starting any !

Patterns could be eliminated [obviously if confirmed]
ones with less than 3 clues in a band
ones with less than 6 clues in a crossing-band - very few 17-puzzle have less than 7 clues in a crossing-band

My initial thoughts - I have to say if we were to get very good at proving the see here
6....... and 5........ [six known puzzles] we might be able to advance

However - the 222222221 case needs extra thought on how to accomplish

There are only 64 ED ways to have 2 clues in each of B1B5B9 - if that helps anything !

Hidden Text: Show

Code: Select all: 1.........2...................1.........2...................1.........2.......... 1.........2...................1.........2...................1.........3.......... 1.........2...................1.........2...................1........2........... 1.........2...................1.........2...................1........3........... 1.........2...................1.........2...................3.........4.......... 1.........2...................1.........2...................3........4........... 1.........2...................1.........3...................1.........4.......... 1.........2...................1.........3...................1........2........... 1.........2...................1.........3...................1........4........... 1.........2...................1.........3...................2.........3.......... 1.........2...................1.........3...................2.........4.......... 1.........2...................1.........3...................2........3........... 1.........2...................1.........3...................2........4........... 1.........2...................1.........3...................4.........5.......... 1.........2...................1.........3...................4........5........... 1.........2...................1........2....................1........2........... 1.........2...................1........2....................1........3........... 1.........2...................1........2....................12................... 1.........2...................1........2....................13................... 1.........2...................1........2....................3.........4.......... 1.........2...................1........2....................3........4........... 1.........2...................1........2....................34................... 1.........2...................1........3....................1........3........... 1.........2...................1........3....................1........4........... 1.........2...................1........3....................13................... 1.........2...................1........3....................14................... 1.........2...................1........3....................2........3........... 1.........2...................1........3....................2........4........... 1.........2...................1........3....................23................... 1.........2...................1........3....................24................... 1.........2...................1........3....................3.........4.......... 1.........2...................1........3....................3........4........... 1.........2...................1........3....................34................... 1.........2...................1........3....................4.........5.......... 1.........2...................1........3....................4........5........... 1.........2...................1........3....................45................... 1.........2...................3.........4...................5.........6.......... 1.........2...................3.........4...................5........6........... 1.........2...................3........4....................3........4........... 1.........2...................3........4....................3........5........... 1.........2...................3........4....................34................... 1.........2...................3........4....................35................... 1.........2...................3........4....................5........6........... 1.........2...................3........4....................56................... 12............................1........2....................1........2........... 12............................1........2....................1........3........... 12............................1........2....................3........4........... 12............................1........3....................1........3........... 12............................1........3....................1........4........... 12............................1........3....................2........3........... 12............................1........3....................2........4........... 12............................1........3....................24................... 12............................1........3....................4........5........... 12............................12............................12................... 12............................12............................13................... 12............................12............................3........4........... 12............................12............................34................... 12............................13............................14................... 12............................13............................23................... 12............................13............................24................... 12............................13............................4........5........... 12............................13............................45................... 12............................3........4....................5........6........... 12............................34............................56...................

with only 8 ED patterns

Hidden Text: Show

but this doesnt change the fact that there are 77 million patterns .....
C

by **champagne** » Sat Mar 29, 2014 2:11 pm

Serg wrote:There are 77 millions e-d 17-clue patterns, having 1 clue in one box and 2 clues per each remaining box (see the thread cited above). Though number of e-d 17-clue patterns, having 1 clue in one row and 2 clues per each remaining row, is probably different, but surely comparable with 77 millions.
champagne, are you ready to search through 77 millions of patterns? (Distribution 122222222 is not the only possible distribution for 17-clue patterns.)

Serg

Hi Serg,

I made a first test with some fresh code, so subject to more checking.

To be clear, as I am looking for patterns where the max lex canonical form is 1.. 1.. ... for the first row, this must be a 2222222221 distribution of clues with no mini row having more than 1 clue.

In that situation, if we push to 18 clues with the same property, we have a strong effect of what I could call "symmetries".
each row and each column must have exactly 2 given in 2 different mini rows/mini columns

I don't know what if the theoretical count for that group of patterns without the "symmetries" effect, but at the end, I have in hands 72 patterns.

If this is correct, scanning 72 patterns for 18 clues is clearly feasible.
If the puzzle is not minimal, we have a 17 clues solution

here is the list of ED patterns I got in my first test

Hidden Text: Show

by **coloin** » Sat Mar 29, 2014 10:28 pm

There appear to be eight known puzzles with row,column and box counts of 222222221
There appear to be sixteen puzzles known with just row and column counts of 222222221

Only 2 puzzles in these lists satisfy the minirow constraint

Hidden Text: Show

C

by **champagne** » Sun Mar 30, 2014 8:42 am

coloin wrote:There appear to be eight known puzzles with row,column and box counts of 222222221
There appear to be sixteen puzzles known with just row and column counts of 222222221

Only 2 puzzles in these lists satisfy the minirow constraint
C

I have a slightly different look at the file.

My primary split is on the row1 where the pattern is in canonical max text form.

Starting from the file with 49152 puzzles, I got 33878 different patterns.

The split on row 1 (for the entire file) is the following

Code: Select all: 1111..1.. 1 1111..... 387 111...... 1847 11.11.1.. 26 11.11.... 1235 11.1..1.. 6537 11.1..... 39031 11....... 86 1..1..... 2

The last item corresponds to your 2 puzzles coming from 2 different patterns.
(BTW, I have 72 patterns with 18 clues, if I try to expand it to 17 clues patterns (loosing the symmetry), I find 663 different patterns.
a full scan on 72 "18 clues" patterns should not be so different of the full scan on 663 "17 clues" patterns).

The item starting with 11.... accepts rows with 3 clues in three different mini rows, so it does not fit with your approach.

Here we can see that no puzzle has been seen so far with the start 1.. 1.. 1..

And a majority of the file has the start 11. 1.. ...
but here we likely have a huge number of possible patterns.

by **coloin** » Sun Mar 30, 2014 11:32 am

I see that you actually had found the two puzzles .....
Interestingly i have always found the max lex pattern perhaps a more economical way to present puzzles - more clues are fixed in row one - usually more than 2 !.

When a pattern search of your possible patterns with max lex 1..1..... has been done - at least we can say that we have searched a complete area !

I also didnt include blues 5 new puzzles - but i see they dont affect the results.

C

by **Serg** » Sun Mar 30, 2014 5:05 pm

Hi, champagne!
If my understanding is correct, you are planning to do exhaustive search for class of pattern having following properties (constraints):

1. Each pattern contains 17 clues.
2. One row of the pattern contains 1 clues, remaining rows contain 2 clues each.
3. Each minirow of the pattern contains not more than 1 clue.
4. You consider essentially different patterns only.

Let's call this class of patterns as "Little subset of 17-clue patterns set".

Let's calculate number of patterns in "Little subset" class.
Approximate lower bound for number of essentially different patterns in this class can be obtained by dividing total number of such patterns (not e-d) by number of VPT for this class.

Total number of patterns can be calculated in this way.
1. There are 9 variants to select row which will contain 1 clue.
2. There are 9 variants of row containing 1 clue.
3. There are 27 variants of row containing 2 clues.

So, total number of patterns is 9 x 9 x 27^8 = 2.28 x 10^13 (approx.)

Number of VPT for this class can be evaluated as 6^8 (all classic VPT, except of transposing, because transposing can destroy class properties).

Therefore, lower bound for number of essentially different patterns in "Little subset" class can be estimated as (2.28 x 10^13)/(1.68 x 10^6) = 1.38 x 10^7 = 13,800,000 patterns. Too many patterns for "Little subset" to my mind.

Serg

by **champagne** » Sun Mar 30, 2014 5:48 pm

Serg wrote:Hi, champagne!
If my understanding is correct, you are planning to do exhaustive search for class of pattern having following properties (constraints):

1. Each pattern contains 17 clues.
2. One row of the pattern contains 1 clues, remaining rows contain 2 clues each.
3. Each minirow of the pattern contains not more than 1 clue.
4. You consider essentially different patterns only.

Let's call this class of patterns as "Little subset of 17-clue patterns set".

Let's calculate number of patterns in "Little subset" class.
Approximate lower bound for number of essentially different patterns in this class can be obtained by dividing total number of such patterns (not e-d) by number of VPT for this class.

Total number of patterns can be calculated in this way.
1. There are 9 variants to select row which will contain 1 clue.
2. There are 9 variants of row containing 1 clue.
3. There are 27 variants of row containing 2 clues.

So, total number of patterns is 9 x 9 x 27^8 = 2.28 x 10^13 (approx.)

Number of VPT for this class can be evaluated as 6^8 (all classic VPT, except of transposing, because transposing can destroy class properties).

Therefore, lower bound for number of essentially different patterns in "Little subset" class can be estimated as (2.28 x 10^13)/(1.68 x 10^6) = 1.38 x 10^7 = 13,800,000 patterns. Too many patterns for "Little subset" to my mind.

Serg

Hi Serg,

I am afraid that your approach does not account the fact that with 17 clues many rows columns will have very similar patterns
On top of it, in the general case, (not here) you can not have 2 empty rows or 2 empty columns in the same band/stack

I started from a 18 clues pattern which is much simpler in that situation.

With 18 clues 222 222 222 never 2 clues in a mini row/mini column

a) you have exactly 2 clues per row and 2 clues per column
b) in the canonical form, r1c1=r1c3=r4c1=1

c) and (due to the row 1 canonical form) you have only one clue per mini row, mini column

I coded these constraints and found at the end 72 ED patterns. (see above)

I am prepared to accept that I made a mistake. If the order of magnitude is yours, it should not be too difficult to give an example of a missing pattern.
I expanded the 72 "18 clues" patterns to 17 clues patterns suppressing one of the clues and replacing the pattern by the canonical form. I got 663 ED patterns again very far from your figures.

I can publish the corresponding patterns to let you give an example of a missing pattern.

I checked that in the 72 patterns I have the 2 patterns corresponding to the puzzles of the 17 clues file. They are there and I started the full scan for one of them (I am waiting for a free core to launch the second).

by **coloin** » Sun Mar 30, 2014 6:39 pm

I am prepared to accept the 72 figure ......
I think 2 clues in a box witout a repeating minirow - means that the 2 clues are effectively "diagonal"
a while back i looked at 27 clue 9*3 diagonal patterns for the patterns game here

two clues diagonally - infers only one place for the third clue

With 3 clues in a box B1B2B3B4B7 can always be normalised to one pattern - leaving the B5B6B8B9 to be variable

Code: Select all: +---+---+---+ |1..|3..|...| |.2.|...|.5.| |...|..4|..6| +---+---+---+ |7..|...|...| |...|...|...| |..8|...|...| +---+---+---+ |...|...|...| |.9.|...|...| |..1|...|...| +---+---+---+

surprizinly there were only 15 patterns - and here is a representative of each [all but one symmetric]

Code: Select all: ..1..2..3.2..1..4.5..6..1....2..4..1.5..6..7.7..2..3....7..5..8.8..7..9.9..3..2.. # C27/S4.da/M1.16.3 2...4...6..4..2.3..7.8..1....24...1.1...3...2.3...54....5..9.7..1.6..2..6...7...9 # C27.M/S4.da/M1.31.2 ..2..3.1..3..1.2..5..6....4..5..7.2..9..4.8..6..9....7.8..9..5.2..5..4....3..8..9 # C27/S2.d/M1.33.1 ..1.2.3...2...1..43..5...6...42...8.9...3...2.3...67...4...3..75..8...4...2.6.1.. # C27.M/S2.p/M1.13.4 1....2..3.9..4..1...73..5....21....9.6..2..5.9....56....3..41...7..8..2.2..6....8 # C27.M/S4.da/M1.11.6 2...3.1....14...2..5...6..3.6.2..4..3...5..7...7..3..65..8..7...9..1..4...6..2..9 # C27/S2.d .2..7...84..6..9....5..4.7..1.2..3..2...1...4..3..5.6..9.5..6....1..7..37...3..5. # C27.M/S4.da/M1.16.1 1..3..2...2..4..1...3..6..52...8..7..7.5..3....9..1..67...9.5...4.1....8..8..2.6. # C27/S2.d ..2.1.3...1...2.4.5..3....2..5..7.8.6...3...4.4.6..9..7....4..6.3.2...5...4.9.7.. # C27.M/S4.da ..1..2..3.2..1..4.3..5..6....51..2...4..7...12....8.3...96...7..6..4.3..8....7..4 # C27 [asymmetric] ..1..3..2.2..4..3.4..6..5....23...1..4...57..5...9...8..6.8..7..9.1..6..7....2..1 # C27/S2.d 2..1....3..1..2.4..5..3.6..5..7...9...6.8.2...8...4..1..7.6..8..6.4..1..3....7..5 # C27/S4.da 2...3.1....14...2..5...6..3.6.2..4..3....4.7...7.8...65..8..7...9..1..4...6..2..9 # C27/S2.d 6....2.7...8.1...5.9.5..3....2..1..3.1..2..4.5..3..2....4..8.9.1...9.8...3.4....7 # C27.M/S4.da ..1.2...3.2...34..5..1...6...4..1.7.2...9...6.6.4..8...9...2..8..69...1.3...5.7.. # C27.M/S4.da

With the proviso that there cannot be 3 clues in a row/column. The B1B2B3B4B7 is fixed. There are reduced options of 2 or 1 or 0 for each of B5B6B8B9

upperlimit 15 * 16 = 180 ...... so prob 72 is about right

by **Serg** » Mon Mar 31, 2014 10:54 am

Hi, champagne!
Let's refine considered class of pattern:

1. Each pattern contains 18 clues.
2. Each row and each column of the pattern contain 2 clues each exactly.
3. Each minirow and each minicolumn of the pattern contain not more than 1 clue each.
4. You consider essentially different patterns only.

Right?

I would be interesting to see your list of 72 ED patterns of the class defined above. (Do you mean that no other ED patterns of this class do exist?)

Serg

by **champagne** » Mon Mar 31, 2014 11:16 am

Serg wrote:Hi, champagne!
Let's refine considered class of pattern:

1. Each pattern contains 18 clues.
2. Each row and each column of the pattern contain 2 clues each exactly.
3. Each minirow and each minicolumn of the pattern contain not more than 1 clue each.
4. You consider essentially different patterns only.

Right?

I would be interesting to see your list of 72 ED patterns of the class defined above. (Do you mean that no other ED patterns of this class do exist?)

Serg

Hi Serg,

In fact, I consider all "17 clues" patterns with a max lex first row starting with 1.. 1.. ..., but the consequences are what you have in your list. Extension to 18 clues is just to "somehow" make it simpler, adding one clue to the row having only one clue with the first row constraint unchanged.

I agree on all terms of your post and I am very curious to see if I missed a point.

The list of the 72 patterns is 5 or 6 posts above, I reproduce it here

Hidden Text: Show

The New Sudoku Players' Forum

No new 17s within {-2+2}

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

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

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

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

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

Ideas on how

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

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

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

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

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

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

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

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

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