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$.
$\begingroup$
$\endgroup$
-
$\begingroup$ 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... $\endgroup$ – Alconja Jul 4 '18 at 4:21
-
$\begingroup$ @Alconja The first sentence threw me off. You cannot generate a puzzle minimising the number of puzzles generated. It does not make sense. $\endgroup$ – Jesse Jul 4 '18 at 4:52
-
1$\begingroup$ It should be a np problem.and it's not a puzzle it seems. $\endgroup$ – apm Jul 4 '18 at 5:45
-
$\begingroup$ Solve for K where number of puzzles is minimised would make sense, but yeah, not a puzzle $\endgroup$ – Jesse Jul 4 '18 at 13:25
-
3$\begingroup$ @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. $\endgroup$ – Bass Jul 4 '18 at 18:34
$\begingroup$
$\endgroup$
This question has been raised in 2006 on this forum. Even "the big guys" of sudoku maths (Ed Russell and Fredrik Kjell) were unable to give a real answer.
