The New Sudoku Players' Forum

[Nick70]

The other day I reached this position:

Code: Select all

 1    24   3    | 49   5    6    | 7    8    29   
 6    24   7    | 1    49   8    | 25   3    259 
 8    5    9    | 7    3    2    | 6    4    1   
----------------+----------------+----------------
 59   7    8    | 29   6    4    | 25   1    3   
 2    3    6    | 8    1    5    | 4    9    7   
 59   1    4    | 3    29   7    | 8    6    25   
----------------+----------------+----------------
 3    8    5    | 24   24   9    | 1    7    6   
 7    6    1    | 5    8    3    | 9    2    4   
 4    9    2    | 6    7    1    | 3    5    8   

which I find quite interesting. Every cell has only two candidates, except for R2C9. All candidates are strongly linked, except in box 3 where the 3-candidates cell gives some uncertainty.

It is easy to find forcing chains (xy-chains) that solve the puzzle, but I keep wondering if there could be some more obvious way to exploit box 3 and remove the false candidates.

[Jeff]

It is easy to find forcing chains (xy-chains) that solve the puzzle, but I keep wondering if there could be some more obvious way to exploit box 3 and remove the false candidates.

The "n digits sharing n cells" principle can be used to solve the grid as follows:

Code: Select all

 1    24   3    | 49   5    6    | 7    8   <29>   
 6   <24>  7    | 1   <49>  8    |<25>  3   <259> 
 8    5    9    | 7    3    2    | 6    4    1   
----------------+----------------+----------------
 59   7    8    | 29   6    4    | 25   1    3   
 2    3    6    | 8    1    5    | 4    9    7   
 59   1    4    | 3    29   7    | 8    6   <25>     
----------------+----------------+----------------
 3    8    5    | 24   24   9    | 1    7    6   
 7    6    1    | 5    8    3    | 9    2    4   
 4    9    2    | 6    7    1    | 3    5    8     

According to the "n digits sharing n cells" principle, all rows and columns can be finally reduced to a combination of naked subsets, ie. naked pair and naked triple etc..

I interpret the state of the game as being that every row and column has a naked pair or a naked bivalue triple where no further reduction is possible, except for row 2 and col 9.

Code: Select all

If row 2 is to be further reduced, it will take up one of the following combinations:

A naked triple and a unique digit - In this case, the only possible naked triple is r2c2=24, r2c5=49 and the 29 content of r2c9. This makes the 5 in that cell redundant and it may be concluded that due to this naked triple r2c7<>2 => r2c7=5.

A naked pair and 2 unique digits - In this case, the only possible naked pair is r2c7=25 and the 25 content of r2c9.  This makes the 9 in that cell redundant and it may be concluded that due to this naked pair r2c2<>2 => r2c2=4.

Two naked pairs - Not possible.

As there are no contradictions, each of the above deductions can complete the grid. 

Alternatively, from the 2 deductions above it can be concluded that r2c9<>5  and r2c9<>9, and therefore r2c9=2.

Code: Select all

If col 9 is to be further reduced, it will take up a combination of a naked pair and a unique digit:

One of the possible naked pairs is r1c9=29 and the 29 content of r2c9. This makes the 5 in that cell redundant and it may be concluded that due to this naked pair r6c9=5.

One of the possible naked pairs is r6c9=25 and the 25 content of r2c9. This makes the 9 in that cell redundant and it may be concluded that due to this naked pair r1c9=9.

As there are no contradictions, each of the above deductions can complete the grid. 

Alternatively, from the 2 deductions above it can be concluded that r2c9<>5  and r2c9<>9, and therefore r2c9=2.

[Myth Jellies]

Jeff,

Are you basically saying, that if you let r2c9 = 59, then row 2 would be a naked bivalue quad, and column 9 would be a naked bivalue triple, and thus, with everything reduced to naked bivalue types, there would be multiple solutions to the puzzle? I can see that justification when you take the column and the row together. I am not sure about the justification when you take the row or the column all by itself.

[Myth Jellies]

[post removed because it distracted from Jeff's interesting application.]

[Jeff]

I am not sure about the justification when you take the row or the column all by itself.

I have been thinking about this too. Checking of both intersecting gridlines may be required.

[Added comment later]: Further studies revealed that, provided the grid has an unique solution and all but one unsolved cell are bivalue, then checking of both intersecting gridlines is not required. The grid can be solved by a single run of the technique.

[Myth Jellies]

Jeff,

If this advanced uniqueness theory indicates that r2c9 cannot be 59, then you can just say immediately that r2c9 = 2 and not bother with all the intermediate steps, correct?!!

[Jeff]

Correct, MJ, although I am still trying to figure out if there exists any patten during cascading of naked subsets.

[tso]

Wow, that's easy. Here's one I came across yesterday:

Code: Select all

 1 7 4 | 8 3 2 | 5 9 6
 5 9 3 | 4 6 1 | 2 7 8
 6 8 2 | 9 5 7 | . . 1
-------+-------+------
 . 6 7 | 5 . . | 9 . .
 . 1 9 | 7 . 3 | 6 . 5
 4 3 5 | . 9 6 | 8 . 7
-------+-------+------
 3 . 1 | 6 . . | 7 5 9
 9 . 8 | . 7 5 | . 6 .
 7 5 6 | 3 . 9 | . 8 2


Code: Select all

 
 1    7    4    | 8    3    2    | 5    9    6   
 5    9    3    | 4    6    1    | 2    7    8   
 6    8    2    | 9    5    7    | 34   34   1   
----------------+----------------+----------------
 28   6    7    | 5    12   48   | 9    123  34   
 28   1    9    | 7    48   3    | 6    24   5   
 4    3    5    | 12   9    6    | 8    12   7   
----------------+----------------+----------------
 3    24   1    | 6    28   48   | 7    5    9   
 9    24   8    | 12   7    5    | 13   6    34   
 7    5    6    | 3    14   9    | 14   8    2   


For example, forming a triple in column 8 -- r3=[34], r5=24, r4 must be [23], leaving r6=1 -- which solves the puzzle. I tried several other combinations in the row and column -- they all worked. It's fun to use a tactic before you completely understand why it works -- it seems magical.




Unfortunately, to get to this point in the puzzle above, I had to use a forcing chain to get past this point:

Code: Select all

 1    7    4    | 8    3    2    | 5    9    6   
 5    9    3    | 4    6    1    | 2    7    8   
 6    8    2    | 9    5    7    | 34   34   1   
----------------+----------------+----------------
 28   6    7    | 5    12   48   | 9    123  34   
 248  1    9    | 7    48   3    | 6    24   5   
 24   3    5    | 12   9    6    | 8    124  7   
----------------+----------------+----------------
 3    24   1    | 6    28   48   | 7    5    9   
 9    24   8    | 12   7    5    | 13   6    34   
 7    5    6    | 3    14   9    | 14   8    2 


Can a similar deduction be made safely at this point, or is this tactic strictly for when you have only one cell left with more than 2 candidates? What are the limitations of this tactic, that is, when is it time to look for this?

[Myth Jellies]

tso,

You don't want to worry so much about forming a triple in column 8 as avoiding the column 8 quad (along with the row 4 quint and box 6 quad). If r4c8 = 13, then you end up in this undisireable BUD (bivalue universal death) layout; thus r4c8 must equal 2.

I don't see any useful BUD avoidance possibilities with the three trivalue cells. Perhaps something good could come of it if the cells shared a house, but it seems in that case the technique would be no quicker than finding a forcing chain.

[Jeff]

You don't want to worry so much about forming a triple in column 8 as avoiding the column 8 quad (along with the row 4 quint and box 6 quad). If r4c8 = 13, then you end up in this undisireable BUD (bivalue universal death) layout; thus r4c8 must equal 2.

Forming a triple in column 8 is just another way to avoid the bivalue universal death. It's just as easy to spot.

[Myth Jellies]

Forming a triple in column 8 is just another way to avoid the bivalue universal death. It's just as easy to spot.

While that is true, there is no reason to prefer the choice leading to a triple and a single (23) over the choice leading to a pair and two singles (12). Seems to me the key is recognizing that (13) is an invalid choice and that whatever is left over (2) must contain the solution.

[Jeff]

It seems to me that no matter which mode of recognition is preferred, provided the grid has a unique solution, the pre-requisite is that all but one unsolved cell must be bivalue, thus satisfying the bivalue universal death consideration.

Any idea how to extend the idea to 2 or more non-bivalue cells, such as that in the example posted by Tso?

Code: Select all

1    7    4    | 8    3    2    | 5    9    6   
 5    9    3    | 4    6    1    | 2    7    8   
 6    8    2    | 9    5    7    | 34   34   1   
----------------+----------------+----------------
 28   6    7    | 5    12   48   | 9    123  34   
 248  1    9    | 7    48   3    | 6    24   5   
 24   3    5    | 12   9    6    | 8    124  7   
----------------+----------------+----------------
 3    24   1    | 6    28   48   | 7    5    9   
 9    24   8    | 12   7    5    | 13   6    34   
 7    5    6    | 3    14   9    | 14   8    2 

[Myth Jellies]

Nothing obvious. Anything I might try would start looking a lot like trial and error very quickly. Might be different if the tri-value cells all had a direct link to each other, but that 248 cell is on an island out there.

[Jeff]

......Might be different if the tri-value cells all had a direct link to each other, but that 248 cell is on an island out there.

Code: Select all

 1    7    4    | 8    3    2    | 5    9    6   
 5    9    3    | 4    6    1    | 2    7    8   
 6    8    2    | 9    5    7    | 34   34   1   
----------------+----------------+----------------
 28   6    7    | 5    12   48   | 9    123  34   
 248  1    9    | 7    48   3    | 6    24   5   
 24   3    5    | 12   9    6    | 8    124  7   
----------------+----------------+----------------
 3    24   1    | 6    28   48   | 7    5    9   
 9    24   8    | 12   7    5    | 13   6    34   
 7    5    6    | 3    14   9    | 14   8    2

MJ, your statement above has triggered me to look for a link for the 3 trivalue cells and I found it at r5c8.

Since r5c8=2 will promote a BUG, r5c8 must be 4. And this completes the grid.

[tso]

Here's another example:

Figure (A)

Code: Select all

 3    7    9    | 1    28   26   | 5    68   4
 2    4    8    | 9    57   56   | 3    67   1
 6    5    1    | 37   4    378  | 2    78   9
 ---------------+----------------+------------
 8    6    2    | 4    37   37   | 1    9    5
 1    9    7    | 6    25   25   | 4    3    8
 5    3    4    | 8    9    1    | 7    2    6
 ---------------+----------------+------------
 4    28   5    | 27   6    78   | 9    1    3
 7    18   3    | 5    18   9    | 6    4    2
 9    12   6    | 23   13   4    | 8    5    7


The tactic solves it instantly -- but again, I had to get past this point first:

Code: Select all

 3     7     9     | 1     28    268   | 5     68    4
 2     4     58    | 9     57    5678  | 3     678   1
 6     58    1     | 37    4     3578  | 2     78    9
 ------------------+-------------------+--------------
 8     6     2     | 4     37    37    | 1     9     5
 1     9     7     | 6     25    25    | 4     3     8
 5     3     4     | 8     9     1     | 7     2     6
 ------------------+-------------------+--------------
 4     258   58    | 27    6     78    | 9     1     3
 7     18    3     | 5     18    9     | 6     4     2
 9     12    6     | 23    13    4     | 8     5     7


When I first tried working on this, I didn't fully understand the tactic and tried to apply it to r7c2 -- falsely assuming that being the only tri-value cell in its row, column and box was enough. I tried the tactic several ways -- sometimes it lead to the Figure (A) the top of this post -- but sometimes it lead to a false placement.

For example:

r8c46 form a [278] triple with the 2 and 8 from r7c2, making r7c3 a 5, leading to figure (A)

OR

r89c2 form a [128] triple with the 2 and 8 from r7c2, making r7c3 and r3c2 a 5, leading to figure (A)

Are these two deductions invalid dispite coincidentally giving the correct answer?


If I formed a pair instead of a triple:

r3c2 forms a [58] pair with the 5 and 8 from r7c2. This implies r8c2=1 which is incorrect.

OR

r7c3 forms a [58] pair with the 5 and 8 from r7c2. This implies r8c2=1 and r7c6=7, both of which are false.


I guess this proves that my first deductions were faulty, right?


Here's what I'm thinking -- in the diagram below, bi-value cells are marked with a 'b', tri-value and higher with a '+:

Code: Select all

 .     .     .     | .     b     +     | .     b     .
 .     .     b     | .     b     +     | .     +     .
 .     b     .     | b     .     +     | .     b     .
 ------------------+-------------------+--------------
 .     .     .     | .     b     b     | .     .     .
 .     .     .     | .     b     b     | .     .     .
 .     .     .     | .     .     .     | .     .     .
 ------------------+-------------------+--------------
 .     +     b     | b     .     b     | .     .     .
 .     b     .     | .     b     .     | .     .     .
 .     b     .     | b     b     .     | .     .     .


Though r7c2 is the only tri-value cell in its row, column and box, it is influenced by the cells r3c2 and r7c6, both of which are in a house with other tri-value or greater cells.

What if the situation were slightly different?

Code: Select all

 .     .     .     | .     b     +     | .     b     .
 .     .     b     | .     b     +     | .     +     .
 .     .     .     | b     .     +     | .     b     .
 ------------------+-------------------+--------------
 .     b     .     | .     b     b     | .     .     .
 .     .     .     | .     b     b     | .     .     .
 .     .     .     | .     .     .     | .     .     .
 ------------------+-------------------+--------------
 .     +     b     | b     b     .     | .     .     .
 .     b     .     | .     b     .     | .     .     .
 .     b     .     | b     b     .     | .     .     .


In this case, r7c2 is still the only tri-value cell in its row, column and box BUT none of the other cells in its three houses share a house with another tri-value or greater cell. Would we be able to correctly apply the tactic to r7c2 in this case?