0

Let's assume I've generated, from an empty board, a complete and valid sudoku board by some means. Borrowing from this question, let's say that board is:

+-------+-------+-------+
| 5 6 4 | 9 3 7 | 2 8 1 |
| 1 7 2 | 5 4 8 | 9 6 3 |
| 9 8 3 | 1 6 2 | 4 7 5 |
+-------+-------+-------+
| 7 4 9 | 3 2 5 | 8 1 6 |
| 2 1 8 | 7 9 6 | 5 3 4 |
| 6 3 5 | 8 1 4 | 7 9 2 |
+-------+-------+-------+
| 8 2 6 | 4 7 3 | 1 5 9 |
| 4 5 1 | 6 8 9 | 3 2 7 |
| 3 9 7 | 2 5 1 | 6 4 8 |
+-------+-------+-------+

According to this paper (pdf) there must be at least 17 clues for the sudoku to be solvable. I take that to mean solvable without guessing. I'm unsure if that means there is distinctly one grid that's an answer.

If I have a grid, how can I pick the 17 squares to reveal and guarantee that the user doesn't have to guess in order to solve the grid?

Community
  • 1
Corey Ogburn
  • 501

1 Answers1

0

CW, not much real mathematics in this.

Solvable does, indeed, mean one and only one solution. Furthermore, it is easy enough, if you know about the general computer backtracking type algorithms, to find all solutions from a given initial set. There was an article in the AMS Notices with a way to imitate backtracking using colored pencils. Guaranteed to work, but not the most fun.

When people solve these things, or when most computer solvers do so, they use a small finite set of rules. For any given set of such rules, there are puzzles with one and only one solution that cannot be solved with that set of rules. The reason for this is not mathematics, it is just that the human mind can remember only so many tricks on a given topic. http://sudokuone.com/sweb/exam/turbotfish.htm

Finally, some of the more interesting tricks, ones that you may not have seen, depend crucially on uniqueness of the solution. Those are fun. Some were found early by programmers. In competitions, puzzles did not always have just single solutions.

Probably enough for now.

Will Jagy
  • 139,541