The New Sudoku Players' Forum

[Serg]

Hi, colleagues!
A year ago coloin and me done similar work - counted e-d patterns, containing 7 clues in the first 2 bands and 27 clues in the third band (we considered not only {3,4,27} patterns, but all possible patterns beloning to this class (for example - {2,5,27} patterns)). (See thread Ask for patterns that they dont have puzzles 2.)

I found after applying 40-patterns list, that {2,5,27} patterns cannot have valid puzzles. I came to higher bound of {3,4,27} patterns which can have valid puzzles - 3428 patterns. My method was the following:

1. Write (manually) all possible maps having 7 clues in the first 2 bands and 27 clues in the third band.
2. Filter out (manually) maps by 40-patterns list.
3. Calculate (by a program) number of e-d patterns for possible maps. (This program enumerates patterns without generating them.)

If one would generate all possible e-d {3,4,27} patterns, and then apply "40-patterns list" filter, then one would get even less (than 3428) possible patterns.

Serg

[champagne]

If one would generate all possible e-d {3,4,27} patterns, and then apply "40-patterns list" filter, then one would get even less (than 3428) possible patterns.

Serg

whatever will be the next step, it would be good to have the list of such ED patterns.

For the time being, before the magic 40 filter, and having added the missing 1,1,1 for the 3 clues band, I find ED 2561 patterns.

I can post my list, you could post yours, this would be one way to come to the right final list.

Anyway, we have the same order of magnitude. then, if I am right, the proof (whatever is the result) would require the check of about 2500 to 3000 patterns with 34 given, and only 401 permutations for the band with 27 given. This can be done in a relatively short period;

[champagne]

champagne,

I get 6099 {3,4,27} ed patterns and only 4919 without 2 empty rows in the same band.

JPF

On my side, I don't consider 2 empty rows.

Same question as to serg, could it be possible to try to match our lists to come to an agreed right count. For the time being, my count is 2561 without 2 empty rows.

My generation is based on a first list of 29 Ed patterns for the band containing 4 clues. This is half manual, half computer checked list.

here below, the corresponding octal table used in the generation. (each entry is the octal value for rows 4 5 6)

Code: Select all

   word tr4[29][3]={
      {0600,0600,0},{0600,0500,0},  //11.  11.  //  11. / 1.1
      {0600,0440,0},{0600,0140,0},  //11. / 1.. 1.. // 11. / ..1 1..
      {0600,0060,0},{0600,0044,0},  // 11. / ... 11. // 11. / ... 1.. 1..

      {0440,0440,0},{0440,0420,0},{0440,0220,0}, // 1.. 1.. / 1.. 1..//
      {0440,0404,0},{0440,0204,0},  // 1.. 1.. / 1.. ... 1..

      {0600,0400,0400},{0600,0400,0200},{0600,0400,0100},{0600,0400,0040},
      {0600,0100,0100},{0600,0100,0040},
      {0600,0040,0040},{0600,0040,0020},{0600,0040,0004},


      {0440,0400,0400},{0440,0400,0200},{0440,0400,0040},{0440,0400,0020},{0440,0400,0004},
      {0440,0200,0200},{0440,0200,0100},{0440,0200,0020},{0440,0200,004},
   };


EDIT I clearly missed also the case 3 + 1 + 0 in the 4 clues band, giving a chance to meet my friends count
EDIT2 I added (manually) the following entries for the 4= 3+1 case

Code: Select all

      {0700,0400,0},{0700,0040,0},
      {0640,0400,0},{0640,0100,0},{0640,0040,0},{0640,004,0},
      {0444,0400,0},{0444,0200,0},


I have now 3403 patterns (no band with 2 empty rows).

If I am right, only one of the magic 40 can reduce the count, it is when the 7 clues are locked in the same stack
applying that filter, I am left with 3317 ED patterns

[JPF]

Here what I finally came up with:

6099 ed {3,4,27} patterns
4919 ed {3,4,27} patterns without 2 empty rows in the same band
1871 ed {3,4,27} patterns (file1 attached) after filtering with the 40 magic patterns

numbers to be checked.

JPF

[champagne]

Here what I finally came up with:

6099 ed {3,4,27} patterns
4919 ed {3,4,27} patterns without 2 empty rows in the same band
1871 ed {3,4,27} patterns (file1 attached) after filtering with the 40 magic patterns

numbers to be checked.

JPF

Hi jpf

Fine

a)I downloaded your file, it has only six rows. Is it what you wanted to do?
I know I can add three rows with all '1' but ...

b) I am surprised by the huge effect of the 40 magic pattern. Could you post your 4919 patterns as well

c) I see that it is possible to attach a file in a post, but I don't catch how to do it. Can you explain?

[blue]

6099 ed {3,4,27} patterns
4919 ed {3,4,27} patterns without 2 empty rows in the same band
1871 ed {3,4,27} patterns (file1 attached) after filtering with the 40 magic patterns

numbers to be checked.

I get those number too.

[champagne]

I get those number too.

my best count so far without 2 empty rows is 3668, so I am interesting in getting the file with the 4919 to see what is wrong in my count.

Regarding the magic 40 effect, i don't have yet the code available, but I see only one pattern that can be used with the 27 clues band filled (pattern 136).
If I apply it, I get 3582 ED patterns to test, so surely other patterns in the magic 40 play a role, but I can't see which ones. Can you give an example.

if as usual you both have the right count, Checking whether a valid puzzle exists with the distribution 3+4+27 should be relatively easy.

[JPF]

Here is the 4919 file in 2 parts - the maximum allowed size is 256 KiB per file.

That's why it doesn't make sense to add the last band.

JPF

[Serg]

Hi, champagne!

Regarding the magic 40 effect, i don't have yet the code available, but I see only one pattern that can be used with the 27 clues band filled (pattern 136).
If I apply it, I get 3582 ED patterns to test, so surely other patterns in the magic 40 play a role, but I can't see which ones. Can you give an example.

All patterns from 40-patterns list, having 100%-filled band (or stack), can be used for filtering. Here is such patterns' list: P123 (transposed), P138 (transposed), P139 (transposed), P98 (transposed), P99 (transposed), P136.

Hope, I didn't miss something.

Serg

[Edited. I corrected an error (thanks to blue, who pointed it) - pattern P110 is not applicable to {3,4,27} patterns.]

[blue]

Regarding the magic 40 effect, i don't have yet the code available, but I see only one pattern that can be used with the 27 clues band filled (pattern 136).
If I apply it, I get 3582 ED patterns to test, so surely other patterns in the magic 40 play a role, but I can't see which ones. Can you give an example.

P98, P99, P123, P136, P138 and P139 are all useful.
P98, P123, P138 and P139 alone, are sufficient.
Here's an example for each of those:

Code: Select all

x . . | x . . | . . .   removed by P98
. x . | . . . | . . .
. . . | . x . | . . .
------+-------+------
. x . | . . . | . . .
. . x | . . . | . . .
. . . | . . x | . . .
------+-------+------
x x x | x x x | x x x
x x x | x x x | x x x
x x x | x x x | x x x

x . . | x . . | . . .   removed by P123
. . . | . . . | x . .
. . . | . . . | . x .
------+-------+------
. . . | . . . | . . x
. . . | . . . | . . x
. . . | . . . | . . x
------+-------+------
x x x | x x x | x x x
x x x | x x x | x x x
x x x | x x x | x x x

x . . | x . . | . . .   removed by P138
. . . | . . . | x . .
. . . | . . . | . x .
------+-------+------
. . . | . . . | x . .
. . . | . . . | . . x
. . . | . . . | . . x
------+-------+------
x x x | x x x | x x x
x x x | x x x | x x x
x x x | x x x | x x x

x . . | x . . | . . .   removed by P139
. . . | . . . | x . .
. . . | . . . | . x .
------+-------+------
. . . | . . . | x . .
. . . | . . . | . x .
. . . | . . . | . . x
------+-------+------
x x x | x x x | x x x
x x x | x x x | x x x
x x x | x x x | x x x

[champagne]

many thanks to you all three, it's a terrific result.


to JPF, I did not see how you attach a file, but this is a side point.

Now the next question

I guess we agree that we have only 1871 ED patterns to check.

Do we agree that the process is to apply all the 401 available permutations for the band having 27 clues to these patterns to see whether a valid puzzle exits

If yes, it can be done in say one week.

(my check on a lot of about 20 patterns shows less than 100k hints per pattern to validate)

[Serg]

Hi, blue!
Nice examples (as usual)!

P98, P99, P123, P136, P138 and P139 are all useful.
P98, P123, P138 and P139 alone, are sufficient.

You are right - pattern P110 (shown in my previous post) is not applicable for {3,4,27} class of patterns. Maybe your shortened list of filtering patterns is correct, but at the moment it is not obvious for me.

I'd like to say - it is not necessary to do separate "2 empty rows" filtering, because 40-patterns list includes such filter (pattern P137), i.e. one should apply 40-patterns list filtering to raw generated patterns.

Serg

[blue]

Maybe your shortened list of filtering patterns is correct, but at the moment it is not obvious for me.

It probably shouldn't be obvious -- it was determined through experimentation.

I'd like to say - it is not necessary to do separate "2 empty rows" filtering, because 40-patterns list includes such filter (pattern P137), i.e. one should apply 40-patterns list filtering to raw generated patterns.

Absolutely.

[coloin]

......Checking whether a valid puzzle exists with the distribution 3+4+27 should be relatively easy.

I dont think so .....
If you check a pattern - then you cant fix the 27 clues. I missed that minor detail earlier
as well !
However I am not aware that there is a band restriction for the 27 clues - as any puzzle can easily be made from any band.....

If you fix the band - it is possible to use the 44 ed bands instead of the 416 - the ordering of the vertical 3 clues in the band doesnt matter.

However if you fix the band - to search a single pattern one would have to search many of the 6^4 ways of ordering the band ....... or i am wrong !

C

[coloin]

IMO you have to iterate the values of the 7 cells in the each ED pattern over the 416 x 6^4 = 539136 base 27-clue bands.
For individual pattern the 539136 factor can be reduced by examining the pattern automorphisms. (Assuming the band 3 has 27 givens, the symmetry over stack and column permutations does the reduction. The rest symmetries are already accounted during the pattern canonicalization).

Indeed dobrichev has already commented. But the 416 -> 44 reduction at least is in our favour.
C