The New Sudoku Players' Forum

[olimpia]

I was wondering if anyone has researched what is the most cells which can be solved given "n" clues, for the range n = 4 thru 17 (I believe 4 is the fewest clues needed to solve one position, and although rare, 17 is enough to form a complete sudoku).

With the data I would be interested in a graph of "qty solved" vs. "givens". Here is what I started so far (just a quick start):

Code: Select all

givens   qty solved
-------   ------------
4          1
6          2
9          3
...
13        16
...
17        64


Here is a case where 4 givens solves one position:

Code: Select all

1 - - - - - - - -
- - - 1 - - - - -
- - - - - - 2 3 -
- - - - - - - - -
- - - - - - - - -
- - - - - - - - -
- - - - - - - - -
- - - - - - - - -
- - - - - - - - -


And here is a case where 13 givens solves 16 positions:

Code: Select all

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


The data here is incomplete, and I'm not sure if best possible. Please jump in if anyone can add to it.

[StrmCkr]

16 clues = 47 solved (2 solutions missing 18 clues)

this was explored very extensivly for the quest of finding a 16 clue 1 solution grid. so far to no avail.

but. there is a collection of 17 puzzles currently listed on here some where with all that have been found to date.

18 clues are equally as rare.
the majority of puzzles hold 21+ clues on average for 1 solution.

18 clues = 63 solved
81 clues = 0 solved :P

[olimpia]

OK, thanks. here's an update (also showing total complete):

Code: Select all

givens   qty solved    total
------   ------------  -----
4         1             5
5         1             6
6         2             8
7         2             9
8         2             10
9         3             12
...
13        16            29
...
16        47            63
17        64            81


If there's any remarkable (partial grids) for this data please post it also, so we can see how its constructed. thanks.

[coloin]

Code: Select all

+---+---+---+
|...|3.1|...|             
|2.4|...|...|   
|...|...|...|       
+---+---+---+   
|8..|52.|...|       
|...|...|9.1|         
|...|...|3..|           
+---+---+---+       
|...|.4.|.5.|           
|91.|...|...|             
|.3.|...|...|             
+---+---+---+ 15 clues     596 grid solutions.   source G Royle

i believe 29 more inserted, 44 in total

Code: Select all

+---+---+---+
|1..|...|...|
|...|1..|...|
|...|...|...|
+---+---+---+
|.1.|...|...|
|...|...|...|
|...|...|.1.|
+---+---+---+
|...|...|...|
|...|..1|...|
|...|...|..1|
+---+---+---+  6 clues 3 inserted


Code: Select all

+---+---+---+
|...|...|.1.|
|.2.|.5.|...|
|...|...|...|
+---+---+---+
|...|1..|...|
|...|...|2..|
|...|...|...|
+---+---+---+
|...|.7.|5.2|
|...|...|4..|
|1..|...|...|
+---+---+---+ 10 clues , 7 inserted

C

[JPF]

olimpia
Good question !

Here is a quick survey :

Code: Select all

 *-----------*
 |.1.|...|...|
 |...|...|..1|
 |...|.2.|...|
 |---+---+---|
 |...|...|...|
 |1..|...|...|
 |...|...|.1.|
 |---+---+---|
 |..2|...|...|
 |...|..1|...|
 |...|...|.2.|
 *-----------*      8 clues

 *-----------*
 |.1.|...|...|
 |...|...|..1|
 |...|12.|...|
 |---+---+---|
 |...|.1.|...|
 |1..|...|...|
 |...|...|.1.|
 |---+---+---|
 |..2|...|1..|
 |...|2.1|...|
 |..1|...|.2.|
 *-----------*      5 inserted


Code: Select all

 *-----------*
 |...|...|...|
 |...|..2|...|
 |1..|...|...|
 |---+---+---|
 |...|...|.2.|
 |...|.1.|...|
 |.2.|...|..1|
 |---+---+---|
 |..2|...|...|
 |...|...|.12|
 |...|1..|...|
 *-----------*      10 clues

 *-----------*
 |2..|..1|...|
 |...|..2|1..|
 |1..|...|2..|
 |---+---+---|
 |..1|...|.2.|
 |...|21.|...|
 |.2.|...|..1|
 |---+---+---|
 |.12|...|...|
 |...|...|.12|
 |...|12.|...|
 *-----------*      8 inserted


will give you more...

JPF

[olimpia]

Cool I really like the 6 clues/3 inserted. It improved on my 6/2 and looks way cool .
Updating the table again (and now I'm showing source in case anyone wants to go back and check):

Code: Select all

givens   qty solved  total   source
------   ----------  -----   ------
4         1           5
5         1           6
6         3           9      (Coloin)
7         3           10
8         5           13     (JPF)
9         5           14
10        8           18     (JPF)
...
13        16          29     (Olimpia)
...
15        29          44     (G. Royle)
16        47          63     (?)
17        64          81     (many)


Now I'm wondering where do we get a 1:1 payoff? That is at what point does "n" clues solve at least "n" positions

[StrmCkr]

16 is also g. royle.

[JPF]

Code: Select all

 *-----------*
 |..1|...|...|
 |...|...|...|
 |...|.2.|...|
 |---+---+---|
 |...|...|1..|
 |...|..1|...|
 |.2.|...|...|
 |---+---+---|
 |...|...|...|
 |...|1..|...|
 |...|...|.1.|
 *-----------*     7 clues

 *-----------*
 |..1|...|...|
 |...|.1.|...|
 |...|.2.|..1|
 |---+---+---|
 |...|...|1..|
 |...|..1|...|
 |12.|...|...|
 |---+---+---|
 |.1.|...|...|
 |...|1..|...|
 |...|...|.1.|
 *-----------*     4 inserted


Code: Select all

 *-----------*
 |...|1..|...|
 |.2.|...|...|
 |...|...|..2|
 |---+---+---|
 |...|...|...|
 |2..|...|..1|
 |1..|...|...|
 |---+---+---|
 |..1|...|...|
 |...|...|.1.|
 |...|..2|...|
 *-----------*    9 clues

 *-----------*
 |...|12.|...|
 |.2.|...|1..|
 |.1.|...|..2|
 |---+---+---|
 |...|..1|...|
 |2..|...|..1|
 |1..|...|...|
 |---+---+---|
 |..1|...|...|
 |..2|...|.1.|
 |...|.12|...|
 *-----------*   6 inserted


JPF

[eleven]

Interesting question, but very hard for puzzles with more clues.

E.g. in 3 million random multisolution puzzles with 12 clues out of 5 different numbers we only found 1, which solved 9 numbers. It was better with only 4 numbers, but it needed hours to get one with 12+10, though i suspect, that the maximum is 12 or higher.

Here is an 11/9:

Code: Select all

 +-------+-------+-------+
 | . . . | 2 . . | . . . |
 | 3 . . | . . . | . . 1 |
 | . . 1 | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | 2 . . |
 | 1 . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . 2 | . 1 . |
 | . 2 . | . . 1 | . . . |
 | . . . | . . . | . . 3 |
 +-------+-------+-------+

11 clues and 9 solve

[Added: ]

Code: Select all

 +-------+-------+-------+
 | . 4 . | . . . | . . 3 |
 | . 1 . | . . . | . . . |
 | . . . | . 3 . | . 2 . |
 +-------+-------+-------+
 | . . . | . . 1 | . . . |
 | . . . | . . . | 2 . . |
 | 2 . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | 1 . . | . . . |
 | 3 . . | 2 . . | . . . |
 | . . . | . . . | . . 1 |
 +-------+-------+-------+

12 clues and 11 solve

[JPF]

Here is a 14/20 :

Code: Select all

 *-----------*
 |...|1.2|...|
 |3..|...|.4.|
 |...|5..|...|
 |---+---+---|
 |.52|...|...|
 |...|.6.|.3.|
 |.1.|...|...|
 |---+---+---|
 |7..|.3.|...|
 |8..|...|...|
 |...|...|1..|
 *-----------*     14 clues

 *-----------*
 |5..|1.2|...|
 |32.|...|541|
 |1..|5.3|...|
 |---+---+---|
 |.52|3..|.1.|
 |...|.61|235|
 |.13|.25|...|
 |---+---+---|
 |7.1|.3.|.5.|
 |8.5|.1.|...|
 |2..|.5.|1..|
 *-----------*     20 solve


[added 1 :]

Here's a 12/13:

Code: Select all

 *-----------*
 |...|1..|...|
 |.23|...|...|
 |.4.|...|...|
 |---+---+---|
 |...|.4.|.2.|
 |5..|...|...|
 |1..|...|...|
 |---+---+---|
 |.6.|.2.|...|
 |7..|...|1..|
 |...|...|...|
 *-----------*     12 clues

 *-----------*
 |.57|1..|...|
 |.23|...|.1.|
 |.41|...|...|
 |---+---+---|
 |3..|.4.|.21|
 |5..|.1.|...|
 |1..|...|...|
 |---+---+---|
 |46.|.21|...|
 |73.|...|1.2|
 |21.|...|...|
 *-----------*    13 solve


[added 2 :]

This 15 clues is interesting :

Code: Select all

 *-----------*
 |1..|2..|...|
 |...|...|3.4|
 |...|...|5..|
 |---+---+---|
 |6..|...|.7.|
 |...|...|.1.|
 |.3.|.5.|...|
 |---+---+---|
 |...|1..|68.|
 |.5.|...|...|
 |..4|...|...|
 *-----------*  15 clues ; 748 solutions

33 cells can be solved :
 *-----------*
 |195|234|768|
 |..6|51.|3.4|
 |4.3|...|5.1|
 |---+---+---|
 |61.|4.3|.75|
 |54.|...|.13|
 |.3.|.51|.46|
 |---+---+---|
 |3..|145|68.|
 |.51|...|43.|
 |.64|3..|15.|
 *-----------*   33 solve


JPF

[eleven]

Excellent results, JPF.

So to my surprise you need already 7 numbers for the 12/13 (at least my guess with 12+ was true).

Also great the 15/33, which i did not expect to be possible (more than the 15 clue with 596 solutions). With 7 in r8c4 and 8 in r5c5 this one gives a 17 clue also.

[Pat]

16 clues = 47 solved (2 solutions missing 18 clues)

this famous 16-clue puzzle was discovered by gfroyle --

Code: Select all

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



is interesting, because it has only 16 clues.

It CANNOT be uniquely solvable, because it is missing both 8 and 9,
and so they can always be exchanged in any final solution.

But, this turns out to be the only problem --
the puzzle has exactly TWO solutions.

[JPF]

Thanks eleven

Here is an improvement :

14/22

Code: Select all

 *-----------*
 |...|..1|...|
 |.2.|...|...|
 |...|...|...|
 |---+---+---|
 |3.1|...|...|
 |...|2..|..4|
 |..5|...|...|
 |---+---+---|
 |.6.|42.|...|
 |...|7..|5..|
 |...|...|13.|
 *-----------*     14 clues

 *-----------*
 |.3.|..1|...|
 |.2.|3..|..1|
 |.1.|..2|..3|
 |---+---+---|
 |3.1|...|...|
 |...|25.|314|
 |2.5|13.|...|
 |---+---+---|
 |163|425|...|
 |..2|713|546|
 |.5.|...|132|
 *-----------*     22 solve


JPF

[olimpia]

Here's a summary again (hopefuly no typo's):

Code: Select all

givens   qty solved  total   source
------   ----------  -----   ------
4         1           5
5         1           6
6         3           9      (Coloin)
7         4           11     (JPF)
8         5           13     (JPF)
9         6           15     (JPF)
10        8           18     (JPF)
11        9           20     (Eleven)
12        13          25     (JPF)
13        16          29     (Olimpia)
14        22          36     (JPF)
15        33          48     (JPF)
16        47          63     (G. Royle)
17        64          81     (many)


I charted the data and the curve is fairly smooth (obviously increases exponentially).

Its also interesting that many of these partial sudokus only put a few clue values in play. The 6/3 only has 1's (and solves just 1's). The puzzles with 7, 8, 9, and 10 clues only have two clue values (1 and 2). They are simple and cute, like a little baby

[JPF]

Here is a 13/17 :

Code: Select all

 *-----------*
 |...|1..|...|
 |...|2..|...|
 |.3.|...|.4.|
 |---+---+---|
 |...|51.|2..|
 |.4.|...|...|
 |...|...|...|
 |---+---+---|
 |...|.46|.3.|
 |...|.3.|...|
 |2..|...|...|
 *-----------*    13 clues

 *-----------*
 |...|1..|.2.|
 |...|2..|...|
 |.32|6.5|.4.|
 |---+---+---|
 |3..|51.|2.4|
 |.4.|32.|...|
 |.2.|46.|...|
 |---+---+---|
 |...|.46|.32|
 |...|.32|...|
 |2.3|.51|4..|
 *-----------*    17 solve


JPF