BY NIKHIL NARAYANAN
(Note: The reader will need experience in some form of programming to understand the topic we are discussing here.)
I’m Nikhil Narayanan, an individual JAVA developer. I develop GUI applications via SWING and AWT. You may remember me from “JAVA: The Birth of a New Age”, a discussion centered on the explosion which JAVA caused in the tech world and the way it has retained its popularity to date.
Today, we’ll be discussing an interesting algorithm for a puzzle solver- Sudoku Solver instead of JAVA’s features, frameworks, or prominence.
A little discussion on this algorithm for all programmers out there!
Let’s talk about the way a brute force algorithm would solve a sudoku puzzle.
Brute Force Algorithm for Solving a Sudoku puzzle:
For those readers unfamiliar with the working principle of a sudoku puzzle, here’s a well-paced explanation of the Board:
A Sudoku Board consists of a 9*9 grid, divided into 3*3 regions or blocks.
The objective is to fill the 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that make up the grid contain all of the digits from 1 to 9. The puzzle provides a partially completed grid, which for most puzzles has a single solution:
Understanding the problem:
Now the question is: How would a computer solve this puzzle? Considering programmers who solve sudoku puzzles regularly themselves, they would probably add in extra functions and subprocesses which streamline which numbers they choose to fill in a particular grid box. But, what if you know absolutely nothing about solving a sudoku puzzle? What if you’ve never solved a puzzle in your whole life? You’re simply given the rules for filling a number into a particular grid box. How would the computer decide which number is correct?
The answer to this is- Perhaps using a brute force algorithm, try every possible combination of number substitution in the board. Then, using a checking algorithm, check which of the combinations follow the rules of the puzzle. Select that puzzle, and return it.
While this approach is a mathematical possibility, it is not a viable solution. The number of boards that would be presented as possible solutions will almost definitely exceed the memory delegated to your solver program. Another approach would be to combine the code which creates the solution for the board and the one which checks the substitutions(of numbers into empty cells) performed. This would be perfect. Except for the fact that the initial phase of solving a sudoku puzzle renders multiple possible solutions for a single grid box. But given the existence of only a single final solution, the other substitutions are almost definitely wrong. This will lead to problems when we solve the puzzle later on:
Consider a board:
As you can clearly see, we should fill the first subregion’s first row as follows: 9,5,7.
But look at the unsolved puzzle, the solutions at first glance do not seem binary.
In place of 9, I might have decided to substitute 5. This would not seem to be wrong initially as i am yet to fill some grid boxes. However, you will hit a point in the grid wherein there are no other solutions possible, because of a seemingly correct number substitution earlier in the game. Some readers may offer that the program can backtrack from the last incorrect substitution and continue solving the puzzle with other solutions. This would be a viable solution. Provided you knew which grid box you filled incorrectly.
This leaves us at a deadlock. Our program knows the rules to fill in a particular grid box but doesn’t know which substitution of the available ones is correct. The problem is further compounded when each grid box has multiple solutions, of which only one is correct, leading to a branching sort of solutions’ tree.
The Solution:
A simple solution is available for our program-
Solve the board linearly, first solve the grid boxes in region/block 1 then 2, up to 9, in order.
Create an array of boards, where you store boards that are possible solutions. A board where you will maintain a loop that parses each board while solving it, cell by cell.
Keep in mind that the original board will be parsed first, up to a point where there are multiple possible substitutions for one grid box, at which point, one board will be created for each substitution and filled with the substitution. After that, the parent board gets deleted. The loop starts parsing the children board from the cell where the parser left off in the parent board. We repeat the process till we obtain a solution.
- ENSURE that the code which substitutes numbers into blank grid boxes chooses numbers from an array that contains solutions. Solutions that are NOT already present in the region, specific row, or specific column.
- There might be multiple solutions for a particular grid box. When this happens, CLONE the board, i.e duplicate the configuration of the board. Then pass each substitution into an alternate version of the original parent board. Now remove the parent board from the array, add the children boards.
Meaning, suppose the particular grid box we are solving has possible solutions 1, 3, and 5. Create a COPY of the original board and fill one with 3 at the required grid box, one with 1, and one with 5.
Add these three to the array containing possible solution boards and remove the parent board. - Continue solving each copy of the board. Create children every time the parent board has more than one possible substitution at the grid box you are solving. Then remove the parent board.
- Boards at which you have made an incorrect substitution will stop providing children at a specific grid box. These boards will be automatically deleted while parsing the array of possible solution boards.
- Once the final grid box/ cell is solved, there will usually be only one child board left.
Provide the user with this board.
If you found this discussion intriguing feel free to visit my website for downloading my software or for reading similar discussions on JAVA programs/features!
Signing off,
Nikhil Narayanan.
