The New Sudoku Players' Forum

[champagne]

Its definitely a nice result for the 640 octal ..... i get it now ......
However arnt the reductions going to be less for the other octals ? ...........
Unless you ignore all the patterns with the max 5 clues in a row ..... this would get rid of octals 770,760,744,666 and 664.

C

I have to work on your posts, just some quick answers.

In the entry 744 of the table, we see one active known pattern and we have 20 for the entry 664, so it seems difficult to skip 5 clues in row 1;

regarding the reduction factor, I have no theory except a general feeling (reinforced by our experience on the 18 clues 222 222 222) that with 17 clues, we have many canonical effects on top of the classical morphs.

Nevertheless, if the count increases in row 1, the chances to produce "invalid patterns" (band and empty rows columns limitations) grows as well.
I have now the count of my code for the entry 664 and I get about 127 millions puzzles, I am hoping to get to-day most of the missing first estimates for the table I posted .

[champagne]

Bad news are coming for the count of 17 clues patterns with other starts for row 1.
Back to the filters, some facts regarding the distribution of clues in bands stacks.

well it is proven that a "crossing" stack/band cant have valid puzzles if there is 3 in each
all these have been shown by Serg to be invalid

Code: Select all

    111   012   210   300
    199   199   199   099
    199   299   099   099   


are all invalid clue counts - and this could probably be taken a bit farthur


however

Code: Select all

    211    310    211
    199    199    199
    199    099    099   


can give valid puzzles


it is not proven that a band count of

Code: Select all

   3
    3
    27


is invalid.....
however no puzzle has ever been found with

Code: Select all

    3
    4
    27


C

all that should be improved and applied.
One possible way to go in that way would be to build a catalog of "possible patterns" with known filters and to shrink it in the future when new facts are established.

regarding the "can give valid puzzles", a side question is "is it still true for 17 clues.

here below the photography of the bands/stacks configuration for all known pattern having at least a 3 clues band or stack.

None of them have twice 3 clues
The maximum of clues in a band stack is 8

Code: Select all

bands stacks  number of patterns
8 6 3 7 5 5   1
8 6 3 6 7 4   1
8 6 3 6 6 5   3
8 6 3 5 7 5   1
8 6 3 5 6 6   1
8 6 3 5 5 7   1
8 3 6 7 6 4   2
8 3 6 6 6 5   1
8 3 6 5 6 6   2
7 7 3 7 5 5   2
7 7 3 6 7 4   1
7 7 3 6 6 5   6
7 7 3 6 5 6   14
7 7 3 5 5 7   1
7 6 4 8 3 6   1
7 6 4 7 7 3   1
7 6 4 6 8 3   1
7 5 5 8 3 6   1
7 5 5 7 7 3   2
7 5 5 7 3 7   2
7 3 7 7 5 5   1
7 3 7 6 5 6   1
7 3 7 5 6 6   1
6 8 3 6 6 5   1
6 7 4 7 7 3   1
6 7 4 6 8 3   1
6 6 5 8 6 3   3
6 6 5 7 7 3   5
6 6 5 6 3 8   1
6 5 6 8 6 3   4
6 5 6 8 3 6   1
6 5 6 7 7 3   2
5 7 5 7 7 3   1

[coloin]

I do think there is are 17 puzzles with 9-4-4 though.....
so those snapshots - must have an 8 and/or at least two 7s ?

you already are excluding 2-x-x
bands with 10 could be excluded - which is similar to excluding 3-4-10 - which we have found difficult to prove.

searching all octals 770,760,744,666 and 664 is similar to he task of proving that we have found all the horizontal 5 plus12 puzzles - again problematic. The 9plus12 aids this somewhat - the patterns have 12 varied clues rather than 17 and there are 6^4 reductions too.

All academic until we find a way to reduce the remaining octals......

C

[champagne]

All academic until we find a way to reduce the remaining octals......

C

also academic, as the proof of the non existence of valid puzzles has been given through another process, is
"what would be the situation with 16 clues".

[Serg]

Hi, coloin!

What about " not more than one band/stack with 3 clues"

well it is proven that a "crossing" stack/band cant have valid puzzles if there is 3 in each
all these have been shown by Serg to be invalid

Code: Select all

111   012   210   300
199   199   199   099
199   299   099   099    are all invalid clue counts - and this could probably be taken a bit farthur

I confirm that all these 4 map cannot have valid puzzles (it can be easily proved by considering "40 maximal patterns" list). It can be formulated as follows:

A pattern having valid puzzles cannot contain 3 or less clues in a band and 3 or less clues in a stack.

About champagne's observation, that no known 17-clue puzzles contain more than one band/stack with 3 clues.
It is well known "coloin's rule 1" conjecture: any valid puzzle must contain not less than 8 clues in any 2 bands (stacks). But this conjecture isn't proven yet.

Serg

[Edited. I refined constraint in "3+3" rule (band+stack) for valid puzzles.]
[Edited2. I found an error in my definition of "coloin's rule 1" - any valid puzzle must contain not less than 8 clues in any 2 bands (stacks).]

[Serg]

Hi, champagne!

champagne,

In order to check that your algorithm works properly, you should first use it without any filter and show that you get a fair estimate of the exact number of patterns i.e. 5.51 x 10^10

JPF

yes,
but the canonical algorithm mixes classical morphs and other "symmetries", so, at the end, it's not so easy.

Are you really sure that max lex canonical algorithm can produced other number of canonic patterns than classic min lex canonical algorithm?

Serg

[champagne]

Are you really sure that max lex canonical algorithm can produced other number of canonic patterns than classic min lex canonical algorithm?

Serg

No, either method would work properly. I use the maxlex because I am supposed to create ED patterns using a maxlex pattern,
but I am not convinced that in the method described by JPF all "symmetry" effects are correctly accounted.

Meantime (partly after remarks from JPF), I thought a little more about my generation algorithm.

So far, I am convinced that I produce one occurrence and only one of any ED pattern, but this has to be checked carefully. It is a key point to have the right count.

BTW, I had problems in my (tailor made some days ago for the patterns) canonical algorithm with the size of tables, especially with patterns starting by an octal 7xx.
The overflow did not crash the program, so I had to investigate in results too low in my view to find the bug. I am waiting for freshly adjusted results.

Anyway, I have to run the generation once more after having added the last filter described by coloin, but using one of your results.

At the end, the results will be convincing only if a contradictory code comes to the same count.

[eleven]

Champage,

not that i did not hope, that the filters could drastically reduce the number of possible 17 clue patterns.

But i cannot doubt, that JPF's calculations are correct, especially the exact number of e-d patterns, which incorporates all automorphisms ("symmetries").
Also his approximations for the number of puzzles, which fall into the 2 filters, seem to be very reliable.
And i do not believe, that the new filters will eliminate more than a few percent of the patterns.

So if at the end you will not get a count in the magnitude of 10^10, you should look for a flaw, which eliminates too much patterns.

Also if i look at the number of e-d 16 clue patterns, 15 bio, i do not think, that it can be reduced to a count, which (theoretically) could be exhaustively searched with current methods in a time, which could compare to that of the 16 clue proof.

[blue]

I'm in agreement with what eleven said, except that I didn't hold out any hope for a large reduction by filtering.
You should be getting results like these (below).

[ I was going to wait until the sample size was >10^9 patterns, but I'll post what I have. ]

This table has errors, see added comments below

Code: Select all

Monte Carlo sample size: 551452672 random 17-clue patterns

+-------------------------+---------------------------------------------------------------------+
|        raw results      |                      results with filtering                         |
+-----------+-------------+-------------+-------------+-------------+-------------+-------------+
| maxlex r1 | ED patterns |    3+/chute | w/o 2 empty |        both |   Serg's 40 |        both |
+-----------+-------------+-------------+-------------+-------------+-------------+-------------+
| 1..1..... |        1109 |        1109 |        1109 |        1109 |        1109 |        1109 |
| 1..1..1.. |     3241818 |     3224829 |     3204236 |     3192101 |     3168942 |     3164088 |
| 11....... |    30572226 |    30245708 |    30206115 |    29951571 |    29522707 |    29360454 |
| 11.1..... |  4436338312 |  4172592432 |  4085405062 |  3919251946 |  3012439243 |  2969339982 |
| 11.1..1.. | 12375979589 | 11143985260 | 10332413611 |  9671075135 |  6100737835 |  6006979047 |
| 11.11.... |  7708482413 |  6508939543 |  5997613742 |  5416728894 |  2448674185 |  2402043753 |
| 11.11.1.. |  6649441925 |  5501234916 |  4931771906 |  4371448085 |  1669592685 |  1636360467 |
| 11.11.11. |   539068778 |   416915224 |   376701515 |   316042437 |    69707433 |    67975824 |
| 111...... |  5303002485 |  4257312019 |  3972312968 |  3462462706 |  1468719261 |  1416870635 |
| 1111..... |  9538518198 |  7456936010 |  6666526074 |  5765454175 |  2017375091 |  1961743940 |
| 1111..1.. |  3605192056 |  2786527835 |  2382918742 |  2040430388 |   609075063 |   594156101 |
| 11111.... |  2790145541 |  1964968007 |  1730801693 |  1416018803 |   277131543 |   268850219 |
| 11111.1.. |  1735550737 |  1228565434 |  1046419776 |   842663989 |   137570996 |   133407175 |
| 11111.11. |   183812712 |   119786243 |   102508153 |    76465582 |     5309514 |     5118207 |
| 111111... |   127616585 |    78080770 |    66286304 |    50080752 |     3873359 |     3719912 |
| 1111111.. |    72618710 |    44851187 |    36044340 |    26577107 |     1464930 |     1401693 |
| 11111111. |    14679464 |     8284930 |     6481624 |     4283224 |       54085 |       51588 |
| 111111111 |      410280 |      207948 |      125296 |       73014 |           0 |           0 |
+-----------+-------------+-------------+-------------+-------------+-------------+-------------+
|    totals | 55114672938 | 45722659404 | 41767742266 | 37412201018 | 17854417981 | 17500544194 |
+-----------+-------------+-------------+-------------+-------------+-------------+-------------+


This is from some old code of mine, that was primarily concerned with the total at the bottom of column 6, which is for filtering by Serg's 40 "magic" patterns. I modified it to do the breakdown by the maxlex top row, and added the other types of filtering. Looking at the code, it matched the method described by JPF here, exept that rather than tracking 'p' and 'a' separately, it just estimated thier product, 'p.a'.

The close agreement with the 55,113,078,988 number and 2 of the 3 of JPF's other numbers, makes me thing that the code is correct, and JPF has a typo for the total at the bottom of the 3rd column [ (4.27 * 10^10) -vs- (4.57 * 10^10) ].
Added: No, it was my mistake ... damn it. A bug in the "3+/chute" filter. (Sorry JPF)
I should have known, since Serg and Colin's proof that there are no valid 17-clue patterns with 2 clues in a band, was based on the 40 patterns, and that should have meant that the last column would match the 2nd to last. The bug is fixed, and that's indeed the case. I'll post a corrected version in a few hours.

For the rest of the numbers above, the top row is order of magnitude only, and the 2nd and last rows, probably have errors in the 2nd digit. The totals (at least for the 6th column), should be accurate to a part in 10,000 (according to the program output).

The last column, is ED patterns with 3+ clues per chute, that pass filtering by Serg's 40 patterns.
Note: The total at the bottom, is only 2% lower than in the column for filtering by Serg's patterns alone.

Best Regards,
Blue.

[champagne]

Hi blue,

This has very high chances to be better than my provisional figures.

If you accept it, I would check the 2 first items to fix my code anomalies.

My problems start with the first one where i find 1173 puzzles, more than your ED first line
This should come from my canonical process (general or tailor made for patterns)

Could you post somewhere your 1109 list (reversely, I can send you my 1173 list to see where the canonical fails)

[blue]

Hi champagne,

Your 1173 number is probably correct.

The 1109 number is just an estimation, and (for that line) not a very accurate one either.
The patterns come up so rarely, that there may have been only 20-30 hits in the 500M grids.

[champagne]

Hi champagne,

Your 1173 number is probably correct.

The 1109 number is just an estimation, and (for that line) not a very accurate one either.
The patterns come up so rarely, that there may have been only 20-30 hits in the 500M grids.

I wrote quickly a comment before going to visit my shrimps pots, but

1) I agree that these are estimates, giving small chances to match the results
1) my preliminary count for item 2 is not so far from your results
3) I had a big flaw in the program with the size of the tables in the new canonical process. Just considering the run time of the ongoing batches I am expecting quite different results. I hope that the rest is correct.

4) I am obliged to wait until the end of these batches before restarting a new count with adjustments in the program (with now serg's exclusion for 3 clues band and stack)

5) As I'll likely come to your order of magnitude, I am thinking of measuring the effect of the exclusion of a 3+4 in band or stack (see above coloin's comment).


EDIT just a side question where is the description of the 40 serg's magic pattern.

[blue]

EDIT just a side question where is the description of the 40 serg's magic pattern.

They're here.

Each one is "maximal" in the sense that it's pattern with no valid puzzles, where adding a cell in any of the unmarked position, gives a pattern that does have valid puzzles.

I should add that the list is complete for patterns with boxes 5,6,8 and 9 filled.
(No others exist).

[blue]

Added: No, it was my mistake ... damn it. A bug in the "3+/chute" filter. (Sorry JPF)
I should have known, since Serg and Colin's proof that there are no valid 17-clue patterns with 2 clues in a band, was based on the 40 patterns, and that should have meant that the last column would match the 2nd to last. The bug is fixed, and that's indeed the case. I'll post a corrected version in a few hours.

As promised, here are results from two concurrent runs with the same sample size.
With two runs, we can get an idea of the errors in the estimates.
It's more than I would have guessed, for the bottom row ("111111111")

Code: Select all

Monte Carlo sample size: 551452672 random 17-clue patterns

+-------------------------+-------------------------------------------------------+
|        raw results      |               results with filtering                  |
+-----------+-------------+-------------+-------------+-------------+-------------+
| maxlex r1 | ED patterns |    3+/chute | w/o 2 empty |        both |   Serg's 40 |
+-----------+-------------+-------------+-------------+-------------+-------------+
| 1..1..... |        1248 |        1248 |        1248 |        1248 |        1248 |
| 1..1..1.. |     3271911 |     3249584 |     3232942 |     3220461 |     3196816 |
| 11....... |    30514744 |    30251810 |    30145859 |    30018414 |    29479717 |
| 11.1..... |  4436876177 |  4139721402 |  4086179790 |  3948845587 |  3012362277 |
| 11.1..1.. | 12373593348 | 10756058970 | 10331203086 |  9642805526 |  6100944466 |
| 11.11.... |  7709713948 |  6082544050 |  5998967868 |  5353313929 |  2449490655 |
| 11.11.1.. |  6649026097 |  5077304988 |  4931832577 |  4299428951 |  1670100179 |
| 11.11.11. |   538558788 |   370352744 |   376312591 |   306934242 |    69535471 |
| 111...... |  5302585756 |  4010620125 |  3971730657 |  3479368099 |  1468429770 |
| 1111..... |  9537892204 |  6821510441 |  6664504973 |  5705374288 |  2017233916 |
| 1111..1.. |  3605251411 |  2517318508 |  2383383315 |  2008246441 |   609587410 |
| 11111.... |  2791336719 |  1696619041 |  1731652970 |  1379953938 |   277330408 |
| 11111.1.. |  1734428551 |  1054470825 |  1046118567 |   818246314 |   137988765 |
| 11111.11. |   183539654 |    95833280 |   102283216 |    72198583 |     5282402 |
| 111111... |   127492052 |    63358524 |    65902996 |    48210950 |     3868783 |
| 1111111.. |    72918602 |    35909614 |    36294863 |    25489590 |     1502581 |
| 11111111. |    15076778 |     5918382 |     6523644 |     3923214 |       53461 |
| 111111111 |      351342 |       89032 |      122384 |       54223 |           0 |
+-----------+-------------+-------------+-------------+-------------+-------------+
|    totals | 55112429330 | 42761132568 | 41766393546 | 37125633998 | 17856388325 |
+-----------+-------------+-------------+-------------+-------------+-------------+

Code: Select all

Monte Carlo sample size: 551452672 random 17-clue patterns

+-------------------------+-------------------------------------------------------+
|        raw results      |               results with filtering                  |
+-----------+-------------+-------------+-------------+-------------+-------------+
| maxlex r1 | ED patterns |    3+/chute | w/o 2 empty |        both |   Serg's 40 |
+-----------+-------------+-------------+-------------+-------------+-------------+
| 1..1..... |        1317 |        1317 |        1317 |        1317 |        1317 |
| 1..1..1.. |     3266502 |     3243759 |     3231555 |     3217549 |     3191339 |
| 11....... |    30603290 |    30337513 |    30243142 |    30114657 |    29576584 |
| 11.1..... |  4436330754 |  4139374082 |  4085709947 |  3948658302 |  3012705367 |
| 11.1..1.. | 12375091908 | 10756989434 | 10331974139 |  9643336318 |  6100308001 |
| 11.11.... |  7709380981 |  6081479762 |  5998302073 |  5352181966 |  2448129317 |
| 11.11.1.. |  6649807065 |  5076358577 |  4930385675 |  4297765433 |  1669007115 |
| 11.11.11. |   539270278 |   371234878 |   376952661 |   307518356 |    69674358 |
| 111...... |  5303719175 |  4011507460 |  3971562440 |  3479633876 |  1468115871 |
| 1111..... |  9538664019 |  6822232817 |  6665359302 |  5706316053 |  2018232124 |
| 1111..1.. |  3604430573 |  2516278558 |  2381048247 |  2006596028 |   609522925 |
| 11111.... |  2790382958 |  1696122988 |  1730673276 |  1379393400 |   277442529 |
| 11111.1.. |  1733606812 |  1054824178 |  1046359104 |   818472221 |   137586667 |
| 11111.11. |   183389812 |    95672690 |   102133374 |    72043125 |     5250714 |
| 111111... |   127540173 |    63082831 |    65704825 |    47951067 |     3839591 |
| 1111111.. |    72990368 |    35900115 |    36158611 |    25492988 |     1475886 |
| 11111111. |    14916535 |     5824774 |     6541048 |     3919193 |       52212 |
| 111111111 |      416660 |      104009 |      136806 |       54362 |           0 |
+-----------+-------------+-------------+-------------+-------------+-------------+
|    totals | 55113809180 | 42760569742 | 41762477542 | 37122666211 | 17854111917 |
+-----------+-------------+-------------+-------------+-------------+-------------+

For the "1..1....." row, the code has been running for only a few minutes (10 ?), since I copied off the results, and already the numbers are down to 1184 and 1250.

[JPF]

blue,
Congratulations !
I am glad you confirmed my first estimations.

The advantage of Monte Carlo algorithms is that they don't need sophisticated coding.
It's straightforward, provided that you have an efficient automorphims counter (thanks to dobrichev)
The breakdown by first row maxlex is unnecessary, except that it points out an interesting fact:

Code: Select all

numbers are %

maxlex      all 17    filtered   known valid
            
1..1.....            
1..1..1..            
11.......      0,1      0,2       0,2
11.1.....      8,0     16,9      78,0
11.1..1..     22,5     34,2      14,4
11.11....     14,0     13,7       2,9
11.11.1..     12,1      9,4       0,1
11.11.11.      1,0      0,4      
111......      9,6      8,2       3,6
1111.....     17,3     11,3       0,8
1111..1..      6,5      3,4      
11111....      5,1      1,5      
11111.1..      3,2      0,8      
11111.11.      0,3         
111111...      0,2         
1111111..      0,1         
11111111.            
111111111            
----------   ------   ------    ------
    totals   100,00   100,00    100,00


92% of the known valid patterns have only two different first row maxlex:

Code: Select all

11.1.....
11.1..1..

far from the ed patterns average, even after your filters.
I don't know how we could use this observation.

JPF

This should come from my cannibalization process

Are you speaking about your shrimps ?