The "n digits sharing n cells" principle

Advanced methods and approaches for solving Sudoku puzzles

The "n digits sharing n cells" principle

Postby Jeff » Sun Nov 20, 2005 5:01 pm

This could be a new technique. Please correct me if I am wrong.

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, naked triple, naked quad etc., provided that there are no contradictions resulted from the reduced combinations.

For example, in a row with 4 digits sharing 4 cells (naked quad):
If one cell is solved, then the row will be reduced to a naked triple.
If 2 cells are solved, then the row will be reduced to a naked pair.

Deductions can be made by examining all possible combinations of naked subsets in a row, column or a box and checking for contradictions.

Code: Select all
Consider the following row with 4 unsolved cells:

+------------------+-----------------+---------------+                 
| 2     8     1    | 47    9    35   | 357   345   6 |
+------------------+-----------------+---------------+

The unsolved cells are 47-35-357-345

According to the "n digits sharing n cells" principle, the next reduced combination of naked subset is a naked pair with 2 unique digits. (a naked triple with 1 unique digit is not possible)

One of the possible naked pairs is r1c6=35 and the 35 content of r1c7. This makes the 7 in that cell redundant and it may be concluded that r1c7<>7.

One of the possible naked pairs is r1c6=35 and the 35 content of r1c8. This makes the 4 in that cell redundant and it may be concluded that r1c8<>4.

Checking for contradiction:

r1c7<>7 => r1c4=7, r1c6=35, r1c7=35 and r1c8=4
r1c8<>4 => r1c4=4, r1c6=35, r1c7=7 and r1c8=35

Multiple solutions, therefore there is no conclusion. 

This example happened to have demonstrated a contradiction, namely multiple solutions. Please refer to Nick70's thread for workable examples.
Last edited by Jeff on Mon Nov 21, 2005 2:50 am, edited 5 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: The "n digits sharing n cells" principle

Postby ChrisT » Sun Nov 20, 2005 5:22 pm

Jeff wrote:r1c8<>8 => r1c4=7, r1c6=35, r1c7=7 and r1c8=35 (contradiction)


I don't follow this line. Presumably r1c8<>8 is a misprint, but I can't think what it should read.
ChrisT
 
Posts: 36
Joined: 16 October 2005

Re: The "n digits sharing n cells" principle

Postby Jeff » Sun Nov 20, 2005 5:33 pm

ChrisT wrote:
Jeff wrote:r1c8<>8 => r1c4=7, r1c6=35, r1c7=7 and r1c8=35 (contradiction)


I don't follow this line. Presumably r1c8<>8 is a misprint, but I can't think what it should read.

Sorry, I made an error. There is no conclusion for this example. Original post edited.:(
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby hrcjcr » Sun Nov 20, 2005 5:47 pm

I like the trend in this thinking, but agree that in this example, multiple solutions are possible, and hence no conclusion.
hrcjcr
 
Posts: 19
Joined: 19 November 2005

Postby Jeff » Sun Nov 20, 2005 5:58 pm

I think it is just a bad example. I gather that if there was no contradiction, then a deduction could be made as shown in Nick70's thread.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: The "n digits sharing n cells" principle

Postby Shazbot » Sun Nov 20, 2005 10:46 pm

Jeff wrote:For example, in a row with 4 digits sharing 4 cells (naked quad):
If one cell is solved, then the row will be reduced to a naked triple.
If 2 cells are solved, then the row will be reduced to a naked pair.


I'm not sure that's accurate. I think it depends on which of the 4 cells is solved. For example, in your original row:
Code: Select all
+------------------+-----------------+---------------+                 
| 2     8     1    | 47    9    35   | 357   345   6 |
+------------------+-----------------+---------------+


if r1c7 were solved to 3, you'd be left with a series of naked singles (r1c6 would be 5, reducing r1c8 to 4 and finally r1c4 to 7).

However, if r1c4 were reduced to 4, you'd have a hidden single (7) at r1c7, leaving a naked pair (35) at r1c6 and r1c8.

Perhaps it depends on how many candidates are in the cell you solve first - I suspect there may be some mathematical equation concerning the number of cells with candidates in your group and the number of candidates in the cell you solve. But it's WAY too early in the morning for me!:)

You'd have to see the rest of the grid to be able to start your reductions and avoid multiple solutions.
Shazbot
 
Posts: 220
Joined: 24 September 2005

Re: The "n digits sharing n cells" principle

Postby Jeff » Mon Nov 21, 2005 6:46 am

Shazbot wrote:Perhaps it depends on how many candidates are in the cell you solve first - I suspect there may be some mathematical equation concerning the number of cells with candidates in your group and the number of candidates in the cell you solve. But it's WAY too early in the morning for me!:)

You'd have to see the rest of the grid to be able to start your reductions and avoid multiple solutions.


At present, the only safeguard against a wrong deduction is by examining all possible cascaded naked subsets combinations and checking to see if there are any contradictions.
Jeff
 
Posts: 708
Joined: 01 August 2005


Return to Advanced solving techniques