Sudoku Puzzle Solving Strategies

By Dr Arf

Strategy

For me, the greatest appeal in solving Sudoku puzzles is the thought process used. Invariably, deductive reasoning is employed when solving a Sudoku puzzle. If this, then that – is the basic thought process.

Being a big fan of Sir Arthur Conan Doyle, thinking using deductive reasoning reminds me of Sherlock Holmes. Sherlock’s deductive logic and thought process was the main plot characteristic of every Sherlock Holmes mystery. Often, Sherlock would engage his friend and colleague, Dr. Watson, to use Sherlock’s deductive technique. Sherlock would explain his analysis indicating that deduction was a learned thought process. For Sherlock, the mental gymnastics of using deductive logic was training to maintain and improve his mental faculties. Similarly, Sudoku appeals to many as an exercise to maintain and improve the mind.

Also like Sherlock, one particular type of deductive reasoning is used, that being the process of elimination. By eliminating what can’t be from a finite set of possible cases, a single remaining possible case may be identified.

When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth.” – Sherlock Holmes

Actually in Sudoku, a numeral (a single digit number) is never improbable. At each grid position of a Sudoku puzzle, a numeral is either possible or impossible. Therefore, Sudoku is even more elementary than a Holmes mystery.

Brute Force

At each open grid position of a Sudoku puzzle, a solver can mentally eliminate numerals by applying the basic rules of Sudoku. If, by the process of elimination, there is only one possible numeral, then it must be the entry that will solve the puzzle. By brute force a solver can, one at a time, analyze each open square. If it has one possible numeral, the solver enters that numeral and then goes on to examine another open square. If there is more than one numeral possible and all but one cannot be eliminated, the solver skips that square and tries another.

However, at the start of a difficult puzzle, few open squares will have a single possibility. In fact, many puzzles will have only one or two at the start. Sometime at the start of a puzzle, using just the basic rules, there are no squares with a single possibility. In that case, more complex logic is required just to begin.

Also, even when there exists a square at the beginning, where only one digit is possible, often as the grid is filled, new locations with only one possibility cease to occur and open squares with only one possibility run out. Again, to continue, only more complex logic can work.

Using brute force becomes very tedious when there are many open squares and few having a single possibility. Brute force has its drawbacks for sure. However, as the solution puzzle progresses and more empty squares are filled, it may become necessary and preferable to employ a brute force method.

Luckily, those situations usually make the brute force process less tedious. In fact, in some situations brute force becomes easy. So, knowing how to determine a numeral by brute force is required. Since the logic is straightforward it a good starting point when learning Sudoku puzzle solving strategies.

To know when brute force is not tedious, it is necessary to know just how tedious it can be. For example, let’s use the brute force method at the beginning of a puzzle. Let’s apply brute force to the upper left hand corner square (shaded green) of the example puzzle grid below. In this illustration, the row, the column and the secto, pertaining to the square being analyzed, are examined for occurrences of each numeral. The pertaining squares are shaded in yellow (see Figure 1).

The numerals 1, 2, 5, and 9 occur in the pertaining row, column and sector (yellow squares). This leaves 3, 4, 6, 7, and 8, or five possibilities for the upper left hand square. We cannot eliminate all but one and cannot determine the proper numeral from this analysis.

Brute Force 1
Figure 1 – Brute force analysis of the upper left hand square.

The next square to the right is not much better (see Figure 2). The numerals 1, 2, 3, 5, 6, and 9 occur in the pertaining area, leaving 4, 7, and 9, or three possibilities.

Brute Force 2
Figure 2 – Brute force analysis of the next square.

To illustrate the situation, a map of the number of possibilities at each position, shows where a square that has a single possibility may exist. By counting the possible numerals at each grid location and placing that count in the corresponding location, a map of possibilities is constructed.

The map constructed from the example puzzle is below. Notice that the two counts in the upper left hand corner of the map (i.e. 5 and 3) correspond to the brute force analysis from above (see Figure 3).

Map of Possibilities
Figure 3 – The map of possibilities of the example puzzle.

It can be seen using this map, by applying the brute force method systematically, the solver would analyze 18 squares, before the first entry is found. The solver could start at the upper left and examine each square, one at a time, across and down, applying the process of elimination (see Figure 4). Well, that seems tedious, doesn’t it?

Tedious Situation
Figure 4 – Applying brute force to each open square systematically.

As an exercise, let’s determine the proper numeral, at the location found in the above map, using the brute force method. The numerals 1, 2, 3, 4, 5, 6, 7, and 9 all occur in the pertaining area (yellow), leaving only 8 as a possible digit (see Figure 5). Great, we have our first entry at last.

Brute Force Can Work
Figure 5 – Brute force analysis to determine the first entry.

After entering the 8, just discovered, to the grid (at green square), the updated map of possibilities now shows a new location where there is only one numeral possible (see Figure 6).

New Location
Figure 6 – The map of possibilities with a new location where only one numeral is possible.

Entering the 8 digit will eliminate the numeral 8 as a possibility from other open squares in the grid and adds new information to the analysis of the grid. Each new entry reduces the overall possibilities. Each entry can lead to the discovery of other entries by changing what is possible. Each deduction leads to the next. Like in a mystery, one clue leads to another. In Sudoku, the challenge is to find the entry that leas to the next. A solution is a sequence of deductive steps.

If the solver applies the brute force method repeatedly in this example, the solver is stymied after only four entries. The map of possibilities shows no squares where only one numeral is possible (see Figure 7). Brute force will no longer work.

Brute Force Stops Working
Figure 7 – The example puzzle grid and map of possibilities after four entries.

Clearly the brute force method is lacking. It is tedious and frustrating. There can be no joy when it is used to solve a Sudoku puzzle exclusively. It may be the first strategy learned, but should not be the first strategy used when starting a new puzzle.

When to Use Force

The best time and the easiest time to use the brute force method is when there is only one open square remaining in a row, column or sector. This is at the other extreme of the tedium spectrum. Finding the one missing numeral in a row, column or sector is easy. For example, if there is only one open square in a row, the solver can look across the row for a existing numeral 1 in the filled positions. If found, the solver looks for a 2. If found, the solve looks for 3 and so on. If a numeral cannot be found in the row, then is must be the numeral in the last open square of the row.

After a little practice the user will learn to abbreviate this scanning the exiting numerals process and the remaining or missing numeral will become immediately visually obvious.

Another time to use brute force is when at an impasse (stymied). It is sometimes useful to try brute force to overcome the impasse and continue solving the puzzle. If there are only two or three open squares in a row, column or sector, it may work and the solution may progress again.

Also at impasse, it sometimes can be visually detected that a particular location may be a candidate for a brute force analysis. As seen above, the application of brute force is very tedious and is in this case an act of desperation. As the solver becomes acquainted with more complex techniques, the solver is less likely to be willing to endure the tedium, and will consider brute force at an impasse only as a last resort. (And unfortunately, It seldom succeeds.)

Row and Column Projection

Here is the method I use when starting a new puzzle. By projecting particular rows and columns, that contain the same numeral, into a target sector, a single position in the target sector, where that numeral can occur, can sometimes be visually identified.

It is a mental construction and is best explained visually. In this illustration, the solver mentally projects a “no 2 area” in rows containing the numeral 2 to the right (shaded red) into a target sector at the middle right that doesn’t contain a 2 (see Figure 8). The solver can visually see (in the minds eye) that there can be only one location in the target sector that can contain a 2.

Projecting Rows Right
Figure 8 – Projecting rows that contain a 2 to the right.

All of the open squares in the target sector are shaded red except where the 2 can be (shaded green). The 2 is entered to the grid.

Since I tried a 2 last, I try 2 again, continuing trying to find all the 2 digits in the puzzle. So next, I try projecting two columns down into the lower right target sector (see Figure 9).

Unfortunately, there are two locations where a numeral 2 can occur (two shaded green). I make a mental note of that. If I find another 2 in one of these two rows later, I can determine which of these two locations has the 2 in it, just from memory.

Projecting Columns Down
Figure 9 – Projecting columns that contain a 2 down.

Not giving up, I continue trying to project rows and columns that contain the numeral 2, and I quickly find two other locations that contain a 2, one in the upper left hand sector  and one in the upper middle sector (see Figure 10).

Projecting Method Finds Two
Figure 10 – Projection quickly finds two more locations.

Projecting the last location found with another column (down), finds another solution digit in the middle bottom sector (see Figure 11). The row that it is in, is a row where I made the mental note from before. From the small mental note made a very short time earlier, I find the 2 in the lower right sector. Thus, I have demonstrated the wisdom to continue projecting with numerals that have been found recently. The time to remember things is shortened.

Projecting Columns Down
Figure 11 – The mental note pays off.

At this point in solving the puzzle, we have found the numeral 2 in eight of the nine sectors. After the eight locations of a numeral are found, there is nowhere for the culprit to hide in the remaining sector. The projection method will always find the remaining location in the last sector (see Figure 12).

Nowhere to Hide
Figure 12 - Finding the ninth of a numeral in the last sector. There is always only one square.

After finding the ninth location that must contain a numeral 2, the numeral 2 is eliminated as a possibility in all of the remaining open squares. For this puzzle, I never consider a 2 again.

Arbitrarily, I use numeral 4 in the projection technique next.  In this example, the 4 was nearby in the last target sector, and very little thought is given to selecting the numeral to project. This “shoot from the hip” approach helps to make the thought process quick and lightweight.

All of the 4’s, 9’s, 3’s and 1’s are found with projection method in this example (see Figure 13). As an exercise, the reader is encouraged to try the projection method with these four numerals.

After filling all of the 1′s, 2′s, 3′s, 4′s, and 9′s in the grid, the puzzle that started with fifty open squares, has been reduced to a puzzle with twenty-five open squares.

I tend to be a visual thinker. Many people have that tendency. After a little practice, this visual technique becomes very quick and does not require a lot of brain power.

Projecting 4's, 9's, 3's, and 1's
Figure 13 – Filling all of the 4′s, 9′s, 3′s, and 1′s in the grid.

Alternating Projection and Brute Force

Note that in this example after completely filling several numerals, there exists a sector and a row (shaded yellow) that have only one open square (see Figure 14).  It is extremely easy to apply brute force to fill these two open squares (shaded green).

Brute Force Quickly Fills
Figure 14 – Only one open square in a sector and one in a row.

After filling the 6 in the sector and 7 in the row, the updated map of possibilities is examined and we see that the rest of the solution can be found with brute force without difficulty (see Figure 15). However, if we limit the use of brute force to the condition when only one open square is in a row, column or sector, and use the projection method when that condition doesn’t exist, the solution is found with little work.

Brute Force Works Again
Figure 15 – Brute force will work again.

This strategy of alternating between a visual projection method and brute force when conditions are right, can easily solve moderately difficult puzzles. Continuing in this example, since the last numeral discovered was the 7, we apply the projection method using 7 and completely fill all that can be that numeral. This leaves only 5, 6, and 8. The strategy of alternating between visual projection and brute force, fills the rest even easier than before. No other technique is needed.

A solver can gain proficiency at this technique and puzzles with the difficulty of this example will quickly become less than challenging. It will be below the solver’s skill level, and the solver will eventually be attracted to more difficult Sudoku puzzles.

By using this alternating method, it can become almost mindless or robotic to fill Sudoku puzzles of lower caliber. Some find this activity of solving Sudoku puzzles, without intense reasoning, comforting or relaxing.

I sometimes do this myself. It can clear my mind or I can unwind after a period of intense contemplation. It’s very much like knitting or basket weaving and can have a similar calming effect. Also, one can fill enormous amounts of time, oblivious to its ultimate duration. It can be an excellent nullification or numbing waste, while suffering from things like modern air travel.

Only One Location in any Class

But we are not here for basket weaving, Watson. Challenges of the mind and more complex logic are our interests here.

A more complicated technique that is sort of a simultaneous combination of brute force and projection is the next approach to be demonstrated.

First, we will introduce some new nomenclature. Since the basic rules of Sudoku are similar for rows, columns and sectors, the logic that applies to one, for example rows, often applies to both of the others (i.e. columns and sectors). Having symmetry in the rules is a benefit.

To avoid always referring to them individually when we mean all three, we give the three structures a common name. Rows, columns and sectors are all types of a Sudoku Class (or just a class). So, if a rule applies to any class, the meaning is it applies to rows, columns and sectors. In addition, we will also say a class when we mean a particular instance of a class (i.e. a particular row).

Another shorthand that is intended to make explanation easier is, when there exists a location that has only one possible numeral, we will now say that a singular possibility exists. Or, there is a singular possibility. This shorthand should help.

Last thing to be introduced is, the previous technique described in the last section is called the alternation method. This is the method that starts with the row and column projection method. And, when a condition where only one open square exists in a class, the technique switches to brute force to find the last entry of that class.

With that, let’s look at a more difficult puzzle to see the new technique in action. As before we start by employing the alternation method. By using the alternation method, we only completely place the numerals 3 and 7. Also, only a handful of other entries are found (see Figure 16).

More Difficult Puzzle
Figure 16 – More difficult puzzle.

We might try brute force as a last resort on good candidate locations (shaded green), but constructing a map of possibilities for this situation shows that it would not help (see Figure 17). With only the alternation method, the solver is stymied.

Brute Force Candidates
Figure 17 – Brute force candidates and the map of possibilities.

Let’s try some new logic. Because a numeral can only appear once in a class, and there is the same number of numerals as the number of positions of a class, then all of the numerals must occur in the class. To illustrate how this helps, let’s look at a row (shaded yellow) that had the candidates locations for brute force method from above (see Figure 18).

Row of Interest
Figure 18 – Analyze a single row looking for every numeral.

Since all of the numerals must occur, we start with the numeral 1 and look for positions in the row of interest that can have a 1. If there is only one position, we have an entry. If there is more than one position in the row, we haven’t eliminated that numeral and we go to the next numeral in order (i.e. 2). If the numeral already occurs in the row, we skip it and try the next. The order can start from 1 and can be ascending or it can start at 9 and be descending. It can sometimes help to start from 9 in many situations.

To illustrate this new method we will call “only once in a class“, we will start with the numeral 1. There are four locations (shaded green) where there can be a 1 in the row of interest (see Figure 19). All four open squares in the row can contain a 1. Nothing has been determined and we try the next numeral in order, which is the 2.

Four Locations Possible
Figure 19 – 1 can be in four locations.

Because a 2 exists in the leftmost column and exists in the upper right sector, it cannot be in squares of the row interest that are shared by this column or sector. Excluding the shared squares, the numeral 2 can only be in one square shaded green of the row (see Figure 20).

Found a 2
Figure 20 – Only one location that can be a 2 in the row.

Unfortunately, the “only once in a class” method finds no more digits in this row. Trying the alternation method on the newly found 2 doesn’t work either. Sticking with the newly found 2 digit, we analyze the column that contains the new entry with the “only once in class” method (see Figure 21).

Column with New 2
Figure 21 – Try the column that contains the new 2.

Noticing the 9’s on both sides of the column of interest, but not in the column of interest. Seeing the 9’s as a clue, we choose to start with 9 and work backward this time. Immediately, a 9 is found in the square shaded green of the lower left sector (see Figure 22).

Only Once in a Column
Figure 22 – Only one place for a 9 in this column.

Again continuing the order using the new method in the column does not find any more singular possibilities. Using the alternation method does not find another entries either.

However, two classes in the grid have only two open squares. A class with only two open squares is a very good candidate for the “only once in class” method. We choose one of them, the leftmost column, to be next with the new technique (see Figure 23).

Leftmost Column of Interest
Figure 23 – Next column to try the only once in a class technique.

Starting with 1, we find a singular possibility in the square shaded green of the top left sector (see Figure 24).

Found a 1 digit
Figure 24 – With only two locations open in the column, 1 can be in only one.

The alternation method fills five more entries (see Figure 25). However, in this situation we are at an impasse, none of the methods find any more entries. A new method is necessary to continue.

Need New Method
Figure 25 – Five more entries found.

Only Two Possible in Two Locations

Notice this row (shaded yellow) in the example puzzle below (see Figure 26). It has only two open squares and both of them are shared by one sector. This jumps out visually to be a candidate for the next logic to demonstrate.

Only Two in Two Possible
Figure 26 – Only two in two possible.

Because there are only two open squares in the yellow row, both of the remaining numerals in that row must occur in those squares. Since these two locations are part of one sector, then the two numerals cannot be in any other squares of the sector. Also, only these two numerals can be in these two squares, even if the rest of the sector is empty. No other numerals need to be considered for these two squares. This is a big benefit of class symmetry.

In the example, the numerals 4 and 5 must occur in the two remaining squares (shaded green) of the row. Therefore, they cannot occur in the other two open squares of that sector (shaded red).

Sometimes this logic finds a singular possibility by itself. In this case it doesn’t. However, only two numerals remain 1 and 9 and they must be in the last two locations of the sector.

Unfortunately, because this technique did not find an entry, we will need another new technique to solve the puzzle.

Only Occurs in Sub-sector

A sector can be subdivided into three rows and three columns. I will call them sub-sectors. The reason that they are interesting is, because if a numeral can only occur in one sub-sector, the remaining squares of the row or column that shares squares with the sub-sector.must not contain the numeral. This means the numeral can be projected from the sub-sector without actually knowing where it is in the sub-sector. Ths logic can be useful.

In the example, only a 1 or a 9 can be in the one column subsector (shaded gray), so a 1 or a 9 can be projected down the column shaded red (see Figure 27).


Figure 27 – 1 ang 9 are used in column projection.

We notice that the projection intersects a row shaded yellow with only two open squares. Eliminating the numerals 1 and 9 from one of the open squares in the row, reveals a singular possibility of a 1 in the only other open square (shaded green). This also finishes the row and using brute force a 2 is found in the last remaining open square.

We now try going down the same column using the “only once in class” technique. Since 1, 2, and 3 are represented already, we start with the numeral 4 and we see that it can not exist on the bottom row in red. It can only exist in the green square, thus we found the 4 in that column (see Figure 28).

Subsector Projection
Figure 28 – Only one location that can contain a 4.

After finding the 4, the alternation method will find the rest of the solution (see Figure 29). Success! I leave that as an exercise.

Easy to Solve
Figure 29 – The alternation method can solve this puzzle now.

Summary

With just a few techniques, a solver can find success with all but the most difficult of Sudoku puzzles. With these techniques and some practice, the novice solvers can jump start to a higher skill level. A solver using these techniques can find many hours of enjoyment and mental exercise using deductive reasoning.

Although these techniques may be new to some, they still may be considered as less than clever. Others may consider the deductive logic, shown here, as obvious or simplistic. For those who may feel this way, I leave you with this quote:

omne ignotum pro magnifico” – Sherlock Holmes

The Latin translation is, “what is unknown appears magnificent”. Sherlock was saying that, after he explains the details of his logic, it no longer appears ingenious. In all cases, each step was simple or elementary. Many minuscule logical steps, lead to a giant leap of truth for Sherlock. Or, in the case Sudoku logic, each small step of simple reasoning leads to a Sudoku puzzle solution.

August 15, 2012Permalink 1 Comment

One thought on “Sudoku Puzzle Solving Strategies

  1. I’m not that much of a online reader to be honest but your blogs really nice,
    keep it up! I’ll go ahead and bookmark your site to come back down the road.

    All the best

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>