I am attempting a classification of the proofs that have been used, based on the contradictions with minimality that they use.
I hope it can give us a better idea of how to prove non-minimality of other patterns.
The simplest one, proof by a hidden single (demonstrated on one of the original non-minimal patterns found by Mauricio):
- Code: Select all
. . . | . . . | . . .
. . . | . x . | . . .
. . . | . . . | . . .
-------+-------+-------
. . . | x . x | . . .
. . . | x . x | . . .
. . . | x . x | . . .
-------+-------+-------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
Let
a be the digit given in r2c5. In b5,
a is forced into the given cells. Deleting the given of
a in b5 will make it a hidden single, therefore it is redundant and the pattern is non-minimal.
Similarly, we can use naked singles (but AFAIK this cannot prove a pattern non-minimal by itself):
- Code: Select all
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|x x x|. . .|
|. . .|x . x|. . .|
|. . .|x x x|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
Let
a be the digit not given in b5. If
a were given anywhere in b2468, any given in b5 seen by the
a given would be redundant, as its cell would be a naked single.
With eight givens in a line, the missing digit cannot be given anywhere in the grid (as it makes one of the givens redundant or eliminates the last candidate from the non-given cell).
We can use fish patterns:
With a set of given cells, if the absence of a digit from these cells would result in a m\m-1 fish on that digit, that digit must appear at least twice within that set of givens.
Proof: One appearance is required for a solution, therefore would be redundant as a given when other cells of the set are filled with other digits.
Demonstration on a pattern I came up with:
- Code: Select all
+-----+-----+-----+
|x x x|x . x|. . .|
|. . .|. . .|. . .|
|x x x|x . x|. . .|
+-----+-----+-----+
|. . .|x x x|. . .|
|. . .|x . x|. . .|
|. . .|x x x|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
Let
a be the digit not given in b5. There is a fish
ab125\r2c5 + given cells in b12. Therefore
a must be given at least twice in these boxes.
It can only be given once in b1, hence it must be given in b2, which is a contradiction with the naked single argument above. This pattern is non-minimal.
We can use the generalisation of fish, multifish, as well.
In this case the individual fish creating the multifish are way more significant then they are when solving a sudoku (demonstrated on a pattern by Mauricio):
- Code: Select all
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+
Every digit
a has the fish
ab28\c5 + givens in b28, hence each of them must appear in them at least twice. That makes 18 givens which must be placed inside 12 cells, ie. a contradiction (as there can only be one given in each cell). The pattern is non-minimal.
I have a few patterns that came from a discussion with JCO where we were trying to extend the argument I had for my previous pattern.
I will post them once I check if they contain smaller non-minimal patterns that can be proven with the multifish argument.
Marek
