The New Sudoku Players' Forum

[dobrichev]

Hi,

Maybe it is time to claim a new solving technique.
Any morph of the following 4-template is invalid because it cannot be completed to a valid sudoku solution grid.

Code: Select all

... .12 .34
.13 4.. 2..
.42 3.. 1..

.21 .34 ...
3.. 1.. .42
4.. 2.. .13

.34 ... .21
1.. .23 4..
2.. .41 3..


Now seriously.
The existence of this template is fact, but for me it is far not obvious why there are 119 503 485 essentially different completable 4-templates, built by joining valid 1-templates, and only one invalid.
Its existence could be cause or effect of some still undiscovered symmetries/asymmetries of the sudoku space.

For the first time I posted this template here.

I am curious whether this template appears in the discussed solving process.

Cheers,
MD

[David P Bird]

MD, for a simple proof that your template is impossible: it's easy to show that r1c47, r4c14 and r7c17 must contain six different digits as any legitimate placement of the same digit in any two of these cells would exclude it completely from one of the boxes 1,5, & 9 - correction - boxes 1,6, & 8. However there are only five different digits still available.

DPB

[ronk]

it's easy to show that r1c47, r4c14 and r7c17 must contain six different digits as any legitimate placement of the same digit in any two of these cells would exclude it completely from one of the boxes 1,5, & 9. However there are only five different digits still available.

Good show, except I think you mean boxes 1, 6 & 8.

[David P Bird]

Good show, except I think you mean boxes 1, 6 & 8.

Yes drat it! - I seem to be incapable of getting anything right first time nowadays.

[dobrichev]

Impossibility to complete this template is not in question.
The ratio 119 503 485 completable : 1 incompletable is my point.

What I did.
Take any of the possible 1-templates. Assign value "1" to the givens.
Join it to all non-intersecting templates, assign "2" to givens in second template, min-lex them, and you have a list of 181 2-templates. All they can be completed to valid solution grids.
Join the 2-templates in the same way to one more non-intersecting template. The result is 259,272 3-templates, all completable to valid solution grids.
Do the same once again, and ... surprise - one of the 119,503,486 4-templates is not completable, the rest are.

[ronk]

Impossibility to complete this template is not in question.
The ratio 119 503 485 completable : 1 incompletable is my point.
...
Do the same once again, and ... surprise - one of the 119,503,486 4-templates is not completable, the rest are.

If this were extended to canonicalized 5-templates, would there be more incompletables?

[David P Bird]

I believe the impossibility proof I gave extends to combination templates with more than 4 digits. If three diagonal boxes have orthogonal rectangles of filled cells then there are restrictions regarding the three 'diagonal' cells in these boxes – those which are on different rows and columns to the filled rectangles. I think that if there are five digits in the templates then two of the three diagonal cells must be filled, and for six or more digits they must all be filled.

Clearly as the number of digits included in the templates increases, so will the number of boxes holding qualifying rectangles.

[daj95376]

Any morph of the following 4-template is invalid because it cannot be completed to a valid sudoku solution grid.

Code: Select all

... .12 .34
.13 4.. 2..
.42 3.. 1..

.21 .34 ...
3.. 1.. .42
4.. 2.. .13

.34 ... .21
1.. .23 4..
2.. .41 3..


Thanks MD,

Ever since I encountered this thread, I've always wondered how many disjoint templates, N, could be selected and still be certain that 9-N disjoint templates remain to complete a solution grid. I'd always thought the answer was N=4, but I now see that N=3 is the correct answer.

Regards, Danny A. Jones

[eleven]

I am curious whether this template appears in the discussed solving process.

The ratio 119 503 485 completable : 1 incompletable is my point.

I cant see, what you are out for. Obviously this template is extremely exotic, but does that need an explanation ?
It is easy to generate puzzles, which have this template as option, mostly it is destroyed by singles early. These 2 have it after basics (found in 30 min):

Code: Select all

..7..2.3...349.2...42...1.8.21.3.......1.....48..6.....3.....2.1....34...9.84....
......9.4..348.........617.62.5.4.......7.6....9..8..3.3.....2.1.6...4..........5

[denis_berthier]

r1c47, r4c14 and r7c17 ... any legitimate placement of the same digit in any two of these cells would exclude it completely from one of the boxes ... 1,6, & 8

errr .... it's easy to show for each of the 30 possible combinations of pairs of cells.
Am I missing a simpler proof?

[denis_berthier]

Its existence could be cause or effect of some still undiscovered symmetries/asymmetries of the sudoku space.

About "still undiscovered" : the definition of Sudoku doesn't leave much liberty for finding other symmetries than those in the obvious well known Sudoku symmetry group.
Moreover, as your template remains impossible under all the changes via this symmetry group, the question I'd rather ask is: is this impossibility a consequence of the symmetry group itself? (Dealing with this would suppose all the notions at work in the templates can be expressed only in terms of the symmetry group; I haven't checked). I don't know if this is worth investigating.

The ratio 119 503 485 completable : 1 incompletable is my point.

I agree that this is surprising.

On the other hand, work with Sudoku has accustomed us to exceptional cases:
- there are fewer than 1 minimal in 10,000,000 that can't be solved by T&E
- in the subset of those that can, there is an extremely small proportion that can't be solved by B6-braids (actually only 2 in the known lists)
- there are only a handful with SER 9.9

[David P Bird]

r1c47, r4c14 and r7c17 ... any legitimate placement of the same digit in any two of these cells would exclude it completely from one of the boxes ... 1,6, & 8

errr .... it's easy to show for each of the 30 possible combinations of pairs of cells.
Am I missing a simpler proof?

Code: Select all

... .12 .34
.13 4.. 2..
.42 3.. 1..

.21 .34 ...
3.. 1.. .42
4.. 2.. .13

.34 ... .21
1.. .23 4..
2.. .41 3..

Denis I'm no mathematician but here's how I saw it: Because of symmetry we only need to try one first cell, and three legitimate second cells to realise that at least one of the listed boxes can't hold the focus digit. I'm sorry I didn't formulate that well enough for you.

Is that what you were trying to query, or have you a superior proof?

BTW didn't you mean to say 15 combinations?

[denis_berthier]

r1c47, r4c14 and r7c17 ... any legitimate placement of the same digit in any two of these cells would exclude it completely from one of the boxes ... 1,6, & 8

errr .... it's easy to show for each of the 30 possible combinations of pairs of cells.
Am I missing a simpler proof?

Code: Select all

... .12 .34
.13 4.. 2..
.42 3.. 1..

.21 .34 ...
3.. 1.. .42
4.. 2.. .13

.34 ... .21
1.. .23 4..
2.. .41 3..

Denis I'm no mathematician but here's how I saw it: Because of symmetry we only need to try one first cell, and three legitimate second cells to realise that at least one of the listed boxes can't hold the focus digit. I'm sorry I didn't formulate that well enough for you.

Is that what you were trying to query, or have you a superior proof?

No, I just wondered if there was a simpler proof than trying all the combinations.
I hadn't noticed the symmetries of the pattern itself.
Thanks.

BTW didn't you mean to say 15 combinations?

yes, 15

[daj95376]

Since I missed everyone else's explanation, I had to find my own explanation (using David's cells).

Code: Select all

 I used eleven's assignments of r1c4=8 and r1c7=9.
 They force r4c7=8, r7c4=9, and leave the following grid.
 *-----------------------------------------------------------------------*
 |  567    567    567    |  8      1      2      |  9      3      4      |
 |  89     1      3      |  4      5679   5679   |  2      5678   5678   |
 |  89     4      2      |  3      5679   5679   |  1      5678   5678   |
 |-----------------------+-----------------------+-----------------------|
 |  567    2      1      |  567    3      4      |  8      5679   5679   |
 |  3      56789  56789  |  1      56789  56789  |  567    4      2      |
 |  4      56789  56789  |  2      56789  56789  |  567    1      3      |
 |-----------------------+-----------------------+-----------------------|
 |  567    3      4      |  9      5678   5678   |  567    2      1      |
 |  1      56789  56789  |  567    2      3      |  4      56789  56789  |
 |  2      56789  56789  |  567    4      1      |  3      56789  56789  |
 *-----------------------------------------------------------------------*


No matter which value is chosen for r4c1, it forces cells r7c56 for [r7] and r89c4 for [c4] to be true for the value. A clear contradiction ... and possibly David's observation!

Code: Select all

 *-----------------------------------------------------------------------*
 |  567    567    567    |  8      1      2      |  9      3      4      |
 |  89     1      3      |  4      5679   5679   |  2      5678   5678   |
 |  89     4      2      |  3      5679   5679   |  1      5678   5678   |
 |-----------------------+-----------------------+-----------------------|
 | +567    2      1      | -567    3      4      |  8     -5679  -5679   |
 |  3      56789  56789  |  1      56789  56789  | +567    4      2      |
 |  4      56789  56789  |  2      56789  56789  | +567    1      3      |
 |-----------------------+-----------------------+-----------------------|
 | -567    3      4      |  9     +5678  +5678   | -567    2      1      |
 |  1      56789  56789  | +567    2      3      |  4      56789  56789  |
 |  2      56789  56789  | +567    4      1      |  3      56789  56789  |
 *-----------------------------------------------------------------------*


[denis_berthier]

Since I missed everyone else's explanation, ...

Symmetries imply that the remaining 5 numbers can be interchanged. So that you can fix e.g. the first row: 567812934
Whipping this, we get:
whip[1]: b8n8{r7c5 .} ==> r7c7 <> 8
whip[1]: c7n8{r4 .} ==> r4c8 <> 8, r4c9 <> 8
whip[1]: b8n8{r7c6 .} ==> r7c1 <> 8
whip[1]: b6n9{r4c9 .} ==> r4c1 <> 9, r4c4 <> 9
whip[1]: c4n9{r9 .} ==> r7c6 <> 9, r7c5 <> 9
whip[1]: b1n9{r2c1 .} ==> r7c1 <> 9
hidden-single-in-a-row ==> r7c4 = 9
whip[1]: b1n8{r2c1 .} ==> r4c1 <> 8
hidden-single-in-a-row ==> r4c7 = 8
whip[2]: c1n6{r4 r7} - b8n6{r7c6 .} ==> r4c4 <> 6
whip[1]: c4n6{r9 .} ==> r7c6 <> 6, r7c5 <> 6
whip[2]: r7n6{c7 c1} - r4n6{c1 .} ==> r6c7 <> 6
whip[2]: c7n6{r7 r5} - r4n6{c8 .} ==> r7c1 <> 6
singles ==> r7c1 = 7, r4c1 = 6, r5c7 = 6
GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR RN-CELL r7n6