Thoughts on developing a SUDOKU solver and a MATLAB implementation of one...
When I decided to implement a SUDOKU solver in MATLAB in order to become familiar with MATLAB's programming facilities, some decisions were move obvious than others. For example it was pretty clear that the puzzle grid is very naturally represented by a 9x9 matrix. Digits 1-9 in matrix elements would represent the given values or ones that were filled in by the solver. It naturally followed that yet-unsolved elements could be represented by zeros. This worked out very nicely thanks to MATLAB's 'find' builtin which distinguishes between zero and non-zero values as its basis for answering the question "What's filled in in this matrix?"
Less obvious was the fact that different levels of SUDOKU complexity required different angles of attack. 'Simple' to 'Medium' level puzzles can be solved (both by a computer and human solver) by repeated applications of scanning. In other words, values can be filled in unequivocally based on other values in the matrix, then other values become 'obvious' based on these values, and so on until the entire matrix is filled in. for 'Hard' and 'Evil' complexity SUDOKU instances, this approach is insufficient. Both the computer and a human solver need to take an analytical (or failing that, a guessing) approach, essentially making pencil marks on the grid and seeing how that decision pans out, ready at any time to discover an inconsistency and back out to a previous point.
In fact, the backtracking approach alone is sufficient to solve any SUDOKU. One could brute-force his way through the entire grid, trying every possible combination unguided by any reason, and still solve the SUDOKU in a fairly reasonable amount of time (there would be less than 9^3 = 729 permutations to try, and for the computer this is not too much.)
But we can do a lot better than this!
In addition to the recursive machinery, the simplest backtracking approach would need two additional facilities: one to recognize when the puzzle has been successfully filled in, and one to recognize that the puzzle has reached an invalid state and cannot possibly be solved. The first will tell us when the entire procedure is complete, while the second will tell us when we've painted ourselves into a corner and it's time to try something else.
I'll get back to this point in a minute. Let's talk about the basics again.
Sudoku consists of a 9x9 grid which is broken down into 9 3x3 regions (which I call quads from time to time for no reason.) The sudoku grid starts off with some places in the grid filled in with digits from 1 to 9, and the solver must fill in the rest of the spaces, also with digits from 1 to 9.
There are 3 constraints to the above: A digit cannot repeat in any of the 3x3 quads (or to put in another way, each quad contains digits 1 to 9 exactly once,) a digit cannot repeat in any of the rows (in other words, each row contains each digit from 1 to 9 exactly once,) and the same holds for columns as well.
A simple scanning approach is to go through each of the 81 positions in the 9x9 matrix and if it's empty, ask the following question: What numbers are NOT in the same quad and NOT in the same row and NOT in the same column? Let's say we're examining a certain position. The quad this element is in contains digits 1, 2 and 5. The row contains 2, 5 and 9. The column contains 6 and 8. Therefore the digit that goes in this blank CANNOT be: 1, 2, 5, 6, 8, or 9. It must, therefore be one of 3, 4 or 7. In this situation we would still have to 'guess' but if (let's say) the column also contained 3 and 4, then the only possible value remaining would 7. If we can eliminate 8 of the digits because they're present in the row, column, or the 3x3 region, then the remaining digit must be the one which goes into this blank. Note that once the Matrix Scan fills in a value, it makes it possible for a subsequent pass of the Matrix Scan to fill in additional values based on the new information.
Another equally simple approach is to consider each of the 9 regions. For each region, generate a list of digits which are not yet present in the region. For example if the region looks like this...
1 0 3
... then the missing values are 4, 8 and 9 (remember, 0 means a blank which is yet to be filled in). There are 3 missing digits and three places where they can go. Let's consider the first missing digit, 4. It could go into any of the 3 empty slots. However, imagine that a region below this one had a 4 in the second column. This means that our region cannot have the 4 in the second column. That means the 4 can only go into the 3rd column, between 3 and 7. If for some digit which is missing from a region, we can reduce the possible locations in that region to 1, then that location must contain that digit. We can add it into our puzzle.
Quad Scan and Matrix Scan are not mutually exclusive: one may be able to fill in digits which the other one cannot. It should be clear that a successful pass of a Matrix Scan means that there's more data for either a Matrix Scan or a Quad Scan to work with on subsequent passes, and vice versa. In fact, I mentioned above that 'Simple' and 'Medium' Sudoku puzzles can be solved by scanning alone. Successively applying the Matrix Scan and the Quad Scan as long as at least one of the two provides at least one additional solved digit can solve such a puzzle.
Since my purpose was to learn how to program in MATLAB, I present the entire implementation of Matrix Scan as a MATLAB m-file. It's quite long due to being extremely well documented. There are only about 20 lines of executable code but with comments the thing runs into about 280 lines. So if you want to learn MATLAB, read it. Of course the comments may provide some insight into the algorithm even if you don't care about MATLAB specifically. Of course, if you REALLY don't care you can skip the whole listing ;)
The code for Quad Scan is a little longer mainly because there are several checks for conditions which allow us to leave early. This becomes more relevant when we're dealing with the recursive variant of the solver. Again, the details are in the comments, but this file is documented more sparsely since many of the concepts were introduced in the Matrix Scan docs.
Let's get back to solving the hard sudokus, the ones which require an analytical/guessing approach. First, how do we distinguish such a problem from one which can be scan-solved? This may be a hard question to answer theoretically (is it the halting problem?) but in practice it's easy - if the Quad Scan / Matrix Scan combo runs its course in a loop until it produces no further improvement, and if at this point the matrix still contains blank slots indicated by 0s, we know it's time for the harder stuff.
I promised to get back to discussing the machinery needed for identifying guesses which had gone wrong, leaving the matrix in an unsolvable state. I get back to it now because we've already written not one but two of such checkers :)
Consider Matrix Scan for a second. It iterates over each empty spot in the grid, trying to narrow down the digits which could go there. We consider it a success if we've whittled it down to one possibility. After all, that means we've now got the solution for that blank. But what if Quad Scan reduces the possible digits which would go into a spot even further - to none? Consider a spot which is in a region containing 1,2 and 3, the row contains 4,5 and 6, and column contains 7, 8 and 9. We're left with no options for this spot which would not violate one of the 3 rules of SUDOKU. Therefore we know that the current conditions of the grid are invalid, and if we got here by taking a 'guess,' then it's time to backtrack!
Nearly the same thing for the Quad Scan. If a region is missing some digit, but the digit cannot go into any of the free spots in the region because of row or column conflicts, then we know we're in an invalid state. Again, time to backtrack!
Now that we know how to detect invalid states, we can talk about how the 'advanced' solution of guessing and backtracking itself will work. Let's say we've run Quad and Matrix scans until they've stopped producing any results. Now what? Now it's time to guess.
Before we discuss HOW to guess, let's talk about what we're going to do. We're going to take 'some' spot in the matrix and fill it in with 'some' digit. Then we're going to play dumb and pretend this is a new puzzle to solve, essentially passing it againt to the program. If the program can solve it (including by additional guessing) and return the solution back to us, great! If not, we detect that our attempted guess has led to an insolvable puzzle and we better remove our guess and try something else!
Great, fill 'some' spot with 'some' digit and hope for the best! How do we decide what to put, and where? There are a few types of guesses that we can do:
The dumbest guessing mechanism is to grab the first blank spot in the matrix and shove a random digit in there and hope for the best. If things don't work out, we'll shove another digit in there. One of them must be the right one!
Brute Force guessing will go into the first free spot and stick any number in there (most likely it will try 1, failing that 2, then 3, etc.) But it may be quite obvious that not all numbers go into all spaces. Somewhat similar to what we do in Matrix Scan, we can easily remove the impossible digits from the list we're going to try. So if the spot we're trying is in a region which contains 1 and 9, a row that contains 4 and a column that contains 5, then we should be smart enough not to try those numbers! Instead we should limit ourselves to 2,3,6,7 and 8. This limits the amount of pointless work we have to do.
In the example above, we reduced the number of digits we will try from 9 to 5. However, if the right digit is '8' then we will have wasted the work of processing 4 incorrect digits before arriving at 8. Since the wrongness of each guess may not become apparent until much lower in the recursion stack, it pays to limit the risk of being wrong as much as possible.
So far we've been taking the first free spot in the matrix as the target for our guess. However this may not be the best place to start. For example, we may not have been able to whittle down the list of digits which go in that spot. If we have 8 remaining options, we could guess wrong 7 times! What if there's some other spot in the matrix which only has 2 options for the digit that would fit. Guessing there means we're wrong no more than once (in fact, we have a 50% chance of our guess being correct!) It makes sense to prioritize the guessing to the slots in the matrix that have the fewest options. This dramatically reduces the time wasted on chasing down the wrong guesses.
Solve Sudoku is a function which implements all of the logic discussed above. It calls Matrix Scan and Quad Scan in a loop until no further improvement happens. Then we check if the puzzle is solved. If not, it's time to make a guess and recursively call Solve Sudoku with the newly formed puzzle.
Sudo Driver is a simple driver function which demonstrates how to create 9x9 matrices representing the initial state of the Sudoku, and how to pass it to Solve Sudoku. This function contains 3 matrices that you can use to test Solve Sudoku. The first one is a 'Medium' difficulty one which is solved by scanning alone - the recursive machinery does not kick in. The other two are 'Hard' and 'Evil' respectively. The hard takes 3 recursive invocations to solve while the 'Evil' requires 9. The puzzles take 1, 2 and 4 seconds to solve on a Pentium Celeron 1.8 although the small gap between the Medium puzzle and the Hard one suggests that some of the expense is associated with startup.
This page contains 4 files with the .m extension. These are MATLAB function files. MATLAB has an unfortunate limit of one function per file.
.m files are plain ASCII files which contain MATLAB commands and (in my case) oodles of insightful comments on both MATLAB builtins and paradigms, and the algorithms at hand. So you may want to read these files even if you don't have MATLAB.
Questions? Comments? Marriage proposals?
ed d0t markovich at gmail d0t com