The New Sudoku Players' Forum

[dobrichev]

Hi coloin,

Excellent .... does the computation get any easier for the 5,6,7 [8,9] !!

Yes for the rookery count since R(5) = R(4), R(6) = R(3), R(7) = R(2), R(8) = R(1), and R(9) = R(0).
"5-rooreries minimal clues to compete" is in progress. So far the max is 9 and I expect ~50 5-rookeries to have this max.

I am confused over the difference between a rookery and a template though !!

one 9-rookery, contents don't matter.

i would say the rookery was the actual clues and the template was the position of the clue .... i think red ed did query this.
From your recent post it is clear now why there is confusion

Code: Select all

So, the number of distinct 3-templates is 259272. The first and last of them alphabetically are respectively

    ......123...123...123............231...231...231............312...312...312......
    ..1..2..3.2..3..1.3..1..2....2..3..1.3..1..2.1..2..3....3.2.1...1.3....22....1.3.

The number of 3-rookeries having at least one valid 3-template is 92048 (confirming dukuso's count).

    ......111...111...111............111...111...111............111...111...111......
    ..1..1..1.1..1..1.1..1..1....1..1.1..1..1.1..1..1....1..1.1..1..1.1..1..1....1..1

I used these definitions

a k-rookery is a subset of the 81 cells in a 9*9 square which contains exactly k-cells from each row,column,block

a k-template is a k-rookery whose 9*k cells are filled with numbers from {1,2,..,k}, such that the rookery-cells from each row,column,block contain each digit from {1,..,k} exactly once

In addition, I generated 3-templates by combining disjoint 1-templates, which discards templates like this, where 1-template for digit 1 must share r9c3 with 1-template for digit 2. I didn't check the other example for uncompletable 2-rookery. The only uncompletable template I found is the following 4-template, and its corresponding 4-rookery.

Code: Select all

....12.34.134..2...423..1...21.34...3..1...424..2...13.34....211...234..2...413..
....11.11.111..1...111..1...11....111...111..1...111...11.11...1..1...111..1...11

That is why the sum of 5-rookeries in the table with minimal clues to complete is one less (2648603 instead of 2648604).

Actually, this suggests additional constrains to the definitions:
- a k-rookery must have at least one valid k-template. (Alternative: There are valid and invalid k-rookeries).
- a k-template must be completable to a valid sudoku grid. (Alternative: There are uncompletable k-templates forming uncompletable k-rookeries).

Anyhow a while back I could only generate 181 distinct 2-rookeries/templates. dukuso would say there were 170 classes [? templates/rookeries].

Have I overcounted ? - using havards program - they are all ED ?
Well the bug in gsfs minlexing has surfaced again - except havards usually is reliable.....
Hmmph, here are the 11 pairs - properly minlexed. I dont know why my usually reliable sofware thinks the pairs are different though....

Here is #4 and #6.

Code: Select all

#4#.......12....12....12.............21...12....12............12.....2..1..2.1...... #
#6#.......12....12....12.............21...12....2.1...........12.....2..1..12....... #

not sure now if they are different or not !

Will check this soon. I started directly from 3-templates, later generating 3-rookeries by them.
I am still using the gsf's implementation of Michael Deverin's row-minlex algorithm. BTW Michael Deverin says that he can't reproduce the bug with his original code so probably it is a bug in the gsf's implementation. Is Havard's code available?

Cheers,
MD

[coloin]

Thanks for all your endevours ! Yes the definition is set. Interesting - hopefully not fruitless !

I think dukuso may well be right though.
In #4 and #6 they have the same minlex 2-rookery.Gsf has a slow minlex rookery function which works. in the case of #4 template a converse 7-template has 8 solutions - and there is 3 unavoidables [U4+U6+U8] in the #4 template. So i think both gsfs implementation and harvards are wrong !

See here

We will see if he is right with this one !

checking gordon's 17s, the minimum numbers of clues required to uniquely solve a 1,2,..,9 rookery are 0,1,2,3,5,7,10,13,17

Havards program "Sudoku Archetect" was a failed commercial venture - he has dropped the idea and moved on i believe. He gave me a copy righted b-copy . Its a brilliant -gui program and has remarkable graphics. I could pm him.

It doesnt usually make mistakes though on removing isomorph dups in up to a million different subpuzzles/puzzles/grids.

C

[dobrichev]

This is the result of my calculations. 4-templates' clues counting is in progress.

Code: Select all

----------------------------------------------------------
|k|  Template   | Rookery |   Min. Clues to Complete     |
| |   classes   | classes |   Rookery    |   Template    |
|--------------------------------------------------------|
|0|           1 |       1 |  0       (1) |  0        (1) |
|--------------------------------------------------------|
|1|           1 |       1 |  0       (1) |  0        (1) |
|--------------------------------------------------------|
|2|         181 |     170 |  4       (3) |  4        (3) |
| |             |         |  3      (16) |  3       (18) |
| |             |         |  2      (46) |  2       (55) |
| |             |         |  1     (105) |  1      (105) |
|--------------------------------------------------------|
|3|      259272 |   92048 |  6       (2) |  6        (5) |
| |             |         |  5      (26) |  5      (229) |
| |             |         |  4    (1128) |  4    (14779) |
| |             |         |  3   (24240) |  3   (116554) |
| |             |         |  2   (66652) |  2   (127705) |
|--------------------------------------------------------|
|4|   119503486 | 2648603 |  8     (170) |  8    (25773) |
| |             |         |  7    (3086) |  7   (471085) |
| |             |         |  6   (35675) |  6  (4039393) |
| |             |         |  5  (303091) |  5 (25179318) |
| |             |         |  4 (1615858) |  4 (74731536) |
| |             |         |  3  (690723) |  3 (15056379) |
|--------------------------------------------------------|
|5| 10989384471 | 2648603 |  9      (57) |               |
| |             |         |  8    (4715) |               |
| |             |         |  7  (196534) |               |
| |             |         |  6 (2051399) |               |
| |             |         |  5  (395896) |               |
| |             |         |  4       (2) |               |
|--------------------------------------------------------|
|6|129688316236 |   92048 | 11      (27) |               |
| |             |         | 10     (514) |               |
| |             |         |  9   (51213) |               |
| |             |         |  8   (40262) |               |
| |             |         |  7      (32) |               |
|--------------------------------------------------------|
|7|           ? |     170 | 12     (124) |               |
| |             |         | 11      (46) |               |
|--------------------------------------------------------|
|8|           ? |       1 | 15       (1) |               |
|--------------------------------------------------------|
|9| 54727305380 |       1 | 17       (1) | 21        (4) |
| |             |         |              | 20        (?) |
| |             |         |              | 19        (?) |
| |             |         |              | 18        (?) |
| |             |         |              | 17        (?) |
----------------------------------------------------------

Note that:
- "Minimal clues to complete" is property of the template, not the rookery. They are matching up to some k.
- Clues to complete a k-rookery in the above table is only a rough approximation, based on evaluation of a single k-template from each rookery.

The 3-template list is small enough to be implemented as a lookup table. 4-template list is ~10GB uncompressed.
Calculating "on the fly" the minimal clues required to complete all 136 * (4-template + its complementary 5-template) takes about 3 seconds per grid for the first several hundreds grids in the Gordon's list.

Soon I'll be ready with some statistics on max(min(clues)) for (2+2+2+3) templates, (3+3+3) templates, and (4+5) templates for the 17's and 39's grid lists.

Only these two 4-templates are not completable to a valid sudoku grid. What they differ from all others?

Code: Select all

....12.34.134..2...423..1...21.34...3..1...424..2...13.34....211...234..2...413..
....12.34.134..2...423..1...21.43...3..1...424..2...13.34....211...243..2...314..

Cheers,
MD

Edit: added minimal clues for 4-templates
Edit March 11, 2017: Added the number of 5-templates
Edit March 14, 2017: Added the number of 6-templates
Edit July 22, 2019: Added 21-clue completable grids at the lower right corner of the table. See this.
Edit March 23, 2021: Changing number of 4-template classes from 119503485 to 119503486. Thanks to nazaz for pointing this out.

[dobrichev]

Distribution of 4-templates by minimal number of clues required to complete its 4-rookery.

Code: Select all

  #templ           Exemplar                                                                #clues
   25773 ....12.34.34...1.212.43......21...433....42.14.12.3....13...42..4..213..2..34..1. 8
  471085 ....12.34.34...1.212.43......234..1..4..213..3.1...42..1.2.4..32..1.3.4.4.3...2.1 7
 4039393 ..1..2.34..234.1..34...12...1..2.4.3.2.4.3.1.4.3.1..2..342....11...34..22..1..34. 6
25179318 ..1..2.34.3..142..24.3....1..24.3.1..14.2.3..3..1..4.2.2..3.14.1..24...34.3..1.2. 5
74731536 ..1..2.34.3..142..24.3....1..21.3.4..14.2.3..3..4..1.2.2..3.41.1..24...34.3..1.2. 4
15056379 ..1..2.34.3..142..4.23...1...423.1..12..4...33....142..1.4..3.2.43.2...12..1.3.4. 3

Somehow one of the templates disappeared. Will check it.

The results are added to the table from the previous post.

[dobrichev]

I think dukuso may well be right though.
In #4 and #6 they have the same minlex 2-rookery.Gsf has a slow minlex rookery function which works. in the case of #4 template a converse 7-template has 8 solutions - and there is 3 unavoidables [U4+U6+U8] in the #4 template. So i think both gsfs implementation and harvards are wrong !

I think gsf's implementation isn't wrong. The bug was found and it affects only puzzles with empty band, which is not the case when playing with rookeries/templates.
There are 181 2-templates and 170 2-rookeries. Matter of terminology.

See here

Interesting. Don't know whether/who/how can return qscgz to the scene.
Michael A. Deverin (a.k.a. holdout), the Master of the puzzle row-minlex canonicalization, is back on the scene, see here.

We will see if he is right with this one !

checking gordon's 17s, the minimum numbers of clues required to uniquely solve a 1,2,..,9 rookery are 0,1,2,3,5,7,10,13,17

We can see whether he is right or not, but working with complete lists of k-templates for k > 4 is unpractical, at least with the methods I am using and on home machines at the present time.

[coloin]

checking gordon's 17s, the minimum numbers of clues required to uniquely solve a 1,2,..,9 rookery are 0,1,2,3,5,7,10,13,17

hi dobrichev
your table suggests that the minimum numbers of clues required to uniquely solve a 1,2,..,9 rookery are 0,1,2,3,4,7.....17

Have you got a representative of the two 5-rookeries which needs only 4 clues ?

The 6-rookery case needing 7 clues
The 7-rookery case needing 10 clues
The 8-rookery case needing 13 clues

these have not really been proven as the limits of your work was reached ....

the 8-rookery case may well be the least fruitless ...... how may of these are there i wonder

Code: Select all

+---+---+---+
|1..|7..|...|
|...|16.|..4|
|.2.|...|16.|
+---+---+---+
|.1.|..2|...|
|...|.18|.3.|
|.7.|...|.1.|
+---+---+---+
|.61|...|7..|
|..3|..1|...|
|...|5..|..1|
+---+---+---+


C

[dobrichev]

The number of ED 5-templates is 10,989,384,471.
The above table is updated accordingly.

When generating all ED grid by joining a 4-rookery A and the corresponding 5-rookery B, only about 10% of A is sufficient to process.
The A survival criterion is reduction of templates in B dictated by avoidance of joining A + X + T1 once, and X + A + T1 as duplicate, where X is another 4-rookery having larger canonical representation and T1 is some 1-template. When the templates in B are reduced to an empty set, then A is safe to eliminate.
For survived A the corresponding templates from B are reduced by various amount.
When X has the same canonical representation as A, further similar comparison at template level must be done for entire removal of the duplicates. This again can be done independently for each fixed A, and doesn't require much RAM for temporary cache. Typically A consists of <100 ED 4-templates and B of several thousands ED 5-templates before any reduction.

[coloin]

dobrichev did provide me with the 2 5-rookeries which completed with only 4 clues

Code: Select all

8695..7..5..76..98.7..895.695.6.7.8.7.68..9.5..8.9567.6..95.8.7.95.78.6..87..6.59
8796..5..6..75.89..5..89.679.75..6.8.6.9.8.75.85.679..5...9678.7.68...59.98.75..6

these are 4 for one of these and 3 for the other = 7 ways
from those 5-rookeries there are only a few different ways each to fill the empty rookery/template with a 4-rookery/template [?]

there were 75 puzzles found with a {999911110} clue freq distribution

Code: Select all

8695..7..5..76..98.7..895.695.6.7.8.7.68..9.5..8.9567.6..95.8.7.95.78.6..87..6.59
...513.24.12.643..3742...1...3.2.481.2..41.3.14.3....2.31..2.4.4..1..2.32..43.1..
...514.23.12.634..3742...1...3.2.184.2..41.3.14.3....2.31..2.4.2..4..3.14..13.2..
...514.23.12.634..3742...1...3.4.182.4..21.3.12.3....4.31..2.4.2..4..3.14..13.2..
...514.23.12.634..3742...1...3.4.281.4..21.3.12.3....4.31..2.4.4..1..3.22..43.1..
...514.32.12.634..3742...1...3.2.184.4..31.2.12.4....3.31..2.4.4..3..2.12..14.3..
...523.14.12.643..3741...2...1.3.482.4..12.3.23.4....1.23..1.4.4..2..1.31..34.2..
...524.13.12.634..3741...2...1.3.284.4..12.3.23.4....1.23..1.4.4..3..1.21..24.3..
...541.23.12.634..3742...1...3.2.184.2..14.3.14.3....2.31..2.4.2..4..3.14..13.2..

....13524612.743..3.42...1...3.2.481.2..41.3.14.3....2.31..2.4.2..4..1.34..13.2..
....13524612.743..3.42...1...3.2.481.2..41.3.14.3....2.31..2.4.4..1..2.32..43.1..
....14523612.734..3.42...1...3.2.184.2..41.3.14.3....2.31..2.4.2..4..3.14..13.2..
....14523612.734..3.42...1...3.4.182.4..21.3.12.3....4.31..2.4.2..4..3.14..13.2..
....14523612.734..3.42...1...3.4.281.4..21.3.12.3....4.31..2.4.4..1..3.22..43.1..
....14532612.734..3.42...1...3.2.184.4..31.2.12.4....3.31..2.4.4..3..2.12..14.3..
....23514612.743..3.41...2...1.3.482.4..12.3.23.4....1.23..1.4.4..2..1.31..34.2..
....24513612.734..3.41...2...1.3.284.4..12.3.23.4....1.23..1.4.4..3..1.21..24.3..
....41523612.734..3.42...1...3.2.184.2..14.3.14.3....2.31..2.4.2..4..3.14..13.2..

....13.24.125.43..3.42..617..3.2.481.2..41.3.14.3....2.31..2.4.2..4..1.34..13.2..
....13.24.125.43..3.42..617..3.2.481.2..41.3.14.3....2.31..2.4.4..1..2.32..43.1..
....14.23.125.34..3.42..617..3.2.184.2..41.3.14.3....2.31..2.4.2..4..3.14..13.2..
....14.23.125.34..3.42..617..3.4.182.4..21.3.12.3....4.31..2.4.2..4..3.14..13.2..
....14.23.125.34..3.42..617..3.4.281.4..21.3.12.3....4.31..2.4.4..1..3.22..43.1..
....14.32.125.34..3.42..617..3.2.184.4..31.2.12.4....3.31..2.4.4..3..2.12..14.3..
....23.14.125.43..3.41..627..1.3.482.4..12.3.23.4....1.23..1.4.4..2..1.31..34.2..
....24.13.125.34..3.41..627..1.3.284.4..12.3.23.4....1.23..1.4.4..3..1.21..24.3..
....41.23.125.34..3.42..617..3.2.184.2..14.3.14.3....2.31..2.4.2..4..3.14..13.2..

...513.24.126.4..33742..1...3..42.1.2.1.384..4..1...32.234....1.4..213..1..3..24.
...513.42.126.4..33742..1...3..42.1.4.1.382..2..1...34.234....1.4..213..1..3..42.
...514.23.126.3..43742..1...3..42.1.2.1.384..4..1...32.234....1.4..213..1..3..24.
...514.32.126.3..43742..1...3..42.1.2.1.384..4..1...23.234....1.4..213..1..3..24.
...514.32.126.3..43742..1...3..42.1.4.1.382..2..1...43.234....1.4..213..1..3..42.
...523.41.126.4..33741..2...4..12.3.2.3.481..1..3...24.314....2.2..314..4..2..31.
...523.41.126.4..33741..2...4..32.1.2.3.184..1..4...32.312....4.2..413..4..3..12.
...532.41.126.4..33741..2...4..21.3.2.3.481..1..3...24.314....2.2..134..4..2..31.
...532.41.126.4..33741..2...4..23.1.2.3.184..1..4...32.312....4.2..413..4..3..12.
...541.23.126.3..43742..1...3..24.1.2.1.384..4..1...32.234....1.4..123..1..3..24.
...541.32.126.3..43742..1...3..24.1.2.1.384..4..1...23.234....1.4..123..1..3..24.
...541.32.126.3..43742..1...3..24.1.4.1.382..2..1...43.234....1.4..123..1..3..42.


8796..5..6..75.89..5..89.679.75..6.8.6.9.8.75.85.679..5...9678.7.68...59.98.75..6
....135246127.4..33.42..1...3..42.1.2.1.384..4..1...32.234....1.4..213..1..3..24.
....135426127.4..33.42..1...3..42.1.4.1.382..2..1...34.234....1.4..213..1..3..42.
....145236127.3..43.42..1...3..42.1.2.1.384..4..1...32.234....1.4..213..1..3..24.
....145326127.3..43.42..1...3..42.1.2.1.384..4..1...23.234....1.4..213..1..3..24.
....145326127.3..43.42..1...3..42.1.4.1.382..2..1...43.234....1.4..213..1..3..42.
....235416127.4..33.41..2...4..12.3.2.3.481..1..3...24.314....2.2..314..4..2..31.
....235416127.4..33.41..2...4..32.1.2.3.184..1..4...32.312....4.2..413..4..3..12.
....325416127.4..33.41..2...4..21.3.2.3.481..1..3...24.314....2.2..134..4..2..31.
....325416127.4..33.41..2...4..23.1.2.3.184..1..4...32.312....4.2..413..4..3..12.
....415236127.3..43.42..1...3..24.1.2.1.384..4..1...32.234....1.4..123..1..3..24.
....415326127.3..43.42..1...3..24.1.2.1.384..4..1...23.234....1.4..123..1..3..24.
....415326127.3..43.42..1...3..24.1.4.1.382..2..1...43.234....1.4..123..1..3..42.

....13.24.12.54..33.42..167.3..42.1.2.1.384..4..1...32.234....1.4..213..1..3..24.
....13.42.12.54..33.42..167.3..42.1.4.1.382..2..1...34.234....1.4..213..1..3..42.
....14.23.12.53..43.42..167.3..42.1.2.1.384..4..1...32.234....1.4..213..1..3..24.
....14.32.12.53..43.42..167.3..42.1.2.1.384..4..1...23.234....1.4..213..1..3..24.
....14.32.12.53..43.42..167.3..42.1.4.1.382..2..1...43.234....1.4..213..1..3..42.
....23.41.12.54..33.41..267.4..12.3.2.3.481..1..3...24.314....2.2..314..4..2..31.
....23.41.12.54..33.41..267.4..32.1.2.3.184..1..4...32.312....4.2..413..4..3..12.
....32.41.12.54..33.41..267.4..21.3.2.3.481..1..3...24.314....2.2..134..4..2..31.
....32.41.12.54..33.41..267.4..23.1.2.3.184..1..4...32.312....4.2..413..4..3..12.
....41.23.12.53..43.42..167.3..24.1.2.1.384..4..1...32.234....1.4..123..1..3..24.
....41.32.12.53..43.42..167.3..24.1.2.1.384..4..1...23.234....1.4..123..1..3..24.
....41.32.12.53..43.42..167.3..24.1.4.1.382..2..1...43.234....1.4..123..1..3..42.

....13.24.12..4..33542..1...3..42.1.2.1.3.4..4..167.32.234....1.4.8213..1..3..24.
....13.42.12..4..33542..1...3..42.1.4.1.3.2..2..167.34.234....1.4.8213..1..3..42.
....14.23.12..3..43542..1...3..42.1.2.1.3.4..4..167.32.234....1.4.8213..1..3..24.
....14.32.12..3..43542..1...3..42.1.2.1.3.4..4..167.23.234....1.4.8213..1..3..24.
....14.32.12..3..43542..1...3..42.1.4.1.3.2..2..167.43.234....1.4.8213..1..3..42.
....23.41.12..4..33541..2...4..12.3.2.3.4.1..1..367.24.314....2.2.8314..4..2..31.
....23.41.12..4..33541..2...4..32.1.2.3.1.4..1..467.32.312....4.2.8413..4..3..12.
....32.41.12..4..33541..2...4..21.3.2.3.4.1..1..367.24.314....2.2.8134..4..2..31.
....32.41.12..4..33541..2...4..23.1.2.3.1.4..1..467.32.312....4.2.8413..4..3..12.
....41.23.12..3..43542..1...3..24.1.2.1.3.4..4..167.32.234....1.4.8123..1..3..24.
....41.32.12..3..43542..1...3..24.1.2.1.3.4..4..167.23.234....1.4.8123..1..3..24.
....41.32.12..3..43542..1...3..24.1.4.1.3.2..2..167.43.234....1.4.8123..1..3..42.

removing clues from all these - i did not find a 999211110 clue distribution - which is in keeping with his findings that 7 clues are needed for a 6-rookery

C

[dobrichev]

A (naive) search for more valid puzzles with digit distribution 999911110 resulted in none found after processing ~20 millions 5-templates.

Then I took all 4-rookeris completable to < 2000 5-templates (i.e. essentially different (ED) permutations of the rest 5 digits), and found 327921.
I sorted them by the number of solutions (i.e. all valid permutations of the rest 5 digits). Argument was that low-clue completion is correlated closer to the number of all solutions than to number of ED solutions.
Keeping the order, I expanded the respective ED 5-templates, resulting in 530,281,861 5-templates.
After processing about 14 millions of them, 1086 5-templates completable with 11110 clues appeared.
Rearrangement of their 9999 part (the 4-rookery) in all possible ED ways expands them to 9956 ED 999911110 puzzles.
None of them can be reduced to a valid 999211110 puzzle.

After 160 hours, the generation still continues, with decreasing rate of findings. It is impossible to do exhaustive search using this method and soon or later I will stop the generation.

Essentially this exercise expands the above search by Coloin from 2/75 puzzles to 1086/9956 puzzles.

If some is interested in these partial results I can publish the puzzles.