Is there a simpler way to solve this?

Advanced methods and approaches for solving Sudoku puzzles

Postby Nick70 » Sun Nov 27, 2005 1:07 pm

If we look at this earlier example
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

It has already been observed that if r5c8=2, the three trivalue cells are forced in a BUG state, and no other cells are affected, so r5c8 must be 4 and the puzzle is solved.

However, we can also apply the principle discovered by Myth Jellies.

By the BUG principle, we can say that at least one of the following is true: r5c1=2, r4c8=2, r6c8=2.

If r5c1=2, then r4c8=12 and r6c8=12
If r4c8=2, then r5c1=28 and r6c8=14
If r6c8=2, then r5c1=28 and r4c8=13

Therefore r5c1 can be reduced to 28, causing a naked pair in box 4 which reduces the puzzle to the following:
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

At this point we can apply the BUG principle to the only trivalue cell left, r4c8, saying that it must be 2, and the puzzle is solved.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Nick70 » Sun Nov 27, 2005 2:42 pm

Here is a position with two trivalue cells where the BUG principle isn't directly applicable.
Code: Select all
1    24   3     | 24   5    6     | 79   78   89
48   5    7     | 3    49   89    | 1    6    2
6    28   9     | 7    12   18    | 4    5    3
----------------+-----------------+----------------
9    7    2     | 5    8    4     | 3    1    6
5    6    18    | 29   3    19    | 28   4    7
3    48   148   | 6    12   7     | 28   9    5
----------------+-----------------+----------------
7    1    6     | 89   49   3     | 5    2    48
48   3    5     | 1    6    2     | 79   78   489
2    9    48    | 48   7    5     | 6    3    1

The BUG princple tells us that either r6c3=8 or r8c9=8, or both.
However, there doesn't seem to be an immediate way to tie the two possibilites.
Nick70
 
Posts: 156
Joined: 16 June 2005

not both

Postby bennys » Sun Nov 27, 2005 4:50 pm

You cant have both r6c3=8 and r8c9=8
r6c3=8 =>r9c3<>8 =>r8c1=8
r8c9=8 =>r8c1<>8
bennys
 
Posts: 156
Joined: 28 September 2005

Postby Myth Jellies » Sun Nov 27, 2005 6:39 pm

For Nick70's puzzle, the most direct path between the two poly-valued cells is via box 7.

If you just chronicle the effects of the box 7 cells directly on the poly-valued cells you end up with the union of possiblities equalling what you started out with. Perhaps we should leave it at that.

However, if you allow the box 7 cells to ripple up to the tri-valued cells via the other cells in the row or column channel, you can eliminate a candidate in both of them. Actually both cells end up being the union of 8 and 4, or 48. I'm not sure how legitimate this move is, though. I would think it should be allowed since it takes the same path to the target, just using different cells in the house to get there. This is similar to the (8, 9) vs (8, 89) case posted earlier, only this one does have an effect on the final unions.

Of course, assigning 48 to the trivalued cells successfully solves the puzzle, or I wouldn't bother bringing it up.

EDIT: I am not worried about the veracity of the result. One of your starting points was the actual solution, so you are guaranteed to have the solution in the unions of your cells no matter how restrictive the path you take is to get there. My worry is about how things start looking more like T&E as you go along. That's why I prefer the shortest path where you can pretty much eyeball the result.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Nick70 » Sun Nov 27, 2005 8:46 pm

Myth Jellies wrote:However, if you allow the box 7 cells to ripple up to the tri-valued cells via the other cells in the row or column channel, you can eliminate a candidate in both of them.

Actually I can't see the reduction in r6c3, but I can see that

r6c3=8=>r8c1=8=>r8c8=7=>r8c7=9=>r8c9=48

and that's enough to move forward so I'm happy with it. After that you have to apply the BUG principle again to remove the other trivalue cell.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Myth Jellies » Sun Nov 27, 2005 9:41 pm

Nick70 wrote:Actually I can't see the reduction in r6c3, but I can see that

r6c3=8=>r8c1=8=>r8c8=7=>r8c7=9=>r8c9=48

It is more like this:

(r6c3=8)=>(r8c1=8)=>(r8c8=7)=>(r8c7=9)=>(r8c9=4)
OR
(r8c9=8)=>(r9c3=8)=>(r5c3=1)=>(r6c3=4)

therefore

r8c9=48
AND
r6c3=48
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Nick70 » Sun Nov 27, 2005 10:41 pm

Thanks, I had missed the step through r5c3.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Jeff » Mon Nov 28, 2005 5:10 am

Myth Jellies wrote:It may very well be that this type of ORing logic is what we are supposed to be doing whenever we have more than one poly-valued cell and a BUG in the candidates. It works for the others (of course their answers were synchronized so that one implied the other, i.e. both were true.)

Sorry, my response was too rush. The back substitution (o-ring) is very valid indeed, well done.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Mon Nov 28, 2005 6:51 am

1) I'm not sure if has been spelled out, but when applying this tactic, all you have to do is see which candidate appears 3 times in the row, column or box including the tri-value cell -- that's the number that will correctly fill this cell. This makes this the easiest advanced tactic ever discovered.

2) I'm falling behind in examining all the posts in this thread carefully.

3) If this thread cannot be renamed to something more useful, maybe a new thread should be started?

Here's a triple tri-value BUG that works logically:

Code: Select all
 . . . | 6 . . | 3 . .
 . . . | 4 . . | . 9 8
 3 8 . | . . 9 | 7 . .
-------+-------+------
 . 1 5 | . 7 . | . . .
 9 . . | 5 . 6 | . . 7
 . . . | . 4 . | 6 3 .
-------+-------+------
 . . 4 | 8 . . | . 7 6
 5 6 . | . . 4 | . . .
 . . 9 | . . 3 | . . .



After many advanced tactics:

Code: Select all
 
 4 9 . | 6 . . | 3 5 2
 . 5 6 | 4 3 . | 1 9 8
 3 8 . | . 5 9 | 7 6 4
-------+-------+------
 6 1 5 | 3 7 . | 4 . 9
 9 4 3 | 5 . 6 | . 1 7
 . . 8 | 9 4 1 | 6 3 5
-------+-------+------
 1 3 4 | 8 . 5 | . 7 6
 5 6 . | . . 4 | . . 3
 8 . 9 | . 6 3 | 5 4 1
 


Code: Select all
  4    9    17   | 6    18   78   | 3    5    2 
  27   5    6    | 4    3    27   | 1    9    8   
  3    8    12   | 12   5    9    | 7    6    4 
 ----------------+----------------+-------------
  6    1    5    | 3    7    28   | 4    28   9 
  9    4    3    | 5    28   6    | 28   1    7 
  27   27   8    | 9    4    1    | 6    3    5 
 ----------------+----------------+-------------
  1    3    4    | 8    29   5    | 29   7    6 
  5    6    27   | 127  129  4    | 289  28   3 
  8    27   9    | 27   6    3    | 5    4    1 


At this point, there is an X-wing in 2s at r57c57 followed either by coloring in 2s or "standard" BUG, however ...

BUG says that at LEAST one of the three tri-value cells in row 8 must be 2 (as there are 3 cells with candidate 2's in columns 4, 5 and 7), therefore the 2's in r8c38 may be eliminated, saving a step and obviating the need for coloring -- in otherwords, this is the easier way to go.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Jeff » Mon Nov 28, 2005 9:14 am

tso wrote:1) I'm not sure if has been spelled out, but when applying this tactic, all you have to do is see which candidate appears 3 times in the row, column or box including the tri-value cell -- that's the number that will correctly fill this cell. This makes this the easiest advanced tactic ever discovered.

Well done for discovering another tactic making use of the BUG principle.

BUG has made the uniqueness rectangle looks like a subset. A BUG is very easy to identify too. All you have to do is to make sure that a candidate does not appear more than twice in a unit.:D

Now, the challenge is to apply the BUG principle over a larger matrix of unsolved cells, and perhaps merge the findings with the uniqueness rules being discussed in the other thread.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Mon Nov 28, 2005 9:51 am

tso wrote:3) If this thread cannot be renamed to something more useful, maybe a new thread should be started?

A new thread has been started. Let me know if the title is appropriate so that adjustment could be made.
Jeff
 
Posts: 708
Joined: 01 August 2005

Previous

Return to Advanced solving techniques