Sudoku Solving Techniques
There are many different ways to solve a Sudoku puzzle. A computer can solve a Sudoku puzzle using a backtracking algorithm to search the tree of plausible combinations until reaching a solution. If a solution is not reached, it goes back to the last safe configuration and keeps searching the tree. That’s what computers do best, but it requires compute engine, some considerable processing time, and it cannot really tell what’s the difficulty level of a Sudoku puzzle. The algorithm can be modified to reduce the number of plausible combinations and speed up the process. Instead of picking a random cell, we could rather choose the one with the lowest count of hints or candidates for a given position. Nevertheless, it is a process that requires processing power and time, and only a computer can do.
It is wise to use logic deduction rules to reduce the number of candidates before using compute power to search through that tree of possibilities. Furthermore, such rules or techniques allow to emulate the human logic and rate the level of difficulty of a Sudoku puzzle as a human would experience it. Some of these Sudoku solving techniques include the identification of singletons or naked singles, hidden singles, and naked and hidden pairs/triples/quads. The Excel Sudoku Solver will take advantage of these techniques to start solving a puzzle. The application of these basic techniques usually allows to solve puzzles of low and medium difficulty (what we often see as Easy, Intermediate, and even some Difficult puzzles). However, for very difficult puzzles, advanced techniques such as X-wing, Swordfish, XY-wing, etc. and/or, ultimately, making assumptions or guessing a number, is needed to reach a solution. It is often told that a proper Sudoku with a unique solution should not require any assumption/guessing to be solved. However, there are many different advanced techniques out there we are not aware of, and sometimes the only way to progress to a solution requires some sort of guessing at some point.
Getting Hints or Possibilities (Pencil Marks)
In order to apply the basic Sudoku solving techniques, the grid of hints or possibilities is often used. That’s the notation of hints or pencil marks most Sudoku players write on the paper or keep in mind to solve a puzzle. The hints are also called possibilities or candidates. The first macro will generate a grid of hints for a given Sudoku puzzle.
In this Excel version of the Sudoku solver, we have the Sudoku puzzle in one sheet (Sudoku), and the hints in the same range of a separate sheet (Solver). For each number (1 to 9), the macro loops through every blank cell in the Sudoku puzzle checking which numbers are allowed. We keep adding those numbers (hints) to compute the grid of possibilities (see above example).
In that process, and for each blank cell and number, we use the CountIf worksheet function to check if the number appears in that row, column, or block. Note that we use a custom function (qRng) to check the range address of the block for a given row and column.
Solving Naked Singles
Naked singles or singletons are unique candidates within the grid of hints. In the example above, we can immediately spot two naked singles in the grid.
We can solve those numbers with Excel VBA simply looping through each cell with content in the grid of hints, and copying the value to the solution when the length of the value in that cell is 1 (Len(cell.Value)=1).
If any singles are found and added to the solution, we need to get a new grid of hints and repeat the process until no more singles are found, or until the puzzle is solved.
Solving Hidden Singles
A hidden single can also solve the value of a cell, but it is less obvious or visible to spot than the naked single. After solving the singletons in the example above, the new grid of possibilities does not show any other naked singles. However, we can easily spot several hidden singles in each of the highlighted cells below. The number 8 is a hidden single in the first row (and top right block). Number 8 is also a hidden single in the last column, and 6 is another hidden single in that block.
There are different ways to find hidden singles in the Sudoku grid of possibilities with a computer. Despite that’s a process the human brain can do fairly quickly, it takes a few loops and functions for the computer to find them.
The ShowHiddenSingles macro loops through the grid of hints by row, column, and block, to search for hidden singles. Let’s see how it’s done for rows (the same applies to columns and blocks). For each cell in a row, we use the Mid function to get each number or hint, and then loop again through the row to check how many times it appears using the Instr VBA function. The Instr function returns the position of a substring (the given number) within a string (all the hints in a cell). If that number is not one of the hints, it returns zero. If that happens for every cell in a row, the number is a hidden single and can be added to the solution.
See below all hidden singles found when running the macro for the Sudoku puzzle example above.
As this is a puzzle of medium difficulty, running these two macros consecutively eventually solves the puzzle. This other Sudoku puzzle below, however, is a level of difficulty higher and won’t be solved just with those techniques.
Finding Pairs, Triples, and Quads
The Sudoku puzzle above requires finding pairs to progress to a solution. Finding pairs, triples, and quads in the grid of hints, allows to eliminate those possibilities in other cells, which, eventually can reduce the possibilities of a cell to a single candidate. After a few solving steps (solving naked and hidden singles), the puzzle example above reached a configuration with no more singles to solve.
However, there are several pairs that can help reduce the number of possibilities. For example, 15 is a pair in the first column, while 18 is a pair in the bottom right block. Therefore, we can remove all 1s and 5s from in the first column, and all 1s and 8s in the last block. When doing that, another pair in the last block becomes apparent (56). Then we can remove the number 5 in the first column for that row, and, bingo, number 1 becomes a singleton to solve. That move actually allows to solve the rest of the puzzle using again the previous techniques (naked and hidden singles).
The macros to find naked and hidden pairs, triples, and quads in this version of Excel Sudoku Solver follow the same principle used for naked and hidden singles. However, the code is too large and intriguing to show here. Download the simplified version of the Excel Sudoku Solver to see the code. Note that this is just a simplified version and can only solve Sudoku puzzles of low to medium difficulty (may solve some difficult too). It only applies the solving techniques explained earlier.
Download Excel Sudoku Solver Simplified
In order to solve difficult and very difficult Sudoku puzzles, advanced solving techniques are needed. Some of these techniques include X-wing, Swordfish, XY-wing, among others. Creating a macro for each technique becomes a hefty work though. Therefore, it is probably better at this point to use compute power and crunch the numbers to solve Sudoku puzzles of any level of difficulty.
Solving with a Backtracking Algorithm
The full version of Excel Sudoku Solver uses a backtracking algorithm when the basic techniques explained earlier can no longer progress towards a solution. The macro selects a cell with the lowest number of hints available and chooses one of those values (usually, one of two values). Then it tries to solve with the logic techniques explained earlier. While progressing, it may need to guess more numbers though. Eventually, it either reaches an unsolvable puzzle or the solution. If not solvable, it goes back to the last safe configuration before making any other assumption. There is a more complex process behind the scenes saving the assumptions to a stack in order to avoid repeating a wrong guess. This method should be able to solve any Sudoku puzzle. The Excel Sudoku Solver has been tested with puzzles of highest difficulty from popular Sudoku websites, and some of the most difficult Sudoku puzzles documented on the internet. It generally takes just a few seconds to solve any puzzle. Download the full version of the Excel Sudoku Solver and let me know if you hit a puzzle that cannot be solved.
No comments:
Post a Comment