Friday 16 October 2015

Do sudoku answers always have a single minimal clue set?



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

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...