Useful pattern discovery helps problem solving skill enhancement, the first interesting Sudoku game play
After we stopped playing Sudoku games for some time, this is the first game in a new series of interesting Sudoku game play.
This game was posted by one of our friends in erstwhile Google Plus Problem Solving community for solution and it attracted our interest. So there it goes.
As always we will briefly sketch out the strategies and techniques we have learned by ourselves while trying to solve wonderful Sudoku games. This time we will clarify our goals in playing Sudoku in addition.
Our goals in playing Sudoku
The goals are,
- To discover new useful patterns that solve a particular situation in a Sudoku game play
- To move through the whole game play adopting a systematic approach so that surely and smoothly the play moves towards the final solution stage. For this to happen we needed to weave the individual tactics into strategies and strategies into methodology that is flexible enough to cater to Sudoku games of varying hardness.
- To enjoy the game play not paying particular attention to how fast we reach the solution.
To be noted that we are not Sudoku experts or theorists. Just that, we recognize the great potential of Sudoku to keep the mind fresh and its potential as a high value educational resource for learning pattern identification and problem solving and that's why we play the game, albeit occasionally.
After all, the truth is, at the heart of all problem solving lies useful pattern identification and its effective application.
In this game we have encountered an interesting 4 digit long cycle and a digit locking condition which finally proved to be the clinching breakthrough. Let us briefly explain the strategies and techniques.
Overall strategy adopted and techniques used
As a strategy we always try first, the row-column scan to find the valid cell at any stage because that is the most basic and easiest of all techniques.
At higher hardness level, easy breaks by row-column scan are few and far between. We have to use in general the method of enumerating small length (2 or 3 digit long) Digit Subsets possible to be placed in favorable cells and writing down the DSs in the cells. This act of writing down the DSs in empty cells helps later in identifying a valid digit by Digit Subset cancellation.
Occasionally, these DSs give rise to Cycles in the corresponding row, column or 9-cell square immediately simplifying the situation significantly. Or sometimes we are able to pinpoint a valid cell by analyzing the DSs in empty cells of a zone with respect to other interacting zones when we find only one digit is left for placement in the cell, rest eliminated. We call this technique as Digit Subset Analysis or DSA in short.
Structure and use of a cycle
Form of a cycle: In a Cycle the digits involved are locked within the few cells forming the cycles, they can't appear in any other cell in the corresponding zone outside the few cells forming the cycle. For example, if a 3 digit cycle (4,7,8) in column C2 is formed with a breakup of, (4,7) in R1C2, (4,7,8) in R5C2 and (7,8) in R6C2, the digits 4, 7 and 8 can't appear in any of the vacant cells in column C2 further.
If we assume 4 in R1C2, you will find R5C2 and R6C2 both to have DSs (7,8) implying only digits 7, and 8 and no other digit to occupy the two cells. This is in fact a two digit cycle in the two cells. Together with 4 in R1C2, the situation conforms to only digits 4, 7 and 8 occupying the set of three cells involved in the cycle.
Alternately if we assume 7 in R1C2 (this cell has only these two possible digit occupancy), by Digit Subset cancellation we get, digit 8 in R6C2 and digit 4 in R5C2 in that order repeating the same situation of only the digits 4,7 and 8 to occupy the set of three cells.
Effectively, the three digits involved cycle within the three cells and can't appear outside this set of three cells. This property of a cycle limits the occupancy the cycled digits in other cells of the zone involved (which may be a row, a column or a 9 cell square) generally simplifying the situation and occasionally providing a breakthrough.
Use of a cycle: In this case, if a vacant cell R8C2 in column C2 has a possible DS of (1,4), as digit 4 has already been consumed in the cycle (4,7,8) in the column, only digit 1 can now be placed in R8C2. This is how a new valid cell is broken through which otherwise we were not able to find out in any other way.
How a valid cell is identified by Digit Subset Analysis or DSA in short
Sometimes when we analyze the DSs in a cell, especially in highly occupied zones with small number of vacant cells, we find only one digit possible for placement in the cell. We call valid cell identification in this way as Digit Subset Analysis.
For example, if in row R4 we have four empty cells, R4C1, R4C3, R4C6 and R4C9 with digits left to be filled up [1,3,5,9] we say, the row R4 has a DS of [1,3,5,9] that can be analyzed for validity in each of the four empty cells.
By the occurrence of digits in other cells if we find in only cell R4C1 all the other three digits 3,5 and 9 eliminated as these are already present in the interacting zones of middle left 9 cell square and the column C1, we can say with confidence that only the left out digit 1 of the DS [1,3,5,9] can occupy the cell R4C1.
This is how we identify a valid cell by Digit Subset Analysis.
You may also refer to our first game play session and second game play session at level 2 where we first explained use of a cycle and DSA.
Let us play the game now.
The first interesting Sudoku game play
Even though the occupancy is as high as 35 (hard Sudoku boards come with as few as 22 cells out of 81 occupied by digits), the digits are so bunched up that not a single valid cell we could find by simple row column scan for more frequently occurring digits 8, 6, 7 and so on. So we resorted to the strategy of focusing our attention to more favorable more occupied zones for digit subset enumeration and analysis.
In the bottom-most row R9, 6 cells are occupied. So we enumerate the possible digits that each of three empty cells can take. These are [4,9], [1,4,9] and [1,4,9] for cells R9C1, R9C3 and R9C9. There was no breakthrough and so we proceeded to attend to column C1 and then on to row R6 which provided the first breakthrough. Each of these have 5 cell occupancy (higher the occupancy of a zone, more favorable it is for finding a valid cell).
First valid cells, R6C3 7, DSA [1,2,3,7] in R6. Interacting column C3 has [2,3] and 9 cell square has [1] so that only 7 is left for this cell.
We color this first breakthrough cell light green and open a new board for ease of understanding.
Valid cell coloring
The valid cells at each stage will be colored in distinctive shades that will be preserved through all the stages of play. This use of different colors makes it easier to recover from mistakes and also eases explanation and following the game flow.
We use spreadsheet for ease and flexibility of representation and manipulation. Because of these qualities, we consider spreadsheet as an invaluable problem solving tool.
The results achieved till now are shown below.
At this second stage, valid cell finding starts with, digit 3 in R6C1 using DS cancel -- R4C1 digit 4, DS cancel -- R9C1 digit 9, DS cancel -- formation of Cycle (1,4) in R9, not useful though at this moment -- R8C1 digit 7 -- Cycle (1,2) in R6. Two digit cycles are always valuable.
Out of new breakthrough digits 3, 4 7, 9, only 4 in R4 is open to affect middle right 9 cell square and as expected, DSA [1,2,3,4,6] in this 9 cell square results in DS [1,2] in R4C8, thus creating a cycle (1,2) in right middle 9 cell square. Thus finally we get the valid cell, R5C8 digit 4, DSA [3,4,6] in this right middle 9 cell square along with a new cycle of (3,6).
We fill up now the DSs in favorable zone bottom right 9 cell square. As we fill up the DS [1,3,9] in R7C5 it immediately forms a four digit cycle (1,3,4,9) in R7. This creates another breakthrough, R7C6 digit 5.
Bottom middle 9 cell square becoming a 5 digit occupancy zone, we fill up its DSs next. Here we discover a very interesting pattern of digit locking in R8C4 and R8C6. The digit 4 is locked between these two cells R8C4 and R8C6. These are the only two places 4 can occur in the bottom middle 9 cell square. This in turn makes occupancy of 4 in R8C2 and R8C3 impossible. As soon as we eliminate these two 4s, the cycle of (1,5) is created producing the breakthrough of 4 in R9C3. This is the breakthrough we were waiting for. We will show further developments in a new board. We call this as digit lockdown technique.
Again we will close this stage here to show further developments clearly. The results are shown in the game board below.
R9C3 digit 4 -- R9C9 digit 1 DS cancel -- Cycle (3,4,9) in R8 (because of cycle (1,5) in R8) -- R7C5 digit 1 -- R6C9 digit 2 DS cancel -- R6C4 digit 1 -- R4C8 digit 1 DS cancel -- R7C8 digit 9 DS cancel -- R3C8 digit 2.
Cycle (1,4,9) formed in R2. We will again show the next stages in a new board. The results till now is shown below.
R2C2 digit 7, cycle (1,4,9) in R2 -- R3C5 digit 9, DSA [2,3,7,9] in C5 -- R8C5 digit 3, DS cancel -- R2C3 digit 9, scan R3, C2 -- R2C9 digit 4 DS cancel -- R2C7 digit 1 -- R1C7 digit 6 DS cancel -- R1C9 digit 9 -- R7C9 digit 3 DS cancel -- R4C9 digit 6 -- Cycle (2,5) in R4. The results are shown below.
The final stage is now easy and it starts with, R4C5 digit 7 cycle (2,5) in R4 -- R4C6 digit 3, DS cancel -- R5C6 digit 9 DS cancel -- R8C6 digit 4, DS cancel -- R8C4 digit 9 -- R7C7 digit 4 -- R5C7 digit 3 -- R1C6 digit 7, scan R3 -- R1C5 digit 2 DS cancel -- R1C4 digit 4, cycle (2,5) in C4 -- R3C6 digit 1 -- R1C2 digit 1 -- R3C3 digit 6 DSA [4,6] in R3 -- R3C2 digit 4 -- R5C3 digit 5 DS cancel -- R8C3 digit 1 -- R8C2 digit 5 -- R4C2 digit 2 DS cancel -- R4C4 digit 5 -- R5C4 digit 2 -- R5C2 digit 6. Solved.
The final result is shown below.
Just remember, you need to solve a number of challenging new games to discover new useful patterns on your own and form your own problem solving mechanism. That is the goal here, and not to break any speed barrier. Go slow, if you like, but go steady and focused following a method using strategies and techniques without any random actions. Above all enjoy the game play. There is no game like Sudoku.
Enjoy.