If you are going to write a computer program it needs to do something. Otherwise, there is no point. So I'm sitting around one day when I thought "it would be fun to write a computer program to solve Sudoku puzzles". And with that I was off.
A little background. Sudoku puzzles became all the rage a few years ago. When they first showed up on the "puzzle" page of the local paper I took a look. It seemed interesting so I gave it a shot. I was a total failure. I could see how you might go about solving one. But I had neither the skills nor the patience to be successful.
I could see what needed to be done. But scanning here and there looking for a good next move wasn't something I had the patience nor the eyeball to be successful at. But I could see how it could be done, in theory.
Now what I am not good at is, in this case, what a computer is very good at. Computers have infinite amounts of patience and are very good at detail. If you add in my analytical ability you have everything you need. And to my eye, the problem was difficult enough to be interesting without being so difficult as to demand more effort than I was interested in expending. So let's look at the rules of the game.
A Sudoku puzzles consists of a 9 x 9 grid. Each box contains either a number or an empty square. You solve the puzzle by filling all the squares with numbers. But what constitutes a "legal" move? That's pretty simple too. Each square must end up with one of the digits running from one to nine. That's extremely simple. It is the additional constraints that make things interesting.
You can't duplicate numbers. There are nine squares in the first column. If there is a "5" in one square in the column then none of the other squares in the same column can contain a "5". In the end everything just fits. There are nine squares in a column and 9 digits. So it's a matter of putting the digits - one through nine - into the squares in the right order. And, if that was it, then the problem would be trivially simple.
But there is a similar row rule. There are nine squares in a row and nine digits. So it is again a matter of arranging all nine digits in the correct sequence so that each fills a square. So now things are more difficult but not all that difficult.
Imagine viewing the grid along the diagonal. In the first diagonal you put a "1". (There is only square in the first diagonal because it is up against a corner. In the next diagonal you put all "2"s. In the next, all "3's, and so on.
Once you have filled nine diagonals with "1" through "9" start over. fill the next diagonal with all "1"s and the one after that with all "2"s. Keep going and you will have a "solution" that meets the "no duplicates in a row" criteria while also meeting the "no duplicates in a column" criteria. So, to make things more interesting a third rule is added.
The 9 x 9 grid is divided into nine 3 x 3 sub-grids. The first sub-grid consists of rows 1-3 and columns 1-3. The second one consists of rows 1-3 but columns 4-6. When you are done you will have 9 sub-grids with the last one consisting of rows 7-9 and columns 7-9. Each sub-grid contains nine cells so you impose a "no duplicates" rule within each sub-grid. With this third rule the puzzle becomes hard but not impossible.
The way things work is that a grid is published. It has some but not all squares filled in. You are supposed to take it from there and figure out what number to put into each of the empty squares. Here's the starting position from a puzzle that was published in the local paper several weeks ago. (I have used white space to highlight the sub-grid boundaries):
Column: - 1 2 3 4 5 6 7 8 9
Row: 1 - * 1 8 * * 9 2 * *
Row: 2 - 4 * * * 3 5 7 * *
Row: 3 - 6 * 3 2 7 1 4 * *
Row: 4 - * 4 * * * * * 6 *
Row: 5 - * * 5 3 6 4 1 * *
Row: 6 - * 3 * * * * * 4 *
Row: 7 - * * 9 4 1 3 6 * 2
Row: 8 - * * 1 5 2 * * * 4
Row: 9 - * * 4 7 * 6 5 3 *
So what do we do next? Well, there's the brute force method. Row 1 - column 1 is empty ("*" denotes empty). We can try a "1" there and see what happens. That doesn't work because row 1 - column 2 already has a "1". But we can move on and try "2" and then "3" and so on. Then we can move on to the next empty square at row 1 - column 4 and do the same thing. After trying a bazillion combinations we will eventually hit on to a legal solution.
But, boy oh boy, will we have to try a lot of different combinations. Computers are very patient so this would eventually work. It is called a "brute force" method. You just try all the combinations until you find one that works. There are better ways.
And that was the one insight I developed about how to proceed. I came up with the idea of a "forced move". Look at square (1,4) - short for row 1 - column 4. If you work through all of the combinations then only move that works is "6". "6" is a forced move. Go ahead and check. You will see that 1-5 and 7-9 are all excluded by other squares that have already been filled in.
So what I had my program do was to look for forced moves. It boringly checked square (1,1) then (1,2) and so on. If the square was already filled it moved on. For each empty square it first tried "1", then "2", and so on up to "9". It counted the number of moves which were "legal", that didn't violate any of the constraints. I called this number LMC for "legal move count". The program moved along calculating the LMC for each empty square.
As it moved along it noted when it found a square whose LMC was lower than all the previous LMCs it had encountered. It remembered where it had found that move (and forgot what it had previously remembered about the old lowest LMC champ). And it remembered for that move the first (lowest - it tried 1 - 9 in that order) legal move it had found for that square. Finally, as soon as it found a square with an LMC of 1 it quit looking. LMC=1 squares are forced move squares.
So the program worked by first playing all the "setup" moves, those moves printed in the paper. Once that was done it tried the same thing over and over. It tried to find the square with the lowest LMC. It did this by scanning the entire grid as I have outlined above. It stopped and "played" the move if it found a square with an LMC of 1.
And if it got to the end, having scanned all 81 squares, and had found no empty squares then it said "I'm done". And for easy puzzles, that's it. It turns out that there is always at least one square with an LMC of 1, a forced move. The program finds it and plays it. Then it goes back to the top and starts a new scan. Eventually all the squares are full and the program is done. In the case of the puzzle above that looks like this:
Column: - 1 2 3 4 5 6 7 8 9
Row: 1 - 7 1 8 6 4 9 2 5 3
Row: 2 - 4 9 2 8 3 5 7 1 6
Row: 3 - 6 5 3 2 7 1 4 9 8
Row: 4 - 1 4 7 9 8 2 3 6 5
Row: 5 - 9 8 5 3 6 4 1 2 7
Row: 6 - 2 3 6 1 5 7 8 4 9
Row: 7 - 5 7 9 4 1 3 6 8 2
Row: 8 - 3 6 1 5 2 8 9 7 4
Row: 9 - 8 2 4 7 9 6 5 3 1
Remember, that as we fill in moves fewer and fewer moves remain valid. When we made our move of placing a "6" in square (1,4) that rendered "6" as an invalid move for any other square in row 1, column 4, and the sub-grid consisting of rows 1-3 and columns 4-6.
In solving the above puzzle the computer first places a "6" at square (1,4). For its next move it places a "4" at square (1,5). For its third move it places a "5" at square (1,8). It continues to proceed in this manner for move after move until it finally places a "1" in square (9,9). On each fresh move it is able to find a square with an LMC of 1. If you have a good enough eye and enough patience, you can too.
But what if the puzzle is harder? Then what? Well, the program is on the lookout for things going wrong. What if it finds an empty square for which there are no legal moves? It sounds like the puzzle has no solution. But there is another possibility.
In the easy puzzle listed above at every stage it is possible to find a forced move, a square with an LMC of 1. But that is not true when it comes to more difficult puzzles. With more difficult puzzles some scans may not turn up a square with an LMC of 1.
Remember, what the program actually does is to look for the square with the lowest LMC. It is certainly true that we don't want to bother with squares that have an LMC of 2 or more if we can find a different square with an LMC of 1.
But with more difficult puzzles sometimes a scan of all the unused squares in the puzzle does not turn up one with an LMC of 1. In that case the program just goes with a square with the lowest LMC it found.
In all the puzzles I have looked at the program invariably finds a square with an LMC of 2 if it can't find a square with an LMC of 1. But the program can deal with situations where the lowest LMC it finds is higher. Here's how that works.
If, on a scan the lowest LMC that is encountered is higher than 1, then the program selects the first square it encountered with that LMC, whatever it is. It plays that square and "guesses" whatever the lowest legal move is. It then goes on to find the next move. If we get to the end and have found a valid solution, hurray! We won.
But that may not happen. We may end up encountering a square that now has no valid moves. That's where a process that is easy for a computer to do and often hard for a person to do comes into play. We don't give up. We do what's called in the computer game "backing off". So how does that work?
As things are going along the computer keeps track of every move it has made. And it keeps track of the order they have been made in. And it remembers the LMC of each move.
Now some moves are special. They are the moves that were used to load the grid with the "setup", the initial configuration printed in the newspaper. These moves are flagged as "s" for setup moves. Later moves are flagged as "n" for normal moves. The first several moves are "s" moves. After that, the moves are all "n" moves.
So when a problem (no legal move) is detected here's what happens. The first thing that happens is that the move we were trying to make is abandoned. All trace of its existence is erased. Then the last move on the "queue" (the data structure used to keep track of moves) is examined. If it is an "s" move then the puzzle is unsolvable and it's time to quit. But it should be an "n" move.
The LMC of the move is examined. If it's 1 then the move is "backed off". All evidence that the move was every made is erased. Then we go back and examine the next oldest move to see what we find.
If, however, the LMC is greater than 1 there is something we can do. We can take a different "fork in the road". Here we take advantage of the fact that we always try the lowest legal value first. Let's say the LMC of the move is 2 and the value we used was "4". That means that besides "4" there should be another move that is higher than "4" that is also legal.
We go looking for it. Let's say it is "6". We then change the move to use "6" instead of "4". We also reduce the LMC by 1. In our example, the LMC is now 1 so, if the "back off" logic again reaches this point, then it would back the move off and keep looking. If perchance the LMC had been 3 it is now 2. So, if we later reach this point, then we can again look for a legal move that is higher than "6".
It is possible, at least theoretically, that we won't be able to find a higher legal move. But that means that the program has screwed up and it is time to look for code to fix.
But if all goes as it should we back off until we find a fork in the road. Then we go down a different fork. Once we've done that we return to business as usual. We jump back in the top and use the usual code to go looking for a move with an LMC of 1 to add onto the list of moves right after the one we ended up modifying.
It may be necessary to do this "two steps forward, one step back" dance several times. And it is common to end up putting the same LMC = 1 move on the stack only to later have to back it off as we look for an "LMC higher than 1" fork in the road. Then, still later after we have taken that different path, we end up just adding the same move back onto the move list again. But, after a certain amount of "toing" and "froing", we should end up with a set of legal moves that ends up filling the grid up completely.
So that's the rest of the logic my computer program uses to solve Sudoku puzzles. It has solved all of the puzzles I have presented it with successfully. And it solves them instantly.
It takes me a minute or so for me to create a file with the setup moves in it. It takes the computer a second or so to print out the "before" (setup) and "after" (solution) grids. But solving the puzzle is essentially instantaneous. Computers are very good at doing a lot of this sort of thing extremely quickly.
And with that, let me give you some background on Sudoku. It is part of a group of mathematical puzzles called "Latin Squares". They have been studied extensively for a period going back more than a hundred years. And it turns out that the origins of Sudoku also go back more than a hundred years.
A puzzle similar to Sudoku was first published in a French newspaper in 1892. Another French newspaper published a puzzle that was almost identical to Sudoku in 1895. About twenty years later they went out of fashion and stayed that way for a long time.
Then a puzzle identical to Sudoku was published in a Dell puzzle magazine in 1979. There it was called "Number Place". (Sudoku puzzles are regularly but infrequently called Number Place to this day.)
It was likely invented by a man named Howard Garnes. Mr. Garns was well known at the time in puzzle creation circles. No one knows if he was familiar with the earlier French puzzles but he was probably very familiar with Latin Squares. He died in 1989 before Sudoku became a giant phenomenon.
The Japanese attribution is not completely unreasonable. That's where the puzzle first became widely popular. It was introduced in a Japanese newspaper in 1984 as "Suji wa dokushin ni Kagiru". This unwieldy name was quickly shortened to Sudoku. It quickly developed a large and loyal following in Japan. So. it soon could be found in many newspapers there.
In 1997 Hong Kong judge Wayne Gould saw a Sudoku puzzle in a Japanese bookshop. He spent six years developing a computer program to quickly crank out new puzzles. The task he set out for himself was much more difficult than the one one I tackled. But, once he had it working, the result was a nearly inexhaustible supply of new puzzles. And they could be made available inexpensively.
He then sold the Times of London newspaper on the idea of regularly publishing Sudoku puzzles. They first published one in 2004. The first Sudoku puzzle appeared in a US newspaper later that same year. And the rest, as they say, is history.
Sudoku has attracted a lot of attention from both professional and amateur mathematicians. They had long been studying various kinds of Latin Squares when it came along. Sudoku fit right in.
So a lot is known about the mathematics behind the game but I am going to spare you all of it. I am also going to spare you from a discussion of the many variants of the game that have been developed in response to its popularity. If you care, the rich literature on this subject is easy to find.
As for me, I have moved on but not very far. There is a puzzle called Numbrix that newspaper columnist Marilyn vos Savant champions.
As a programming challenge, it looks very similar to Sudoku. So I am now writing a program to solve Numbrix puzzles. I expect to be able to reuse a lot of the code I wrote for my Sudoku program.
I am making slow progress. But this is because I'm not putting that many hours into it. It is, after all, a time waster. I only work on it when I have time to waste.
So that's what I am now up to.
No comments:
Post a Comment