10 open questions about Sudoku (2012-01-21)
1. We don’t know
1.1. how many valid Sudoku puzzles with exactly one solution exist
1.2. how many valid Sudoku puzzles with exactly one solution exist, whereby no given can be left out and a Sudoku with multiple solutions is created (Minimum Sudoku)
1.3. if there are more Minimum or Non-Minimum Sudoku - as Sudoku with exactly one solution (non Minimum) could be reduced to various Minimum Sudoku
2. Off course we don’t know how many Sudoku with no solution or multiple solutions exist
3. 16er We don’t know, what the minimum number of givens is for a minimum Sudoku (It’s assumed that the minimum number of givens is 17; but there is no prove) – Note: This problem has been solved 01/01/2012 – there is no 16 clue puzzle with one solution.
4. We don’t know, what the maximum number of givens is, for a minimum Sudoku (Maximum Sudoku:There are known maximum Sudoku with 39 givens; but there is no prove)
5. We know very little about hardness of 9*9 Sudoku
5.1. We have no (commonly agreed) measure of hardness of Sudoku
5.2. We don’t know, whether every 9*9 Sudoku has the property “logic” (this means that any 9*9 Sudoku with exactly one solution can be resolved by logic)
5.3. We don’t know the maximum hardness of valid 9*9 Sudoku with exactly one solution
5.4. We have no logical algorithm to find at least one solution for a Sudoku with multiple solutions
6. We don’t know whether or not it is easier to find a Sudoku resolution theory or to define necessary and sufficient criteria on an existing solution (criteria that would only bear on the entries of a puzzle)
7. There is a lot of confusion and disagreement about the question what is trail-and-error and logic in respect of Sudoku
8. We have no logical algorithm to create Sudoku – but all generators are trail and error
9. We don’t know the ratio between Sudoku puzzles fulfilling the primary logic (each given appearing less than 9 times in each row, column and block) and between valid Sudoku puzzles. (pls note: a puzzle might fulfill the primary logic, but have no solution)
10. We don’t know whether or not P=NP or P<>NP (Answering the question, whether each 9*9 Sudoku with exactly one solution can be resolved by logic with a “Yes”, wouldn’t answer the P=NP question.
There is prove that Sudoku in general is NP hard. But this includes regular Sudoku of increasing size (9*9, 16*16, 25*25, ….) and Sudoku with multiple solutions. Vice versa if we would know, that 9*9 Sudoku can’t be resolved by logic, we would not know that P<>NP.
But note: I’m not dealing with P=NP as this question has been dealt with by many people more intelligent than I’m for more than 30 years (with no result). Solving the question whether all 9*9 Sudoku puzzles can be solved by logic is only a mosaic stone in the whole universe of open P=NP questions.
I won’t promise to answer those questions (except Nr. 3), but I will discuss and analyze each of those questions on a separate page and bring the information I found by search and analysis together. I’m interested in your opinion.