For a 9 x 9 Sudoku puzzle with a unique solution: 1. What is the fewest possible number of shown squares with which the puzzle can be solved? 2. What is the greatest number of shown squares that can't be solved? 3. How would one determine the answers to the two questions?est
1. 17
2. 77
3. For 1, see Mathematicians Solve Minimum Sudoku Problem | MIT Technology Review. It wasn't easy. For 2, all you need are four empty squares that are the four corners of rectangle, where the rectangle goes across two boxes, and the missing numbers are two of one value and two of another. Then there are two solutions, so it can't be solved.
(Note: for #2, I am assuming that you mean the puzzle can't be solved because there is more than one solution, not because there are no solutions, i.e. the puzzle is invalid. For the no solution case, the answer is arguably 81, since you can provide a filled-in puzzle that is simply wrong, and therefore cannot be solved.)
2. 77
3. For 1, see Mathematicians Solve Minimum Sudoku Problem | MIT Technology Review. It wasn't easy. For 2, all you need are four empty squares that are the four corners of rectangle, where the rectangle goes across two boxes, and the missing numbers are two of one value and two of another. Then there are two solutions, so it can't be solved.
(Note: for #2, I am assuming that you mean the puzzle can't be solved because there is more than one solution, not because there are no solutions, i.e. the puzzle is invalid. For the no solution case, the answer is arguably 81, since you can provide a filled-in puzzle that is simply wrong, and therefore cannot be solved.)
Comments
Post a Comment