# Generate a sudoku puzzle with minimum number of entries that has exactly $k$ solutions

Is there an algorithm to generate a sudoku puzzle having the minimum number of entries that has exactly $k>1$ solutions? What is this minimum number of entries, as a function of $k$? Given that the minimum number of entries for $k=1$ solutions is $17$, then surely the solution to this question is less than or equal to $17$.

• FWIW: I disagree with @Jesse, I think this question does belong on this stack. Whether you'll get an answer or not, given how much effort it took to prove k=1, is another matter... – Alconja Jul 4 '18 at 4:21
• @Alconja The first sentence threw me off. You cannot generate a puzzle minimising the number of puzzles generated. It does not make sense. – Jesse Jul 4 '18 at 4:52
• It should be a np problem.and it's not a puzzle it seems. – apm Jul 4 '18 at 5:45
• Solve for K where number of puzzles is minimised would make sense, but yeah, not a puzzle – Jesse Jul 4 '18 at 13:25
• @apm I don't think this is even in NP (Non-deterministic Polynomial time); given an answer, a brute force search is still needed to verify that the number of entries is minimal. In any case, PSE is a site for those who create, solve, and study puzzles, so this question is definitely on-topic, even though it isn't a puzzle in itself. – Bass Jul 4 '18 at 18:34