15
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A few pictures would probably help. $\endgroup$ – agc Jun 22 at 19:47
  • 2
    $\begingroup$ What does "and started from a minimal set of clues" mean? $\endgroup$ – Jonathan Allan Jun 22 at 20:21
  • 2
    $\begingroup$ @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. $\endgroup$ – agc Jun 22 at 23:39
  • $\begingroup$ @agc So that's a local minimum for that particular puzzle? $\endgroup$ – Rosie F Jun 23 at 6:09
  • 2
    $\begingroup$ @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). $\endgroup$ – Sriotchilism O'Zaic Jun 23 at 13:02
35
$\begingroup$

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)
$\endgroup$
  • 1
    $\begingroup$ The diagram looks very pretty. +1 :) $\endgroup$ – Feeds Jun 23 at 4:30
  • $\begingroup$ 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? $\endgroup$ – val Jun 23 at 13:54
  • $\begingroup$ You could also have run your Python code on the previously posted disjoint set from Deusovi to make two disjoint irreducible sudoku. $\endgroup$ – Cœur Jun 23 at 15:30
  • $\begingroup$ @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). $\endgroup$ – Jonathan Allan Jun 23 at 18:35
  • $\begingroup$ 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. $\endgroup$ – user21820 Jun 24 at 15:28
12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – Gareth McCaughan Jun 22 at 22:19
  • 1
    $\begingroup$ 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. $\endgroup$ – agc Jun 22 at 23:18
  • $\begingroup$ @agc Each of these has a single solution - i.e. they are both what are termed "proper sudoku". $\endgroup$ – Jonathan Allan Jun 22 at 23:28
  • 5
    $\begingroup$ @agc Making these sudokus minimal is left as an exercise to the reader. $\endgroup$ – Alex F Jun 23 at 0:12
  • 8
    $\begingroup$ @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. $\endgroup$ – Deusovi Jun 23 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.