From the Desk of Richard J. Runion
Chieftain
Sudoku Village
http://www.SudokuVillage.com

This is a ‘free for all’ Sudoku page. Anything related to ‘Sudoku‘ goes here, in this category. (Other than, of course, what’s covered in the other specific Categories).

Tip 20. Possibility Matrix Method: Tie Breaker Rule

This is a rule you can apply when you’re no longer able to apply any of the other rules. This rule is sure to solve any Sudoku for you, however difficult. However, applying this rule could be cumbersome, in very difficult cases.

Let’s say this is the Sudoku we want to solve:

We’ve reached the following position, after creating the Possibility Matrix, and applying the PM rules iteratively, and applying Reduction and Group Reduction, iteratively:

At this stage, any application of any of the rules doesn’t solve the puzzle any more.

Now, we apply the Tie Breaker Rule.
Let’s assume (1,5) -> 7.

This resolves to give a wrong solution; e.g., Column 5 has two ‘8’s and no two. So, we need to discard this possibility of (1,5) -> 7.]

Let’s now assume (1,5) -> 8, the only other possible value for this cell.

We check and see that we get the right solution, by checking to see if it obeys the rules of the game we’d mentioned initially. (i.e., we should have 1 to 9 in each row, column, and major square, with no repetitions.)

This is how we apply the Tie Breaker Rule to solve any puzzle. If after an assumption, we are not able to resolve the given puzzle completely, we may have to superimpose another similar assumption. If that doesn’t work, one more, and so on, till we get a solution. Normally, such situations don’t arise.

Generally, it will be a good idea to apply the Tie Breaker to a Cell where there are fewer possible values (2 possible values, to begin with, as we have, in the above case).

Tip #19. Possibility Matrix Method: Iterative application of Reduction and Group Reduction Rules

This involves just repetitive application of Tips #17 and #18, one after the other. That is, when you’re no longer able to apply Tip #17, try applying Tip #18; you may be able to resolve some Cells, or you may at least eliminate a few possibilities in the Possibility Matrix. Now, if you try applying Tip #17, you may be able to resolve some Cells, or you may at least eliminate a few possibilities in the Possibility Matrix.

Keep applying these two rules till you solve the puzzle completely. If the puzzle doesn’t get solved still, at least reach the point where any more application of these two rules does not resolve any more Cells, nor eliminates any few possibilities in the Possibility Matrix.

Tip 18. Possibility Matrix Method: Group Reduction Rule

The Reduction Rule of the Possibility Matrix Method is the same as: ‘Tip #9. Hidden Groups Approach’ of the Conventional Method.

Let’s see a simple example:

The values 1, 7, and 8 must be shared between the 3 Cells (4,3), (7,3) and (9,3) only. So, eliminating these values from the other Cells, we now have:
(2,3) -> {2,6}
(5,3) -> {3,5}
(6,3) -> {2,3}
(8,3) -> {5,6}

Let’s now see a more difficult example:

Now, don’t focus on the values, which are so many, but on a few specific Cells that can’t take any values other than a small set.
(2,1) -> {1,5}
(2,3) -> {4,5}
(3,3) -> {1,4}

We see that the values 1, 4 and 5 MUST BE shared ONLY within these 3 Cells.

So, remove these 3 values from the other Cells.

We have
(1,1) -> (2,6)
(1,2) -> (2,3)
(2,2) -> (6,7)
(3,1) -> (3,7)

Tip #17. Possibility Matrix Method: Reduction Rule

The Reduction Rule of the Possibility Matrix Method is the same as the combination of ‘Tip #7. Reduction Approach’ of the Conventional Method.

Let’s try to see how far we’re able to solve the puzzle we saw last, using the Reduction Rule.

1. (1,1) -> {7,9}; (1,3) -> {3,4,9}; (1,7}-> {3,7}; (1,9) -> {4,7}

Can you try the rest of it? It’s all so simple, though you have to go through many steps.

Check if you get this answer?

Tip #16. Possibility Matrix Method: Constructing the Possibility Matrix (PM)

Let’s take a typical Sudoku, like this one:

Let’s try to fill in all the possible values that the blank Cells can take. Do you want to go from left to right, top to bottom? (You can go in any order you like.)

Some cells may get completely resolved along the way. This is the initial PM.

Simple, isn’t it?

If you keep repeating the process, you’ll find that some more cells may get resolved, completely or partially, based on some cells that may have got resolved in the previous round. This way, you may either solve the given Sudoku completely, or a few cells may remain unresolved, and any number of iterations of the PM may not help solve them. Thus, you arrive at the final PM.

Tip #15. Trial & Error Approach

When all the approaches we’ve learnt fail, use the Tie Breaker Approach we’d learnt in the Possibility Matrix Method (let’s call it the ‘Trial And Error’ Approach here). ‘Trial And Error’ Approach also helps determine if a puzzle has multiple solutions or any solution at all. This Approach is not an inherent part of the Conventional Method, and that’s why this is not included formally as part of the Method. Most purists call it the ‘Sledge Hammer’ Approach, and refuse to accept it. However, since the Conventional Method doesn’t guarantee results for every Sudoku, you may be forced to borrow this ‘Tie Breaker’ Approach from the Possibility Matrix Method. This Approach also comes in handy when you are unable to proceed (though there may well be a solution without having to resort to this Approach, but you are unable to find it).

In a way, you could say ‘Forcing Chains’ is also part of the ‘Trial And Error’ Approach, because you realize whether a chain forces values or not only thru ‘Trial And Error’. However, in the case of ‘Trial And Error’ Approach, you continue with the trial regardless of whether trials result in resolution or not, whereas the ‘Forcing Chains’ Approach actually helps resolve conflicts successfully without having to try to solve the puzzle completely.

Tip #14. Forcing Chains Approach

If Cell (2, 2) takes the value ‘1′, Cell (2,8) will take ‘2′, Cell (3, 9) will take ‘3′, Cell (8, 9) will take ‘4′ and Cell (8, 2) will take ‘5′. And there are no conflicts.

However, if Cell (2, 2) takes the value ‘2′, Cell (2,8) will take ‘3′, Cell (3,9) will take ‘4′, Cell (8, 9) will take ‘5′ and Cell (8, 2) will take ‘2′. Now there is a conflict. So, this set of values is not right.

So, we are able to deduce that we should go with the assumption that Cell (2, 2) takes the value ‘1′, and fill up the rest of the Cells on this basis.

This is called the ‘Forcing Chains’ Approach

Pattern to look for: A set of values yet to be found following a chain of possibilities across the Table, going thru Rows, Columns and Major Squares in any order. Typically it is possible to resolve only when we go through chains of Cells with 2 possible values in
each Cell, as with more possibilities in some Cells, it will be too complex.

Tip #13. Coloring Approach

Here, we can see that if Cell (2, 3) takes the value ‘5′, Cell (3, 1) can’t; but Cell (3, 7) can, and Cell (2,8) can’t; and nor can Cell (7, 3). And we have a conflict in Cell (7, 7); while it is an alternative to Cell (3, 7) and so it should take a color different from it, it should also take the color alternative to Cell (3, 7) and so it should take a color different from it too. So, we see that Row 7 cannot have a ‘5′ which we need. So, this cannot be the solution.

Let’s look at the alternative solution. If Cell (3, 1) takes the value ‘5′, Cell (2,8) and Cell (7, 3) can take the value ‘5′ too, and our requirements are completely met.

So, we can see how coloring has helped us resolve this conflict. Sometimes, we may not be able to completely resolve such conflicts with this Approach, but we may only be able to eliminate the possibility of some values in certain Cells as we have seen with the previous approaches.

This is called the ‘Coloring Approach’

Pattern to look for: A single value yet to be found following a chain of possibilities across the Table, going thru Rows, Columns and Major Squares in any order, such that some of these possibilities would become impossible in case some of the other possibilities are true.

Tip #12. XY-Wing Approach

Reduces to

This is called the ‘X-Y Wing’ Approach . We have seen only the case of row-column interaction. The same obviously holds true for row-major square interaction and column-major square interaction.

Pattern to look for: Four Cells falling in 2 identical Rows and Columns need 3 prospective values (x, y and z), with the possibilities being {x,y}, {x,z}, {y,z}, and {p,z},. (This is also true of Four Cells falling in 2 identical Rows and Major Squares, OR, in 2 identical Columns and Major Squares).