The New Sudoku Players' Forum

[m_b_metcalf]

An obvious 25*25 is like this:
[snip]
just like the minimal grid in Latin Squares. It has 156 givens.

Very nice. Here's a more readable version:

Code: Select all

  1  2  3  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .
  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18
  2  3  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17
  3  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17 16
  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20
  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17 16 15
  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19
  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17 16 15 14

[hkociemba1]

qiuyanzhe's method is really a great improvement compared to what I did. Very nice. An adaption to the default grid I use now also gives Floor(N^2/4) clues, here the cases N=16 and N=25.

Code: Select all

 +-------------+-------------+-------------+-------------+
 |  1  2  3  4 |  5  6  7  . |  .  .  .  . |  .  .  .  . |
 |  5  6  7  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  8 |
 |  .  .  .  . |  .  .  .  . |  .  .  .  8 |  9 10 11 12 |
 +-------------+-------------+-------------+-------------+
 |  2  3  4  5 |  6  7  .  . |  .  .  .  . |  .  .  .  . |
 |  6  7  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  8  9 |
 |  .  .  .  . |  .  .  .  . |  .  .  8  9 | 10 11 12 13 |
 +-------------+-------------+-------------+-------------+
 |  3  4  5  6 |  7  .  .  . |  .  .  .  . |  .  .  .  . |
 |  7  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  8  9 10 |
 |  .  .  .  . |  .  .  .  . |  .  8  9 10 | 11 12 13 14 |
 +-------------+-------------+-------------+-------------+
 |  4  5  6  7 |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  8  9 10 11 |
 |  .  .  .  . |  .  .  .  . |  8  9 10 11 | 12 13 14 15 |
 +-------------+-------------+-------------+-------------+
64 givens, 1706 candidates(pencilmarks).

+----------------+----------------+----------------+----------------+----------------+
 |  1  2  3  4  5 |  6  7  8  9 10 | 11 12  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  6  7  8  9 10 | 11 12  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 | 11 12  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  . 13 14 15 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  . 13 14 15 | 16 17 18 19 20 |
 +----------------+----------------+----------------+----------------+----------------+
 |  2  3  4  5  6 |  7  8  9 10 11 | 12  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  7  8  9 10 11 | 12  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 | 12  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  . 13 14 15 16 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  . 13 14 15 16 | 17 18 19 20 21 |
 +----------------+----------------+----------------+----------------+----------------+
 |  3  4  5  6  7 |  8  9 10 11 12 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  8  9 10 11 12 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . | 13 14 15 16 17 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . | 13 14 15 16 17 | 18 19 20 21 22 |
 +----------------+----------------+----------------+----------------+----------------+
 |  4  5  6  7  8 |  9 10 11 12  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  9 10 11 12  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  . 13 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  . 13 | 14 15 16 17 18 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  . 13 | 14 15 16 17 18 | 19 20 21 22 23 |
 +----------------+----------------+----------------+----------------+----------------+
 |  5  6  7  8  9 | 10 11 12  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 | 10 11 12  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  . 13 14 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  . 13 14 | 15 16 17 18 19 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  . 13 14 | 15 16 17 18 19 | 20 21 22 23 24 |
 +----------------+----------------+----------------+----------------+----------------+
156 givens, 6567 candidates(pencilmarks).

The method even works for rectangular boxes, here a 3x4 and 5x3 box. The number of clues for NxM boxes is Floor(N^2*M^2/4)

Code: Select all

 +-------------+-------------+-------------+
 |  1  2  3  4 |  5  .  .  . |  .  .  .  . |
 |  5  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  6  7  8 |
 +-------------+-------------+-------------+
 |  2  3  4  5 |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  6  7  8  9 |
 +-------------+-------------+-------------+
 |  3  4  5  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  6 |
 |  .  .  .  . |  .  .  .  6 |  7  8  9 10 |
 +-------------+-------------+-------------+
 |  4  5  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  6  7 |
 |  .  .  .  . |  .  .  6  7 |  8  9 10 11 |
 +-------------+-------------+-------------+
36 givens, 710 candidates(pencilmarks).

 +----------+----------+----------+----------+----------+
 |  1  2  3 |  4  5  6 |  7  .  . |  .  .  . |  .  .  . |
 |  4  5  6 |  7  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  7  .  . |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  .  8  9 |
 |  .  .  . |  .  .  . |  .  .  . |  .  8  9 | 10 11 12 |
 +----------+----------+----------+----------+----------+
 |  2  3  4 |  5  6  7 |  .  .  . |  .  .  . |  .  .  . |
 |  5  6  7 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  8  9 10 |
 |  .  .  . |  .  .  . |  .  .  . |  8  9 10 | 11 12 13 |
 +----------+----------+----------+----------+----------+
 |  3  4  5 |  6  7  . |  .  .  . |  .  .  . |  .  .  . |
 |  6  7  . |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  .  .  8 |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  8 |  9 10 11 |
 |  .  .  . |  .  .  . |  .  .  8 |  9 10 11 | 12 13 14 |
 +----------+----------+----------+----------+----------+
56 givens, 1427 candidates(pencilmarks).


It seems that you can solve all these grids by either naked singles or also by hidden singles only.

[ton]

20x20(4x5), 91-clue
I think minimum number is 88.

Code: Select all

+---------------+---------------+---------------+---------------+
|  .  .  .  .  .|  .  .  .  .  .|  .  6  .  .  .|  .  .  .  .  .|
|  9  .  .  .  .|  . 18  .  .  .|  3  2  . 14  .|  .  .  .  1  .|
|  . 11  .  .  .|  .  8  .  .  .|  .  .  .  .  .| 13  .  .  .  .|
|  . 13  .  . 15|  . 10  . 11  .|  .  .  .  . 16|  . 19  .  .  .|
+---------------+---------------+---------------+---------------+
|  .  .  6  . 12|  .  .  .  .  .|  .  .  7  .  .|  .  .  1  2  .|
|  .  .  .  .  .|  .  .  .  .  .|  .  .  .  .  8|  .  .  .  .  .|
|  2  .  1  .  .|  .  .  5  .  .|  .  .  .  .  .|  .  .  9  3  6|
|  . 19  .  .  .|  . 16  . 10  .|  .  .  .  . 11|  .  .  .  .  .|
+---------------+---------------+---------------+---------------+
|  . 15  . 10 11|  . 13  . 16  .|  .  5  .  . 19|  .  .  .  .  .|
|  . 16  .  .  8|  . 11  .  .  .|  .  .  .  .  .|  .  .  . 20  .|
|  .  .  .  . 19|  .  .  .  .  .|  2  9  .  .  .|  .  .  .  6  1|
|  .  .  .  .  .|  .  .  3  .  .|  6 20  .  1  .| 17  .  2  9 14|
+---------------+---------------+---------------+---------------+
|  .  .  .  7  .|  .  .  .  . 20|  .  .  .  .  .| 10  .  .  .  .|
| 17  .  2  .  .|  9  .  6  .  3|  .  .  .  .  .|  .  .  .  .  .|
|  .  .  .  . 10|  .  .  .  .  .|  .  .  8  . 13| 11 16  .  . 15|
|  .  .  .  .  .|  .  . 14  .  2|  .  .  .  .  .|  .  .  .  .  .|
+---------------+---------------+---------------+---------------+
|  .  .  .  .  .|  .  .  .  .  .|  .  .  .  .  .|  8 13  .  .  .|
|  .  8  .  . 13|  .  .  .  .  .|  .  .  .  .  .| 15 10  . 18 11|
| 14  . 20  .  .|  1  .  2  4  6|  9  3  .  .  .|  .  .  .  .  .|
|  .  .  .  .  .|  .  .  9  .  .|  . 14  .  .  .| 16  .  .  .  .|
+---------------+---------------+---------------+---------------+


25x25(5x5), 146-clue
I think minimum number is 140.

Code: Select all

+---------------+---------------+---------------+---------------+---------------+
|  . 12  .  .  .|  .  .  .  .  .|  .  .  .  9  .|  .  . 15  .  .| 22  .  .  .  .|
|  .  .  .  .  .|  .  9  . 19  .|  .  . 10 11  .|  .  .  .  .  .|  .  .  .  .  .|
|  .  4  . 22  .|  .  .  .  .  .|  .  .  .  .  .|  .  . 12  .  .| 20 15  1  .  .|
| 16  1 20 15  .|  .  .  .  .  .|  .  .  .  .  .| 14  .  4  . 22| 12 25  .  .  .|
|  .  .  .  .  .|  .  7  2 11  .| 23  . 19  8  .|  .  .  . 13  .|  .  .  .  .  .|
+---------------+---------------+---------------+---------------+---------------+
| 13  .  8  .  2|  .  .  .  .  .|  .  .  7 23  6|  .  9  . 19 11|  .  .  .  .  .|
|  .  .  .  . 23|  .  .  .  . 16|  .  .  .  .  .|  .  .  .  .  .|  1  .  .  .  .|
|  7  .  .  . 10|  3  .  .  .  .|  .  .  9 19  .|  . 13  . 23  .|  .  .  .  5  .|
|  .  .  .  .  .| 15  .  .  . 22|  .  .  .  .  .|  .  .  .  .  .| 25 20  .  .  .|
|  .  .  .  .  .| 12  . 14  1 25|  .  .  .  .  .|  .  .  3  .  .| 16  4 15  .  .|
+---------------+---------------+---------------+---------------+---------------+
|  .  .  .  .  .|  . 19  9  .  .|  .  . 13  7  .|  .  .  .  5  .|  .  .  . 23 10|
|  . 22  . 25 17|  .  .  .  .  .|  .  .  .  .  .| 12  . 20  .  .|  .  .  .  .  .|
|  . 20 12 16  .|  .  .  .  .  .|  .  .  .  . 14| 15 22  1  . 25|  .  .  .  .  .|
|  . 15  .  .  .|  . 11  .  .  .|  .  .  .  .  .|  .  . 16  .  .|  .  .  .  9  .|
|  .  .  .  1  .|  . 10  . 23  .|  .  .  .  . 18|  .  .  .  .  .|  .  .  .  .  8|
+---------------+---------------+---------------+---------------+---------------+
| 10  .  .  .  8|  . 13  .  5  .|  .  .  .  .  .|  . 19  . 11 23|  .  .  .  6  .|
|  .  .  . 17  7|  .  .  .  .  .|  .  .  .  .  1|  .  .  .  .  .|  4 22  .  .  .|
|  .  .  .  . 11|  . 23  .  .  .|  .  .  .  . 20|  .  .  .  2  .| 14  .  .  .  .|
| 19  . 23  .  5|  .  8  .  9  .|  . 21  .  .  .|  . 10  .  7  .|  .  .  .  .  .|
|  .  3  .  .  .|  .  .  .  .  .| 25  4  .  . 12|  .  .  .  .  .| 15  1 16  .  .|
+---------------+---------------+---------------+---------------+---------------+
|  .  .  .  .  .|  .  .  .  . 15|  . 12  .  . 25|  1  . 22  .  .|  3  .  .  .  .|
| 23  .  .  . 19|  .  2  .  .  .|  .  .  .  .  .|  .  .  . 10  .|  .  .  .  7 11|
|  .  .  . 18  .|  .  .  .  .  .|  . 20  .  .  .|  .  .  .  .  .|  .  .  .  .  .|
|  .  .  .  .  .|  .  .  .  .  4| 14 15  .  . 22|  .  .  .  .  .|  .  .  . 10  .|
| 11  .  .  .  9|  .  .  .  .  .|  .  .  .  .  .|  .  .  .  .  .|  .  .  . 19  .|
+---------------+---------------+---------------+---------------+---------------+


[hkociemba1]

I think minimum number is 88.
I think minimum number is 140.

Do you have any arguments for this assumption?

[coloin]

maybe the assumption is the extrapolation of known minima

im just trying to work out why qiuyanzhe's method is superior to hkociemba's.
Looking at it the canonical clues seem to be influencing across and down ...

however i don't see a 9x9 puzzle treated this way - [ maybe its obvious !]

Code: Select all

+----------+----------+----------+
|  1  2  3 |  4  .  . |  .  .  . |
|  4  .  . |  .  .  . |  .  .  . |
|  .  .  . |  .  .  . |  .  5  6 |
+----------+----------+----------+
|  2  3  4 |  .  .  . |  .  .  . |
|  .  .  . |  .  .  . |  .  .  . |
|  .  .  . |  .  .  . |  5  6  7 |
+----------+----------+----------+
|  3  4  . |  .  .  . |  .  .  . |
|  .  .  . |  .  .  . |  .  .  5 |
|  .  .  . |  .  .  5 |  6  7  8 |
+----------+----------+----------+  20 clues valid

Perhaps this is where we are in the thread .....

Code: Select all

puzzle         hkociemba      qiuyanzhe      actual smallest puzzle found to date
9x9[3x3]        21 clues       20 clues      17 clues   
16x16[4x4]      86 clues       64 clues      55
25x25[5x5]     185 clues      156 clues      146 
........

12x12[2x6]                     36            32
12x12[3x4]                     36            30
15x15[3x5]                     56            48
20x20[4x5]                     100           91 

100x100 [10x10]                2500   

[Mathimagics]

Perhaps it is interesting to look at the known LNC (least # of clues for a valid puzzle) as a proportion of grid size:

Code: Select all

Box  Grid   LNC   LNC/Grid
--------------------------
3x3    81    17    0.2099
3x4   144    30    0.2083
3x5   225    48    0.2133
4x4   256    55    0.2148
4x5   400    91    0.2275
4x6   576   133?   0.2309  (guess only)
5x5   625   146    0.2336


The 4x6 entry is an interpolated prediction only, as nobody seems to have actually considered this case.

The overall trend seems to suggest that we are getting quite close to the minimum possible clue counts in most cases, but of course the tantalising fact remains that we simply don't know what these absolute minimums really are, other than the 3x3 case (and we know how hard getting that result was).

Rows need to be added (5x6, 6x6, etc), and at least 2 more columns also need to be added, IMO:

• LNCS: least # of clues for a strong puzzle (minimal, singles only)

• GNC: greatest # of clues for a minimal puzzle

For 3x3 we know LNCS = 17 also (45% of the 17-clue puzzles appear to be singles only). Singles only means naked + hidden singles.

I think we also have some GNC results for the 3x3 case, but I can't put my finger on them at the moment …

[m_b_metcalf]

I think we also have some GNC results for the 3x3 case, but I can't put my finger on them at the moment …

Look here and you will find dobrichev's astounding

Code: Select all

  . . . . . . . . .
 . 1 2 . 3 4 5 6 7
 . 3 4 5 . 6 1 8 2
 . . 1 . 5 8 2 . 6
 . . 8 6 . . . . 1
 . 2 . . . 7 . 5 .
 . . 3 7 . 5 . 2 8
 . 8 . . 6 . 7 . .
 2 . 7 . 8 3 6 1 5     No. of givens =  40

Regards,

Mike

[Mathimagics]

40 it is … thanks Mike!

[Mathimagics]

Here is the new table, with data from dobrichev's max-givens results (which are indeed very impressive! ).

Code: Select all

Minimal Puzzles vs Givens:
------------------------------------------------
Box  Grid   LNC   LNC/Grid   LNCS    GNC    GNCS
------------------------------------------------
3x3    81    17    0.2099      17     40      39
3x4   144    30    0.2083
3x5   225    48    0.2133
4x4   256    55    0.2148
4x5   400    91    0.2275
4x6   576   
5x5   625   146    0.2336


Legend:

• Box: box size
• Grid: grid size
• LNC: least # of clues
• LNCS: LNC for singles-only puzzle
• GNC: greatest # of clues
• GNCS: GNC for singles-only puzzle

For standard Sudoku (box 3x3), the proportion of 17-clue puzzles that are singles-only 0.45. For minimal 39-clue puzzles, this drops to 0.0001 (I found 119 cases among the 1,261,278 puzzles I was able to extract from Mladen's data).

Sample 39-clue minimal puzzle, singles-only:

Code: Select all

..........12.34567.345.6182..1.582.6..86....1.2...7.5...37.5.28.8..6.7..2.7.83615


[m_b_metcalf]

I wondered whether there is some correlation between the number of clues in a minimal puzzle and the number of unavoidable sets in its solution grid (maybe someone's been down this path already, but I don't remember). The more UAs you have, the more clues you need to pin them down, I thought. So I counted the number of UA-4s in 2650 of dobrichev's 9x9 39-clue puzzles, and got this distribution (from 1 to 60):

Code: Select all

   0   0   0   0   0   2 287  32 327 145
 293  941139 278  18   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   1   0   1   3   0   2   5   1   4   5
   1   4   2   1   2   1   0   0   1   0
   1   0   0   0   0   0   0   0   0   0

I then did the same for 2650 9x9 17-clue puzzles, and got (from 0 to 60):

Code: Select all

                                       5
  21  63 147 219 340 379 360 340 261 193
 119 107  52  19  17   6   0   2   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0

which does look different. (There may be some distortion in the distributions as I didn't check for duplicate grids. Too late now.)


I then thought to make the same test on some 16x16s. I started with 191 16x16s from Sudoku16-MP-MM:

Code: Select all

   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0 191   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0

which wasn't very illuminating, so generated myself 2000 random grids and got

Code: Select all

   0   0   0   0   0   0   0   0   0   0
   0   0   1   0   4   6   9  12  17  23
  53  58  84  91 112 136 133 148 135 158
 133 132 124 110  67  57  50  46  30  22
  16   8   8   8   5   1   2   1   0   0
   0   0   0   0   0   0   0   0   0   0

and ran the same test on ton's 55-clue puzzle, for which the number is 21, at the low end of the range.


Finally, I generated 10 puzzles from each of my extreme grids, 13 and 48, wondering whether there would be any noticeable difference in the number clues in them. There wasn't. But below are the two grids for others to play with (my code is too slow for a really long run).


Regards,

Mike

Code: Select all

 13  UA-4s
 13 11 15  2  4 14  8 10  1 16 12  5  3  6  9  7
 12 10 14  1  2 11 15 16  7  3  6  9  8  5 13  4
  9  7  8  6 12 13  3  5 10 11  2  4 15 14  1 16
 16  5  3  4  7  9  6  1 14 15 13  8 10 11 12  2
  6  9 12  7 10  2 13 11  3  8  1 14  4 15 16  5
 14  8 11 13  6  7 12  3  5  4 15 16  2  9 10  1
  1 16  5 10  8 15  4 14  2  6  9  7 12 13 11  3
  2 15  4  3 16  5  1  9 12 10 11 13  6  8  7 14
 11 14  6 12  1  4  5  7  9 13  8 15 16  2  3 10
  7  3 16  5  9  8  2 13  6  1 14 10 11  4 15 12
  4  2  1  8 11 10 14 15 16 12  5  3  9  7  6 13
 10 13  9 15  3  6 16 12  4  2  7 11 14  1  5  8
 15  4 10 16 14  1  9  6 13  5  3  2  7 12  8 11
  3 12 13  9 15 16  7  8 11 14  4  1  5 10  2  6
  8  1  2 11  5 12 10  4 15  7 16  6 13  3 14  9
  5  6  7 14 13  3 11  2  8  9 10 12  1 16  4 15


Code: Select all

 48  UA-4s
  8  6  5 11  2 13 15  4 16 14 12  9  3  1  7 10
 16  7 10 14 11  8  1  5  3  4  6 13  9 12  2 15
  3 15 13 12 16 14  7  9 10  8  2  1  5 11  4  6
  2  9  1  4 10  6 12  3 11  5 15  7  8 14 16 13
 10  8  6  1 12 16  2 14  5 11  4  3 13 15  9  7
 15  2  7 16  8  1  5  6 14 13  9 12 10  4 11  3
 14 13  9  3  7  4 11 15  2  6 10 16 12  8  5  1
  4 12 11  5 13  3  9 10  7 15  1  8 16  2  6 14
  7 16 12  6  3 10  4  2  9  1  5 11 15 13 14  8
  5 10 14 13 15  7  8 11  4  3 16  2  1  6 12  9
  9  3  4 15  1  5 14 16  8 12 13  6  2  7 10 11
  1 11  2  8  9 12  6 13 15 10  7 14  4  5  3 16
 13 14 15  2  5 11 10  7  1 16  3  4  6  9  8 12
 11  4  3 10 14  9 13 12  6  2  8 15  7 16  1  5
  6  1 16  7  4 15  3  8 12  9 11  5 14 10 13  2
 12  5  8  9  6  2 16  1 13  7 14 10 11  3 15  4



[Mathimagics]

Hi Mike,

I wondered whether there is some correlation between the number of clues in a minimal puzzle and the number of unavoidable sets in its solution grid (maybe someone's been down this path already, but I don't remember).

It's actually a well-trodden path, because there is an intimate link between UA's and clue counts!

You compared two cases in your sample with the lowest (13) and highest (48) UA4 counts, and found no apparent difference in minimal puzzle clue counts. That's mainly due to the fact that no individual UA can be treated in isolation, as most UA's overlap with others. So typically no inferences can be made based on the UA4 counts.

The least clue requirements are determined by the complex interaction of multiple overlapping UA's. A minimal puzzle is necessarily one whose clues "hit" every possible UA (assuming the complete UA set is known). Given that we usually only have a subset of all the possible UA's for a given grid, we typically settle on some reasonable pool of UA's, then enumerate all the "hitting sets" (sets of cells that hit every UA in the pool).

This process at the very least gives us a lower bound for LNC (via the size of the smallest hitting set), but this lower bound will typically be several clues short of the actual LNC value, due to the incompleteness of our UA pool. So we usually have to add further clues from the general population in order to find valid puzzles, and the number of puzzles we have to test goes up alarmingly as the possible "extra clue" combinations increase (and for 16x16 puzzles this is bound to become very intimidating).

But the HS approach is complex and, for 16x16, is likely to be very, very expensive. And it only works with individual solution grids. Perhaps it could be used to see if our 55-clue puzzle has any relatives, but even that simple task may turn out to be infeasible with desktop PC's.

As for finding minimal puzzles with low clue counts, sadly we can get very little information from simply counting small-sized UA's, I'm afraid.

[PS] Some hint of the combinatorial-explosion factor for 16x16 is given by the time it took me to conduct a full {-2, +1} trawl on the 55-clue puzzle, looking for a 54-clue puzzle that way. Using a SAT solver for testing (the fastest solving option available), this took more than 2 days. (And did not find anything).

[m_b_metcalf]

Mathimagics,

Thanks for your observations. I don't intend pursue this further, except

a) to point out that the distribution I posted for 17-clue puzzles failed to include the fact that there are five (in that sub-set) with zero UA4s;

b) to post this high-on-the-scale 9x9 grid:

Code: Select all

Grid (rotational symmetry of givens) with 36 UA4s

  7  3  4  8  5  1  6  9  2
  9  6  1  7  2  4  3  8  5
  2  5  8  6  3  9  7  1  4
  3  7  2  4  9  8  1  5  6
  1  8  5  3  6  7  4  2  9
  6  4  9  2  1  5  8  3  7
  5  9  3  1  7  6  2  4  8
  4  2  7  5  8  3  9  6  1
  8  1  6  9  4  2  5  7  3

Of course, dobrichev's 39-clue puzzles go up to 51.

Regards,

Mike

[Mathimagics]

Interestingly, the solution grid for dobrichev's 40-clue discovery has minimal puzzles for just about any size in the range:

Here it is with a 19-clue twin (I think 19 is the actual LNC for this grid *)

Code: Select all

+-------+-------+-------+   +-------+-------+-------+
| . . . | . . . | . . . |   | 5 . . | . . . | . . . |
| . 1 2 | . 3 4 | 5 6 7 |   | 8 1 . | . . . | 5 . . |
| . 3 4 | 5 . 6 | 1 8 2 |   | . . . | . . 6 | . . 2 |
+-------+-------+-------+   +-------+-------+-------+
| . . 1 | . 5 8 | 2 . 6 |   | . . . | 3 . . | . 9 . |
| . . 8 | 6 . . | . . 1 |   | 3 . . | 6 . 2 | . 7 . |
| . 2 . | . . 7 | . 5 . |   | . . . | . . . | 8 . . |
+-------+-------+-------+   +-------+-------+-------+
| . . 3 | 7 . 5 | . 2 8 |   | . 6 . | . 1 . | . . . |
| . 8 . | . 6 . | 7 . . |   | . . 5 | . . . | . 3 . |
| 2 . 7 | . 8 3 | 6 1 5 |   | . . . | . 8 . | . . 5 |
+-------+-------+-------+   +-------+-------+-------+


[ * ] I have since found an 18-clue puzzle on this grid

[ton]

20x20(4x5), 89-clue
I think minimum number is 88.
I think minimum numbers are about "floor(n^2 / 4) - (h - 1)(w - 1)".

Code: Select all

+---------------+---------------+---------------+---------------+
|  .  6  .  .  .|  .  3 11  .  .|  .  .  .  .  .| 18  2  .  .  .|
|  .  .  8  .  5|  .  .  .  .  .| 19  . 13 16  .|  .  .  .  .  .|
|  .  . 16  .  9|  .  .  .  .  .|  8  .  . 15  .| 20  .  .  .  .|
|  .  .  .  .  .|  .  .  4  .  .|  .  .  .  .  .| 10 12  .  . 14|
+---------------+---------------+---------------+---------------+
|  .  .  .  .  .|  .  .  .  .  .|  .  2  .  . 11|  .  .  .  .  .|
|  .  .  .  .  8|  .  .  1  .  .|  .  .  .  . 12|  .  .  .  .  .|
|  .  .  .  .  .|  . 18 12  .  .|  .  4 10  .  3|  .  .  .  .  .|
|  .  .  9  . 15|  .  .  .  .  .|  .  .  .  . 18|  .  .  8  . 16|
+---------------+---------------+---------------+---------------+
| 15  .  5  . 19|  .  .  .  .  .|  .  .  . 13  .|  .  . 16  9  8|
|  .  .  . 18  .|  . 10  2 12 11|  .  .  .  .  4|  1  .  .  .  .|
|  .  .  .  .  .|  .  4 18  . 20|  .  .  .  . 10|  .  . 19  .  .|
|  .  .  .  . 16|  . 17  .  .  .|  .  .  .  .  .|  .  .  5  . 13|
+---------------+---------------+---------------+---------------+
|  .  .  . 11  .|  .  .  .  .  .|  .  .  .  .  .|  .  .  .  .  .|
| 10 12  .  4  .|  .  .  .  .  .|  .  .  .  .  2| 11  .  .  .  .|
|  .  .  . 14  .| 15  .  . 19  .|  9  .  .  5  .|  .  . 13  .  .|
|  .  .  .  .  .|  8  .  .  .  .|  .  .  .  .  .|  .  .  .  .  .|
+---------------+---------------+---------------+---------------+
|  .  .  .  .  .| 16  .  .  .  .| 15  .  . 19  .|  .  .  .  .  .|
|  .  .  .  1  .| 19  .  . 13  .|  .  .  .  8  .|  4  .  .  .  .|
|  . 11  . 10  .|  . 14  .  .  .|  .  .  .  .  .|  2 20  .  .  .|
|  .  4  .  2  .|  .  .  .  .  .|  .  .  .  .  .| 12 10  .  3 11|
+---------------+---------------+---------------+---------------+


[ton]

20x20(4x5), 88-clue

Code: Select all

+---------------+---------------+---------------+---------------+
|  .  .  .  .  .|  .  .  .  .  .|  .  .  .  . 12|  .  .  .  .  .|
|  .  .  . 18  .|  .  .  .  .  .|  .  . 13  . 15|  .  .  3  .  .|
|  . 11 16  .  .|  . 19  .  .  .|  .  .  .  .  .|  6  .  .  4  .|
|  .  .  .  .  .|  . 14  .  .  .|  .  .  .  .  .|  .  .  .  .  .|
+---------------+---------------+---------------+---------------+
|  . 14  1  .  .|  .  .  8  .  .|  .  .  .  .  .|  .  .  .  .  .|
|  .  7 11  . 19|  .  .  .  .  .|  4  .  .  .  .|  1  .  . 17  .|
|  .  .  .  .  .|  3  .  2  . 15|  .  .  .  . 13|  .  . 10  .  .|
|  .  .  .  .  .| 12  . 13  . 18|  .  .  2  .  3|  .  . 15  .  .|
+---------------+---------------+---------------+---------------+
|  8  .  .  2  .| 20  . 12  .  .|  .  .  .  .  .|  .  .  .  .  .|
|  .  .  .  .  .|  .  .  6  .  .| 11 19  .  4  .|  7  5  . 14  .|
|  .  .  . 16  .|  .  .  .  .  .|  9  1  .  7  .| 17  .  . 19  4|
| 18  .  .  3  .| 15  . 10  .  .|  . 13  .  .  .|  .  .  .  .  .|
+---------------+---------------+---------------+---------------+
|  .  .  .  .  .|  .  . 15  .  .|  .  .  .  .  2|  9  .  .  .  .|
|  9 17  7  .  .|  .  .  .  .  .|  .  .  .  .  .|  4  .  .  1 11|
|  .  1  .  .  .|  .  .  .  .  .|  .  .  .  .  .| 19  .  .  7  .|
|  .  .  .  .  .|  2  .  3  .  .|  .  . 12 18  8|  .  .  .  .  .|
+---------------+---------------+---------------+---------------+
|  .  .  . 12  .|  .  9  .  .  .|  .  .  .  .  .|  . 15  2  .  .|
|  .  .  .  .  .|  .  4  .  .  .|  .  .  .  .  .|  . 13 12  .  .|
|  .  4  .  .  .|  .  1  . 19 14|  7  .  .  9  .|  .  .  .  .  .|
|  .  .  .  .  .|  .  7  . 17  .| 19  .  .  .  .|  . 18  .  .  .|
+---------------+---------------+---------------+---------------+