This Sudoku solver in Excel will help you solve a sudoku puzzle with brute force. This Sudoku solver, has been written in VBA and incorporates a brute force algorithm which helps its solve some of the toughest sudoku puzzles using nothing more than an excel spreadsheet.
In this article we will talk about how to develop a Sudoku solver using code in Excel, discover the tips that allow the player to solve any Sudoku puzzle and discuss the use of brute force when trying to solve a Sudoku puzzle.
How to develop a Sudoku Solver in Excel using VBA code
If you are not very well versed with the concept of a solving a Sudoku puzzle, I would suggest that you read through the two sections below, before returning to this section. Developing a sudoku solver is pretty easy if you keep these simple rules in mind:
Quickly generate the list of likely numbers that can be placed in a particular cell
For a Sudoku solver to begin solving a puzzle, the first step is to quickly create a list of all possible numbers that can ever be placed in a cell. A number becomes a likely candidate for being placed in a cell when:
– It is not already in place in any cell in that row AND
– It does not occupy in place in any cell in the column to which the cell under consideration belongs AND
– that the number is not present in any cell of the 3×3 grid to which that particular cell belongs.
So in our code, we make each of the numbers from 1 to 9 pass through all these conditions. Only when a number meets all these criteria, we add that number to the list of likely number for a particular cell. Using VBA, we first define a 2-dimensional 9×9 array to store all the existing numbers in the (partially filled) Sudoku. Then we proceed on to creating a 3-dimensional 9x9x9 array in VBA Excel such that each cell in the 2-dimensional array created earlier is provided with 9 possible slots to accommodate all likely numbers for that cell.
Eliminate likely numbers that can potentially be placed in a cell as fast as possible
Having done that we use a simple method to eliminate numbers in the list of likely numbers. The rule of the thumb here is that if a particular likely number for a cell does not feature as a likely number for any other cell in that row, it must be the right number to be placed in that cell. The same rule applies for the column in which that cell exists and the 3×3 grid to which that cell belongs. If any of the three conditions are met, you can safely place that particular likely number in the cell under consideration.
Move from one cell to another in an iterative manner
Although newer computers can run this code in a matter of milliseconds, it does not hurt if the sudoku solver code is optimized so that unnecessary iterations are avoided. However, what helps in speeding up the process is that we have read the numbers from the Excel spreadsheet and have placed in an array which resides in the memory. Any subsequent operations will therefore be carried out in memory rather than having to reference one cell at a time, and consequently will be much faster.
Using brute force to solve a Sudoku puzzle in Excel
All the steps that we have covered previously try solving Sudoku puzzles in Excel using conventional logic of eliminating likely numbers that can be placed in cell, one by one. However there are times that this approach can fall short. This happens in cases when we cannot reduce the list of likely number for the remaining cells any further and still have blank cells in the Sudoku puzzles. A normal sudoku solver in such cases will get stuck. Solving this category of Sudoku puzzles requires some amount of guesswork or in computer terms, brute force. So how do we do it?
Well, we simply take the first empty cell and apply the first value from its list of likely numbers to that cell. We then try solving for all the other cells using the steps described previously. If it works, fine. If it does not, we simply pick up the next likely value for that cell in the spreadsheet and apply that instead and try resolving for the rest of the cells. And so and so forth.
The last two sections deal with the basic of a Sudoku puzzle and would be helpful if you are learning about sudoku puzzles for the first time.
The steps that we employ in developing the Sudoku solver in Excel are:
1. Read the partially filled Sudoku puzzle from the Excel Spreadsheet into a 9×9 array.
2. Create a new 9x9x9 array and fill it up with the list of likely numbers for each cell of the 9×9 array.
3. Eliminate as many likely numbers in the 9x9x9 array as possible so that we are left with only one choice per cell (for as many cells as possible)
4. Once any particular cell in a 9×9 array has only one possible option left, we quickly fill up that cell and discard all the likely values that we might have had for that cell.
5. We iterate till such time that the Sudoku puzzle is either completely filled or we come to a standstill using this method.
6. If required, we use brute force and guess work to fill the remaining values.
Basics of a Sudoku Puzzle – Logic and Development
Sudoku is a number combination puzzle. The objective is to fill a 9×9 grid so that every column, every row, and each of the nine 3×3 square boxes contains each of the digits from 1 to 9 once each without repetition. Typically a Sudoku puzzle will feature a partially completed grid that the player has to fill in the remaining numbers. According to Wiki, the puzzle was invented by the American architect Howard Garns in the year 1979. Although being able to complete a Sudoku in itself is an achievement, it is possible for two players to play against each other. However, different Sudoku puzzles can and do differ in their difficulty levels with some of the tougher ones requiring some amount of guesswork.