Smallest integer $k$ so that no Sudoku grid has exactly $k$ solutions Inspired by this question,
consider hints on a Sudoku board. A regular puzzle has a unique solution.
It is clear that there are puzzles with 2 or 3 solutions, and therefore, I guess, puzzles with say 4, and 6 solutions.
Now, what is the smallest integer $k$ such that there is no set of Sudoku clues resulting in exactly $k$ solutions?
 A: This is just a partial answer, which can perhaps be turned into a community wiki, where examples of partial fillings that allow $n$ complete valid fillings.
This admits $k=2$ solutions:
\begin{array}{ccccccccc}
 . & . & . & . & 5 & 1 & 8 & 7 & 6 \\
 . & 7 & . & 6 & . & 9 & . & . & 3 \\
 6 & . & 8 & . & . & 2 & . & 9 & . \\
 . & 4 & . & 1 & . & . & . & 8 & . \\
 . & . & 1 & . & 3 & . & . & . & 4 \\
 8 & . & . & . & . & 7 & 1 & . & . \\
 2 & . & . & 5 & 6 & . & . & 3 & . \\
 . & . & . & . & 1 & . & 9 & . & 8 \\
 3 & . & . & . & . & 4 & . & . & . \\
\end{array}
This allows $k=3$ fillings:
\begin{array}{ccccccccc}
 . & . & . & . & . & 1 & 8 & 7 & 6 \\
 . & 7 & . & 6 & . & 9 & . & . & 3 \\
 6 & . & 8 & . & . & 2 & . & 9 & . \\
 . & 4 & . & 1 & . & . & . & 8 & . \\
 . & . & . & . & 3 & . & . & . & 4 \\
 8 & . & . & 9 & . & 7 & 1 & . & . \\
 2 & . & . & 5 & 6 & . & . & 3 & . \\
 . & 6 & . & . & 1 & . & 9 & . & 8 \\
 3 & 8 & 7 & . & . & . & . & . & . \\
\end{array}
If my calculations are correct, this allows $k=5$ complete fillings:
\begin{array}{ccccccccc}
 . & . & . & . & 5 & 1 & 8 & 7 & 6 \\
 . & 7 & . & 6 & . & 9 & . & . & 3 \\
 6 & . & 8 & . & . & 2 & . & 9 & . \\
 . & 4 & . & 1 & . & . & . & 8 & . \\
 . & . & 1 & . & 3 & . & . & . & 4 \\
 8 & . & . & . & . & 7 & 1 & . & . \\
 2 & . & . & 5 & 6 & . & . & 3 & . \\
 5 & . & . & . & 1 & . & . & . & 8 \\
 3 & . & . & . & 9 & . & . & . & . \\
\end{array}
Currently, $k=7$ is still unknown.
This is the mathematica code I use to solve Sudokus. 
It is just basic recursion, and can most likely be optimized a lot.
(* Returns true iff we can place n at r,c in the filling. *)

IsValidQ[partFil_, n_, {r_, c_}] := Module[{sr, sc},
   (* Check row, col, sub-box for already existing. *)
   Catch[
    If[MemberQ[partFil[[r, All]], n], Throw[False]];
    If[MemberQ[partFil[[All, c]], n], Throw[False]];
    sr = Floor[(r - 1)/3]; sc = Floor[(c - 1)/3];
    If[MemberQ[
      Join @@ partFil[[3 sr + 1 ;; 3 sr + 3, 3 sc + 1 ;; 3 sc + 3]], 
      n], Throw[False]];
    True
    ]
   ];

SolveSudoku[partialFilling_List] := Module[{recSolve, sols = {}},
   recSolve[pFil_List] := Module[{nFil},
     Catch[
      Do[
       If[pFil[[r, c]] == 0,

        (* Try all 9 numbers. *)

        Do[If[IsValidQ[pFil, n, {r, c}],
          recSolve[ReplacePart[pFil, {r, c} -> n]]]
         , {n, 9}];

        (* We tried all 9 numbers here. Now abort. *)

        Throw[False]
        ]
       , {r, 9}, {c, 9}];
      AppendTo[sols, pFil];
      (*Print["NSOLS: ",sols//Length];*)
      True
      ]
     ];

   recSolve[partialFilling];
   sols
   ];

A: Consider the process of randomly generating single solution puzzles and randomly dropping one or more clues as shown in the pseudo-code below:
GenerateValidNotNecessarilyMinimalSudoku() {
  clues := {}
  consequences := {}
  for literal in RandomPermutation(Range(729)) {
    if literal not in consequences {
      switch (CountSolutions(clues U {literal}, limit=2)) {
       case 0:
         continue
       case 1:
         return clues U {literal}
       case 2:
         clues := clues U {literal}
         consequences := UnitPropagate(clues)
      }
    }
  }
}

samples = []
for _ in Range(NumSamples) {
  clues := GenerateValidNotNecessarilyMinimalSudoku()
  relaxed := clues - PickRandomElements(clues, NumToDrop)
  samples += [CountSolutions(relaxed, limit=10000)]
}

Interestingly, though maybe not surprisingly, this process gives rise to an approximately lognormal distribution of solution counts. Here's a chart showing the empirical distribution (black) of solution counts from a sample of 15 million random puzzles with 1 dropped clue vs. the fitted lognormal model (green). 

And here's the same chart for another 15 million random puzzles, this time dropping 4 clues:

This behavior suggests an absence of the kinds of pattern in solution count probability that might conspire to produce a "low" k. Maybe it also hints at a way to at least guess at the order of magnitude of k. (e.g., choose a useful way to partition the space of possible puzzles, estimate the number of distinct non-equivalent puzzles in each partition, find a way to sample from these puzzles uniformly, fit lognormal models for each partition, given lognormal model and size of sample space, ask in what range does it become likely that some count is zero).
