The New Sudoku Players' Forum

[dobrichev]

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

[Serg]

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

[dobrichev]

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]

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

123456789456789123798132564267345918534918276981267435375691842619824357842573691
1......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.8

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