Today I came across an interesting note on math stackexchange in reply to an old question on whether the clues of a proper sudoku can have fewer than 8 distinct digits. The longstanding accepted answer, and the one conventionally given, is "no". However, a new reply proposed an alternative definition of uniqueness that would treat solutions differing only in re-labelling of the missing digits as the same. That is, the task is to find 9 patterns or templates, each comprised of 9 cells obeying the usual exactly-one constraints, where together they cover all 81 cells of the board, and where no pattern covers more than 1 distinct digit given as a clue. The puzzle has a unique solution if there is only one set of 9 patterns that achieves this, ignoring labels. Put another way, if there are N distinct digits in the clues of a puzzle, then the puzzle has a unique solution under this definition iff it has exactly (9-N)! conventional solutions.
Suppose we call puzzles with unique solutions under this defintion as "pattern proper puzzles". The first question this raises is, of course, how few distinct digits a pattern proper puzzle can have in its clues. From some brief search it looks like all grids probably admit pattern-proper puzzles with 7 distinct digits, most grids (90%+) admit them with 6 distinct digits, and a very small fraction admit them with 5 distinct digits. I didn't look for 4, but that seems unlikely.
Here is an example with 5 distinct digits:
- Code: Select all
1...2...3.4.............21....2...3..2....5..5...13.4..1..34...3...5....2.......5
Has a variant like this been discussed before? Has anyone explored the distinct digit limit either theoretically or empirically but more exhaustively? Has anyone explored the difficulty of such puzzles or developed theory or techniques for how such puzzles might be solved in a logical manner?
The first idea that springs to mind is that if you can prove that a cell can't contain any digit already present somewhere on the board then you can fill it with an arbitrary choice from the currently missing digits. In this way you may be able to convert the puzzle incrementally or all at once to a normal sudoku. For example, in the puzzle given above row 6 already contains clues 1,3,4,5. And we can exclude '2' from 3 of the blank cells in the row. So we might immediately place 6,7,8 in these cells, and now we have a conventional sudoku with 8 distinct clue digits. So this puzzle is pretty easy (or at least its difficulty doesn't arise from the missing digits). But maybe these can be much harder, and can involve interesting new classes of uniqueness inferences.
Cheers,
Tom
