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$ 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
    Commented Jul 4, 2018 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
    Commented Jul 4, 2018 at 4:52
  • 1
    $\begingroup$ It should be a np problem.and it's not a puzzle it seems. $\endgroup$
    – apm
    Commented Jul 4, 2018 at 5:45
  • $\begingroup$ Solve for K where number of puzzles is minimised would make sense, but yeah, not a puzzle $\endgroup$
    – Jesse
    Commented Jul 4, 2018 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
    Commented Jul 4, 2018 at 18:34

1 Answer 1


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.

  • $\begingroup$ Welcome to Puzzling :D $\endgroup$
    – ABcDexter
    Commented Oct 12, 2018 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.