Invalid (incompletable) 4-template(s)

Everything about Sudoku that doesn't fit in one of the other sections

Invalid (incompletable) 4-template(s)

Postby dobrichev » Wed Feb 08, 2012 11:28 pm

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
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Invalid (incompletable) 4-tempate(s)

Postby David P Bird » Thu Feb 09, 2012 9:58 am

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
Last edited by David P Bird on Thu Feb 09, 2012 12:39 pm, edited 1 time in total.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: New Solving Technique (I think)

Postby ronk » Thu Feb 09, 2012 11:48 am

David P Bird wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby David P Bird » Thu Feb 09, 2012 12:34 pm

ronk wrote: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.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: New Solving Technique (I think)

Postby dobrichev » Thu Feb 09, 2012 1:47 pm

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.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: New Solving Technique (I think)

Postby ronk » Thu Feb 09, 2012 3:43 pm

dobrichev wrote: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?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Invalid (incompletable) 4-template(s)

Postby David P Bird » Thu Feb 09, 2012 4:02 pm

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.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Invalid (incompletable) 4-template(s)

Postby daj95376 » Thu Feb 09, 2012 8:40 pm

dobrichev wrote: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
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby eleven » Fri Feb 10, 2012 9:56 am

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

dobrichev wrote: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
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Feb 10, 2012 1:46 pm

David P Bird wrote: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
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Feb 10, 2012 2:10 pm

dobrichev wrote: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.

dobrichev wrote: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
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby David P Bird » Fri Feb 10, 2012 2:57 pm

denis_berthier wrote:
David P Bird wrote: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?
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Invalid (incompletable) 4-template(s)

Postby denis_berthier » Fri Feb 10, 2012 3:02 pm

David P Bird wrote:
denis_berthier wrote:
David P Bird wrote: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.

David P Bird wrote:BTW didn't you mean to say 15 combinations?

yes, 15
Last edited by denis_berthier on Sat Feb 11, 2012 8:06 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby daj95376 » Fri Feb 10, 2012 4:51 pm

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  |
 *-----------------------------------------------------------------------*
Last edited by daj95376 on Fri Feb 10, 2012 5:10 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Feb 10, 2012 5:32 pm

daj95376 wrote: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
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Next

Return to General

cron