Sudoku Puzzle Solutions: Methodology of Process
I wanted to include this section on Sudoku Puzzle Solutions because I believe it would be
beneficial to give some insight on what I like to call the 'The Methodology of Process'.
Whether we realize it or not when we undertake to solve a Sudoku , we are employing a
system of logical steps, to define, or arrive at the solution.
As an avid sudoku puzzle solver for more than 30+ years ( I remember doing Number Place
in the 1980's), I have become so familiar with 'my processes ' to solve the puzzle, it has
become , for lack of a better term, lost in translation.
That is ,until I decided to start this web page, and rediscovered my subconscious tactics.
Funny thing is I didn't realize they actually had names for these processes, so for any
novices let us investigate these now. So here are my methods
Methodology of Process:
(A set of working methods for Sudoku puzzle solutions):
The names of these methods include: Elimination, CRME ( Column-Row-Minigrid Elimination),
Lone Rangers, Twins (sometimes called "Naked Pairs"),Triplets( "Naked"), Quads ("Naked") and
Brute Force.
These are by far the absolute best methods I have found to work and highly recommend for solving
a vast majority of sudoku puzzles.
I now propose to discuss each, in turn briefly , here today.
We begin with the Elimination method.
- Elimination
The first and most obvious step.
Simply scan your puzzle board and eliminate the obvious.
That is you can first see if there are any rows or columns which have only one possible solution.
| 9 | 6 | 5 | 1 | 7 | xxx | 2 | 3 | 4 |
| 8 | 7 | 3 | 6 | 9 |
In the above example we can see that the first row column six has one, and only one possible
solution , "8". See. Eliminate. Simplify.
The above example although serving a purpose, is not a practical solution, mainly
we are not looking at the entire grid.
Aside :Before we proceed I want to also introduce some convenient notation for our puzzle board.
To identify a particular cell, we give it a designator with the ordered pair ( column , row).
Therefore the 1st cell in any Sudoku puzzle is identified by (1,1). and the last (9,9) .
(see diagram below).
|
We take a standard 9x9 puzzle and introduce , for each and every individual cell ( a unique position identifier- as shown ). Starting with the leftmost position we have assigned it the ordered pair (1,1),[ where the notation (1,1) = ( 1st column, 1st row) ] ; more generally, we order the pair by letting ( column, row) = ( c, r ). Therefore, the position of the 5th cell over, 3 rows down can be given by the shorthand: (5th column, 3rd row) = (5, 3). We shall now adopt that notation for the rest of our discussion. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- CRME( or Column-Row-Minigrid Elimination):
A more elaborate method for solution would be the column-row-minigrid-elimination process.
For this method we will employ a three tiered attack:
- 1.scan rows.
- 2.scan columns.
- 3.scan local (3x3 minigrid).
|
We begin by choosing cell (2,1) as a starting point, (denoted by X)-see diagram below). Employing our 3 tiered attack we scan across row 1 and see the numbers 6, 3, 8, 7,2, therefore we eliminate those from contention.
Next we scan down column two and see 3, 8, 9, 7 2. (Eliminate them).
|
(Remembering X can only be the numbers 1-9) Starting Values for X : 1,2, 3, 4, 5, 6, 7, 8, 9 ====================================== ====================================== (Row scan eliminates 6,3, 8, 7, 2) Therefore, X possible (after scanning row1): 1, 4, 5, 9 ====================================== ====================================== (Column scan eliminates 3, 8, 9, 7, 2) Therefore, X possible( after scanning down column two): 1,4,5,6 ====================================== ====================================== |
Scanning our local ( 3 x 3 ) local grid We see 1,3,4, 6,7, 8 already entered, therefore, if we now eliminate 1, 4, 6 , we have cell(2,1) = 5. [(Enter it in slot (2,1)] |
|
- Lone Rangers:
Simply put a 'Lone Ranger' is a single number out of a possible value in a cell which is the only
one in a given row, column, or sub-grid. In the example below we have a typical row which has
been filled in ( 6, 8, 5, 9, 2, 7 ) , leaving 3 cells (highlighted in blue) with their possible values of 1,3,4.
Looking at the possible values we see 4 is available only once, therefore 4 is a lone ranger.
-
6
1 3 4
8
5
9
2
7
1 3
1 3
In the above example we consider 4 to be a 'lone ranger' because it appears only once.
As a technique the lone ranger method it is quite useful in helping solve some complicated
sudoku puzzles.
Remember to scan every sub-grid, row and column looking for these lonely fellows,
they often may lead to other methods of solution.
Below are several more examples
|
Sub-grid Lone Ranger example:
This is a partially filled puzzle, showing the first three rows. We have highlighted the filled in possible values for each of the first three sub-grids. |
We want to focus on the third sub-grid :
For this sub-grid we can see that 1 has only one possible location, therefore by the method of Lone Rangers, we conclude 1 MUST be the value of that cell( to the exclusion of all others). |
|
LONE RANGER: ROW EXAMPLE
Again we have filled our puzzle with possible values, and we are scanning each row for possible ' lone rangers'.Let us isolate row 5, to check the cell highlighted in yellow. |
ROW 5:
Of all the possible values in this row 2 appears only once in column 6 (as highlighted above), therefore 2 is the only possible number, discovered by the method of lone rangers.
Our Row 5 now appears as follows:
|
|
LONE RANGERS BY COLUMNS:
We are now performing a column scan for possible lone rangers, ( after filling in the possible values of this Sudoku). Column 8 appears to be worth noting. |
By performing a column scan we have found the value 8 is a lone ranger in the cell position highlighted in gold above. Thus we write “8” into that location. |
- Twins/Triplets/Quads:
These methods are extensions of the 'lone ranger' method discussed above, except we apply our
testing cells to cells with two pairs and three pairs, and more.
Let us look at the method of twins( also called 'naked pairs') as they apply to sub-grids, rows
and columns. (Note:Twins will allow us to restrict or eliminate possible values for other cells in the grid
(refer to the diagrams below)).
|
TWINS METHOD:
Above we have a partially solved puzzle (with possibles in the highlighted cells). If we focus our attention on the sub-grid (in the middle), we see two cells of particular interest, with possibilities 8, 9 (our twins) . For this particular sub-grid we can now make some observations: (see diagram to the right).
|
1) because either 8 or 9 must be in those two cells, we can eliminate those values from any other cells in this sub grid as follows:
Note: As shown above, the remaining cells in this sub-grid have only 2,4 or 5 remaining as possibles). We can apply this to column 6 as follows: Again by the method of Twins, we can reduce the possibles in the cells , as shown. above .( Eliminating 8 and 9 , leaves only 367 available in column 6 cells).
|
The triplet ( naked triples) and hence the Quads ( or Naked Quads)process would work similar to
the twins method except we would apply our scanning process to search for triples (or Quads)
in a sub-grid, row and column. We have simple examples below ( side-by-side).
|
METHOD OF TRIPLES:
Above we are given a sub-grid with the highlighted triple. Similar to twins we are able to eliminate the values in the other cells, ( in this instance creating another triple -789).
|
METHOD OF QUADS:
Above we are given a sub-grid with the highlighted Naked Quads. Similar to triples we are able to eliminate the values in the other cells, ( in this instance creating a twin, 89 in the cells as shown below).
|
HIDDEN PAIRS / TRIPLES:
You now know to look for certain patterns of grouped numbers ( lone rangers, naked twins, triples and quads),
this should help you find other combinations like hidden pairs and hidden triples.
In other words you may see a pattern like the one above where we actually uncovered a hidden twin
( the diagram above where we had the quads, the two cells containing 135789 are actually a hidden twin,
because they are the only two cells with 8, and 9 available in that sub-grid ( "....more than one way to
skin a cat" as the saying goes).
You may come across the following a set of two triples( say two cells with 1,2,3) and a third cell which
contains a subset of the triple ( a subset can be 12,13,23 in some order) or a single triple
(again using 123 as our triple example) and two other cells which contain the subset.
To summarize , to solve Sudoku puzzles with any of these methods above one has to be able to recognize
patterns in numbers and scan each sub-grid, row and column, painstakingly removing or eliminating
numbers until one arrives at the correct solution.
BRUTE FORCE:
Is as the name sounds, a less substantial method of solving, but if all else fails........
Brute force may be less about brute, think of it more as a hunch or even an educated guess.
Let us say you have tried all the methods above, and you haven't made any progress,
time to put your old noggin to work.
Review the grid , start with the most probable candidate, that would be the cell with the least amount of possibles.
For example say we find a cell with 6,8 in it.
By the process of Brute force we simply pick one or the other (your choice is arbitrary) and see where
that path leads us. Say we choose 6, then we begin by putting in all the possible values
(Also at this point I would recommend maikng a mental note of your branching off point, because
you may go through many steps and arrive at a dead end), at that point you would backtrack to
your starting point and plug in the other number , in this case 8.
To summarize the Brute Force method may seem less technical than some of the other methods,
but, ( take it from this experienced player), it sometimes works and may even lead to other
methods, like hidden pairs or triples.
- ADVANCED TECHNIQUES
Below is a discussion of more advanced methods of solving Sudoku puzzles.
These methods we would recommend only if none of the above methods work, as the advanced
methods are usually more involved.and for my tastes more time consuming then even the
Brute Force method.
But if you insist, click on this link to see 'em :
X-Wing, XY-Wing, Swordfish , Color
- BRUTE FORCE ALGORITHMS: (COMPUTER METHOD)
There are approximately 67,000, 000, 000, 000, 000, 000, 000( YES, that is 6.7 x 10 to the 21st power)
Sudoku puzzle solutions (or game combinations) possible.
Brute-Force algorithms are basically computer programs that will solve Sudoku puzzles.
A good program might be a practical way to solve Sudoku puzzles, (so long as the puzzle is a valid one,
that is one of the 6.7 x 10^ 21 grids).
Basically it is a numbers crunching game,
A brute force algorithm visits the empty cells in some order, filling in digits sequentially from the
available choices, or backtracking (removing failed choices) when stymied. For our purposes
assume a algorithm order of left to right, top to bottom. (The algorithm could, however,
visit the empty cells in any order)
Briefly, a brute force program(or a person doing it manually) would solve a puzzle by placing the
digit "1" in the first cell and checking if it is allowed to be there. If there are no violations
(checking row, column, and box constraints) then the algorithm advances to the next cell, and places
a "1" in that cell. When checking for violations, it is discovered that the "1" is not allowed, so the value is
advanced to a "2". If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves
that cell blank and moves back to the previous cell. The value in that cell is then incremented by one.
The algorithm is repeated until the allowed value in the 81st cell is discovered. The construction of 81
numbers is parsed to form the 9 x 9 solution matrix.
Most Sudoku puzzles will be solved in just a few seconds with this method, but there are exceptions.
From Sudoku Puzzle Solutions to Sudoku Puzzle
From Sudoku Puzzle Solutions to Puzzle Games Online
Riddles:
If you try to fail and succeed, what have you done?
Does 'expect the unexpected' make the unexpected expected?
If we are here to help others, what are the others here for?
If corn oil is made from corn and olive oil made from olives, what is baby oil made from?
More Riddles:
If you have a bunch of odds and ends and throw away all but one, what do you have left?
Would a fly without wings be called a walk?
Why is 'abbreviation ' such a long word?
What was the best thing 'before' sliced bread?
Why isn't there mouse-flavored cat food?
Why is the person who invests your money called a broker?
The Social network based search engine & news service
Who links to my website?