Do sudoku answers always have a single minimal clue set?

Question

Suppose we have a solved sudoku, which was started from a minimal set of clues to its unique solution, i.e. 17+ numbers in specific locations, which we'll call set1. Is there a set2, (or set3, etc.), with few or no elements in common with set1?

Put another way, suppose you have Monday and Tuesday newspapers, each with an apparently different sudoku. You finish Monday, and have its 81 number solution. Tuesday seems to be a different puzzle, but when you finish, it turns out the solution is identical to that of Monday. Is that, given the mathematics of sudoku, possible?

@JonathanAllan, It means no redundant clues, where any clue removed would make the answer insoluble or diverge to more than one solution. So 33 > clues > 16, as implied by Wikipedia. — agc, Jun 22 '19 at 23:39
@agc So that's a local minimum for that particular puzzle? — Rosie F, Jun 23 '19 at 06:09
@RosieF, Yes, that'd be a local minimum for that particular puzzle. Sudoku clue minimums vary between puzzles, so unless I'm missing something, there seems to be no obvious benefit of adding the term local to the question's text. — agc, Jun 23 '19 at 11:39
@agc The difference it makes is pretty significant. A clue set is locally minimal if you can't remove any clue from it without making it ambiguous (that is it has no redundant clues). Globally minimal would mean there is no smaller clue set for that puzzle. For example in Jonathan Allen's answer they provide two locally minimal clue sets but the 25 clue set cannot be globally minimal since there is a smaller clue set (the 24 clue one in the answer). — Wheat Wizard, Jun 23 '19 at 13:02
@SriotchilismO'Zaic, That sounds like a useful distinction, but its application here eludes me. Suppose we've disjoint clue-sets {X,Y}, and X is globally minimal and Y is not; or both are; or neither is. How would those distinctions pertain to this specific Q? — agc, Jun 23 '19 at 13:22
@agc To easily see how this makes a difference to the question we can just look at Jonathan Allen's answer again. In their answer we have two definitely locally minimal sets, however one of them is definitely not globally minimal (as pointed out in my last comment). So if your question asks about local minima (as it seems to right now) then that answer sufficiently answers the question. However it would not answer the question if it were about global minima, that question is much much harder to answer. This is likely why they were the one to ask about this distinction. — Wheat Wizard, Jun 23 '19 at 13:51
@Abigail, See Is there a Sudoku answer that has only a single minimal clue set? — agc, Jun 25 '19 at 13:23

Jonathan Allan · Accepted Answer · 2019-06-23T18:34:19.730

Here are two proper, irreducible sudoku with the same solution as each other and disjoint sets of clues (24 & 25 clues, respectively).

   1 2 3   4 5 6   7 8 9          1 2 3   4 5 6   7 8 9
 ·-------·-------·-------·      ·-------·-------·-------·
A| · · · | 4 · · | 7 · · |     A| 1 2 3 | 4 5 6 | 7 8 9 |
B| · · 6 | · 8 · | 1 · · |     B| 4 5 6 | 7 8 9 | 1 2 3 |
C| 7 · · | · · 3 | · 5 · |     C| 7 8 9 | 1 2 3 | 4 5 6 |
 ·-------+-------+-------·      ·-------+-------+-------·
D| 8 · 7 | · 3 · | · · 4 |     D| 8 9 7 | 2 3 1 | 5 6 4 |
E| · · 1 | · · · | · · · |     E| 2 3 1 | 5 6 4 | 8 9 7 |
F| · 6 · | · · · | 2 · · |     F| 5 6 4 | 8 9 7 | 2 3 1 |
 ·-------+-------+-------·      ·-------+-------+-------·
G| 3 · · | · · 5 | · · 8 |     G| 3 1 2 | 6 4 5 | 9 7 8 |
H| · 4 · | 9 · · | · · 2 |     H| 6 4 5 | 9 7 8 | 3 1 2 |
J| · · · | · 1 · | 6 · · |     J| 9 7 8 | 3 1 2 | 6 4 5 |
 ·-------·-------·-------·      ·-------·-------·-------·

   1 2 3   4 5 6   7 8 9          1 2 3   4 5 6   7 8 9
 ·-------·-------·-------·      ·-------·-------·-------·
A| · · 3 | · · · | · · · |     A| 1 2 3 | 4 5 6 | 7 8 9 |
B| 4 · · | · · · | · 2 · |     B| 4 5 6 | 7 8 9 | 1 2 3 |
C| · 8 · | 1 2 · | · · 6 |     C| 7 8 9 | 1 2 3 | 4 5 6 |
 ·-------+-------+-------·      ·-------+-------+-------·
D| · · · | · · · | · · · |     D| 8 9 7 | 2 3 1 | 5 6 4 |
E| 2 · · | · 6 · | · · 7 |     E| 2 3 1 | 5 6 4 | 8 9 7 |
F| · · · | 8 · 7 | · 3 1 |     F| 5 6 4 | 8 9 7 | 2 3 1 |
 ·-------+-------+-------·      ·-------+-------+-------·
G| · 1 · | 6 4 · | 9 · · |     G| 3 1 2 | 6 4 5 | 9 7 8 |
H| 6 · 5 | · · 8 | · · · |     H| 6 4 5 | 9 7 8 | 3 1 2 |
J| 9 · 8 | 3 · · | · 4 · |     J| 9 7 8 | 3 1 2 | 6 4 5 |
 ·-------·-------·-------·      ·-------·-------·-------·

Proper: Having a single, unique solution
Irreducible: Removing any clue would make the resulting puzzle no longer proper
Disjoint: Having no elements in common

Note: The first is very, very difficult, but the second is extremely easy!

I found these by running the below Python code, which uses sudoku which is solver code available from my GitHub.

from random import shuffle
from sudoku import getRandomSudoku, Solver

MAX_CLUES = 26  # Warning: gets slow below 25
MIN_NON_CLUES = 81 - MAX_CLUES

n = 0
while True:
    unsolved = getRandomSudoku()
    if sum(x is None for x in unsolved._repr) < MIN_NON_CLUES:
        continue
    solved = next(unsolved.genSolutions())
    newUnsolved = Solver([b if a is None else None for a, b in zip(unsolved._repr, solved._repr)])
    if newUnsolved.uniqueness() != 1:
        continue
    indices = [i for i, v in enumerate(newUnsolved._repr) if v is not None]
    shuffle(indices)
    for i in indices:
        s = Solver(newUnsolved._repr[:i] + [None] + newUnsolved._repr[i+1:])
        if s.uniqueness() == 1:
            newUnsolved = s
    if sum(x is None for x in newUnsolved._repr) >= MIN_NON_CLUES:
        break

print(unsolved.representation())
print(newUnsolved.representation())
print(unsolved)
print(newUnsolved)
print(solved)

As a sidenote, that would be great to take a look at your python code. Can you, please, upload it to some gist service and drop a link here? — val - disappointed in SE, Jun 23 '19 at 13:54
You could also have run your Python code on the previously posted disjoint set from Deusovi to make two disjoint irreducible sudoku. — Cœur, Jun 23 '19 at 15:30
@val - I've added code. It's not the most efficient code, but it works (also the same could be achieved without dlx by using a backtracking algorithm instead). — Jonathan Allan, Jun 23 '19 at 18:35
The first one is not at all "very, very difficult". I only needed basic techniques and a binary branch-point at G7 (either 4 or 9) to solve it. — user21820, Jun 24 '19 at 15:28
@user21820 then either your definition of basic is different to mine or you made an assumption that you did not realise you made. Try the solver as sudoku wiki for example; I wouldn't call those basic techniques myself. — Jonathan Allan, Jun 24 '19 at 15:41
@user21820 also with the option to "guess and check" aren't all sudoku "easy"? ;p — Jonathan Allan, Jun 24 '19 at 15:49
@JonathanAllan: I'm sure that I didn't make any mistake, and I only used singles and intersection. The point is that any competent solver would not only use fixed techniques, but know when to split into cases. In this case, I used just one binary split at a point I believed to be useful, and I could easily check both cases. There are much harder puzzles than that. For example, try this one generated by a program of mine many years ago: 4---1---8---2---6---3---14--8---3---5---7---4---46--2---13--9---5---1---6---27--3. — user21820, Jun 24 '19 at 16:01
@JonathanAllan: My guess is that the graders you used were programmed to first search for a solution that only involves some set of fixed techniques, and if so then classify its difficulty according to which techniques from that set were used. They would therefore fail to find easy solutions that involve just 1 or 2 case-splits if they have already found one using the techniques. The more complicated techniques in their set, the worse this issue gets. — user21820, Jun 24 '19 at 16:34
@user21820, See Most objective online linkable sudoku grader? — agc, Jun 25 '19 at 12:55

score 12 · Answer 2 · answered Jun 22 '19 at 20:09

12

Yes, it's completely possible that two Sudoku puzzles with disjoint clues have the same solution.

The two puzzles below:

123|456| 89       |   |7  
4 6|7 9|12      5 | 8 |  3
78 | 23|4        9|1  | 56
---+---+---    ---+---+---
 3 |567|       2 4|   |891
567|8  |          |  1|234
891|   |5 7       |234| 6 
---+---+---    ---+---+---
34 |  8|9        5|67 | 12
6  | 1 | 4      78|9 2|3 5
  2|   |       91 |345|678

both have the same (unique) solution, but share no clues in the same positions.

answered Jun 22 '19 at 20:09

Deusovi

146,248
16
519
609

2

I wonder what the maximum number of disjoint clue-sets that determine the same solution is. Obviously no bigger than floor(81/17)=4, given that 17 is the minimum number of clues to make a unique solution; I bet 3 is easy but 4 might be difficult or impossible. (On the handwavy grounds that 81 is nearly 5*17, my guess is that 4 is possible.) – Gareth McCaughan Jun 22 '19 at 22:19
1

Interesting. That example is in the right direction, but the clue-sets, (at 41 and 40 clues apiece), contradict the word minimal in the question title. With 41 clues, it's hardly what anyone would think of as a sudoku at all. The answer should also note the method (not necessarily the details) of determining that each clue-set is soluble. – agc Jun 22 '19 at 23:18
@agc Each of these has a single solution - i.e. they are both what are termed "proper sudoku". – Jonathan Allan Jun 22 '19 at 23:28
5

@agc Making these sudokus minimal is left as an exercise to the reader. – Alex F Jun 23 '19 at 00:12
9

@agc "it's hardly what anyone would think of as a sudoku at all"? They both seem like perfectly fine Sudoku puzzles to me (if a bit easy). But you can also make them minimal by just removing clues until you can't remove any more without losing uniqueness -- that part isn't really a constraint on the clues. If there are nonminimal examples, then there are minimal ones. – Deusovi Jun 23 '19 at 01:22
@GarethMcCaughan, See Maximum number of disjoint clue-sets that determine the same Sudoku solution? – agc Jun 25 '19 at 12:12

Do sudoku answers always have a single minimal clue set?

2 Answers2

Linked