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

Postby dobrichev » Sun Aug 07, 2011 7:43 pm

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 Puzzles
123456789456789123789123465234617958597348612861295374348571296675932841912864537        5      13   7.262       6      15 8.036       8     14 10.77      1
123456789456789123789123465234915678567348912891672354348261597672594831915837246        5      12   6.357       6      15 7.071       8     13 10.12      1
123456789456789123789123564234975618567318942891642375378291456642537891915864237        5      13   6.536       6      15 7.357       8     13 10.40      1
123456789456789123789132465217594638635821974948367251394675812571248396862913547        5      14   7.298       6      15 8.143       9     14 10.89      1
123456789456789123798132564267345918534918276981267435375691842619824357842573691        5       9   5.524       6       8 6.321       8     11  9.32      1
123456789456789123798231645265943871871625934934178562319864257582317496647592318        5       8   5.738       6       8 6.714       8     10  9.59      1
123456789456789123798231645275148936639527418814963257347892561561374892982615374        5       6   5.095       6       8 6.286       8     10  9.12      3
123456789456789132789132564271564893635897421948213675314978256567321948892645317        5      13   6.893       6      15 7.679       8     13 10.44      1
123456789456789132789231546295374861347618295618592374531967428862143957974825613        5       8   5.917       6       8 6.750       8     11  9.63      1
123456789457189236689327514215694378746835192938271465392748651571962843864513927        5      15   7.940       6      13 8.821       8     15 11.61      1
123456789457189236698237541261394857584671923739528164315762498876945312942813675        6      12   7.738       7      11 8.464       9     13 10.58      1
123456789457189236698723145249618357316275498785394612564937821872541963931862574        5      15   7.869       6      12 8.607       8     16 11.39      1
123456789457189263689327541216594378394278615578613492745831926862945137931762854        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      1
Max                                                                                      6      15   8.345       7      15 9.036      10     16 11.61     29
Average                                                                              5.000  10.862   6.782   6.000  10.485 7.552   8.292 12.166 10.18  1.062

Grids having 39-clue puzzles
----------------------------
Min                                                                                      5       9   6.393       6       9 7.214       8     11  9.98
Max                                                                                      5      15   8.250       6      13 9.000       9     16 11.61
Average                                                                                  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: 1311
Joined: 24 May 2010

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

Postby Serg » Tue Aug 09, 2011 4:08 pm

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.

Your approach is interesting.

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Does it matter?

Postby dobrichev » Wed Aug 31, 2011 9:38 pm

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...12

678912345913456728245783169761825493384197256529634871892571634136249587457368912  0
678912345913456728245873196891725463364189257527634981782591634136248579459367812  6
678912345913456827245783169761825493384197256529634781892571634136249578457368912  0
678912345913456827245783169781625493364197258529834671892561734137249586456378912  5
678912345913456827245783169891625473364179258527834691782561934139247586456398712 20
678912345913456827245783196891625473364179258527834961782591634136247589459368712  6
678912345913457628245683179761825493384196257529734861892561734137249586456378912  0
678912345913457628245683179791825463384169257526734981862591734137248596459376812  0
678912345913457628245683179791825463384196257526734891862571934137249586459368712  7
678912345913457826245683179761825493384196257529734681892561734137249568456378912  0
678912345913457826245683179791825463384169257526734981862591734137246598459378612  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: 1311
Joined: 24 May 2010


Return to General