1
$\begingroup$

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$.

|improve this question
$\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
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Welcome to Puzzling :D $\endgroup$ – ABcDexter Oct 12 '18 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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