## Minimal clues to complete a grid examining k-templates

Everything about Sudoku that doesn't fit in one of the other sections

### Minimal clues to complete a grid examining k-templates

Each Sudoku Solution Grid can be represented as union of 9 1-templates, where each 1-template is the set of the 9 cells occupied by the same digit.

Each unordered pair of 1-templates forms a 2-template. There are 36 of them: (1,2), (1,3) ... (1,9), (2,3) ... (8,9).
Each unordered triplet of 1-templates forms a 3-template. There are 84 of them: (1,2,3) ... (7,8,9).
Each unordered quartet of 1-templates forms a 4-template. There are 126 of them: (1,2,3,4) ... (6,7,8,9).

The complementary cells of each 4-template form a 5-template.
The complementary cells of each 3, 2, and 1-template form respectively a 6, 7, and 8-template.

The grid itself is a 9-template. For completeness.

The grid can be represented also by union of three 2-templates plus one 3-template. There are 1260 choices to do this, one of them is [(1,2), (3,4), (5,6), (7, 8, 9)].
The grid can be represented as union of three 3-templates. There are 280 ways to do this, one of them is [(1, 2, 3), (4, 5, 6), (7, 8, 9).

Each k-template requires a minimum number of clues to be completed. Imagine a grid, where all cells except these from the template are known. The minimum number of the givens, along with their exact position, could be preprocessed. See this table for some details.

Inspecting all possible combinations for 2+2+2+3, 3+3+3, and 4+5 templates for a fixed grid, and taking the worst one (that requires maximum number of clues to complete the respective combination of k-templates) gives a lower limit of clues, required to complete the whole grid. It is sufficient to sum the minimum clues for each of the templates within the combination, looping over all template combinations.

This was done for the grids with 17-clue and 39-clue puzzles.
In addition, the minimal and average clues for each of the methods are calculated.

Hidden Text: Show
Code: Select all
`Grids having 17-clue puzzles----------------------------Some of the extreme grids                                                          Min2223 Max2223 Avg2223  Min333  Max333 Avg333  Min45   Max45 Avg45 Puzzles123456789456789123789123465234617958597348612861295374348571296675932841912864537        5      13   7.262       6      15 8.036       8     14 10.77      1123456789456789123789123465234915678567348912891672354348261597672594831915837246        5      12   6.357       6      15 7.071       8     13 10.12      1123456789456789123789123564234975618567318942891642375378291456642537891915864237        5      13   6.536       6      15 7.357       8     13 10.40      1123456789456789123789132465217594638635821974948367251394675812571248396862913547        5      14   7.298       6      15 8.143       9     14 10.89      1123456789456789123798132564267345918534918276981267435375691842619824357842573691        5       9   5.524       6       8 6.321       8     11  9.32      1123456789456789123798231645265943871871625934934178562319864257582317496647592318        5       8   5.738       6       8 6.714       8     10  9.59      1123456789456789123798231645275148936639527418814963257347892561561374892982615374        5       6   5.095       6       8 6.286       8     10  9.12      3123456789456789132789132564271564893635897421948213675314978256567321948892645317        5      13   6.893       6      15 7.679       8     13 10.44      1123456789456789132789231546295374861347618295618592374531967428862143957974825613        5       8   5.917       6       8 6.750       8     11  9.63      1123456789457189236689327514215694378746835192938271465392748651571962843864513927        5      15   7.940       6      13 8.821       8     15 11.61      1123456789457189236698237541261394857584671923739528164315762498876945312942813675        6      12   7.738       7      11 8.464       9     13 10.58      1123456789457189236698723145249618357316275498785394612564937821872541963931862574        5      15   7.869       6      12 8.607       8     16 11.39      1123456789457189263689327541216594378394278615578613492745831926862945137931762854        5      13   8.345       6      13 9.036       9     13 11.16      1... rest grids with 17s ...============================================================================================================================================================Min                                                                                      5       6   5.095       6       8 6.286       8     10  9.12      1Max                                                                                      6      15   8.345       7      15 9.036      10     16 11.61     29Average                                                                              5.000  10.862   6.782   6.000  10.485 7.552   8.292 12.166 10.18  1.062Grids having 39-clue puzzles----------------------------Min                                                                                      5       9   6.393       6       9 7.214       8     11  9.98Max                                                                                      5      15   8.250       6      13 9.000       9     16 11.61Average                                                                                  5  12.074   7.360       6  11.254 8.093   8.576 13.093 10.68`

For 17s, the SFB grid holds all records for minimums.

Interesting phenomena for the 17s is that the average over all grids for method Max2223 (10.862) is higher than average for method Max333 (10.485). This suggests lack of 2-digit UA sets. Maybe the fully-entwined pairs approach isn't worthless?

MD
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Minimal clues to complete a grid examining k-templates

Hi, dobrichev!
You posted very interesting experimental data, as usual.

You divide solution grid by parts considering complementary n-templates (for example, it is possible to divide a solution grid by 2 parts considering its 4-template and complementary 5-template). We can see from your data that it is sufficient 5 clues only to hit all unavoidables for each complementary k-template in 2+2+2+3 templates combinations. But besides UA sets beloning as a whole to one of complementary k-templates there are "cross-template" UA sets which were not accounted by your investigation. If we would account all "cross-template" UA sets, we could get 17-clue minimum grid subset (a puzzle) hitting all UA sets of the grid. The higher "k" in k-template, more precise estimate for minimal number of clues being necessary a puzzle can have unique solution we can get.

Serg
Serg
2018 Supporter

Posts: 785
Joined: 01 June 2010
Location: Russia

### Does it matter?

This 5-template has 11 ED solutions, and 6 of them can be defined by 17 clues in 49 different ways.
Code: Select all
`....12345.1345..2.245..31....1.254.33.41..25.52..34..1..25.1.3413.24.5..45.3...12678912345913456728245783169761825493384197256529634871892571634136249587457368912  0678912345913456728245873196891725463364189257527634981782591634136248579459367812  6678912345913456827245783169761825493384197256529634781892571634136249578457368912  0678912345913456827245783169781625493364197258529834671892561734137249586456378912  5678912345913456827245783169891625473364179258527834691782561934139247586456398712 20678912345913456827245783196891625473364179258527834961782591634136247589459368712  6678912345913457628245683179761825493384196257529734861892561734137249586456378912  0678912345913457628245683179791825463384169257526734981862591734137248596459376812  0678912345913457628245683179791825463384196257526734891862571934137249586459368712  7678912345913457826245683179761825493384196257529734681892561734137249568456378912  0678912345913457826245683179791825463384169257526734981862591734137246598459378612  5`

So, this 5-template, coupled to all 11 4-templates from its complementary 4-rookery, gives high density of 17-clue solvable grids (6/11).

In contrast, from all 2723 5-templates of this 5-rookery, only this 5-template is capable to generate grids solvable with 17 clues (1/2723).

Cheers,
MD
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Minimal clues to complete a grid examining k-templates

In continuation of the table in the initial post, all grids were processed for 3+3+3 method.
Each solution grid was split to 3 partitions, each containing 3 different values. This is done in all possible ways. The maximal sum of clues required to resolve all 3 27-cell partitions (each independently from the other 2) was calculated. These are the results.
(Compare to this result by Blue for splitting grids to 3 bands.)
Code: Select all
`|MC3T|grids     |17CG |17CG/grids|17CP |17CP/grids|17CP/17CG|+-----------------------------------------------------------+|   6|          |     |          |     |          |         ||   7|          |     |          |     |          |         ||   8|      2826|    4|0.1415428%|    6|0.2123142%|  1.50000||   9|  75838126| 4901|0.0064624%| 5320|0.0070149%|  1.08549||  10| 870139488|19187|0.0022050%|20438|0.0023488%|  1.06520||  11|2522652319|17559|0.0006961%|18539|0.0007349%|  1.05581||  12|1682829554| 4182|0.0002485%| 4373|0.0002599%|  1.04567||  13| 291188927|  429|0.0001473%|  442|0.0001518%|  1.03030||  14|  25155656|   33|0.0001312%|   34|0.0001352%|  1.03030||  15|   4636997|    5|0.0001078%|    5|0.0001078%|  1.00000||  16|    267033|     |          |     |          |         ||  17|     13660|     |          |     |          |         ||  18|      5952|     |          |     |          |         |+-----------------------------------------------------------+|    |5472730538|46300|          |49157|          |         |`

For the grids requiring 8 clues, from the 4 grids having 17-clue puzzles, one has 3.
The grids and their puzzles follow.
Code: Select all
`1234567894567891237981325642673459185349182769812674353756918426198243578425736911......8...67....3............34.......9.8.....1.....5...6.1..2.........84.....9.123456789456789123798231645265943871871625934934178562319864257582317496647592318..34.6..........2...82.....26.....7..7..........1..5................74......9.3.8123456789456789123798231645275148936639527418814963257347892561561374892982615374....56......7......98....4.2.5.....66...........9....734...2.........89..............56......7......98....4.2.5.....66...........9.....34...2.....1...89..........1...56.............98....4.2.5.....66...........9.....34...2.........89........7.123456789456789132789231546295374861347618295618592374531967428862143957974825613..34.........8...2..9......2...7.....4.....9....5..3.....9..4..86......7....2....`

Edit: fixed link to Blue's result.
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010