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?
Answer
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)
No comments:
Post a Comment