I’m finally starting to think about sudoku, and am having a lot of fun with it.
I’m taking an online class on artificial intelligence with udacity, and sudoku is being used to illustrate some ideas used to solve constraint satisfaction problems.
Naturally, before solving sudoku puzzles by using the algorithms described in the online course, I thought about what I could do with a brute force approach, which naturally led me to think about variants of sudoku where brute force is a feasible approach. And that’s what I’ll write about here.
But first, let’s recap the basics. To begin with, what is sudoku?
It’s a puzzle that was popularized about thirty years ago in Japan. The word “sudoku” is Japanese (数独) and means “single number”: “su” means number and “doku” means single.
It’s a puzzle that involves a grid of grids, namely a by grid where each cell is itself a by grid (i.e. a sub grid), so that ultimately we have a by super grid. There are various ways of placing the numbers in each by sub grid (without repetitions) so that the columns and rows of the by super grid each have no repetitions.
A sudoku puzzle takes a partially filled super grid as input and asks for a filled super grid as output.
As you might guess, there’s nothing special about the number , and we could just as easily do all of the above with the number , with the only change being that the numbers from to are replaced with the numbers To make the discussion easier, I’ll continue for a while with the by variant of sudoku, instead of the by classic sudoku that everyone knows.
An example of a by sudoku puzzle would be
and a solution (actually the only solution) would be
For programming purposes, I’m going to encode the puzzle as a sequence of characters that correspond to scanning the by super grid from left to right and top to bottom. That results in the sequence
where the missing numbers are indicated by a period.
A similar encoding is done for the solution, namely
With that in mind, let’s consider a simple brute force approach to solving the puzzle.
Given an input sequence , for example “4..3…1..3.2…”, the first step would be to construct the collection of all possible filled super grids The second step would be to consider every element of in turn, and check to see if and are the same if we ignore the periods in If we find such an we can stop with a solution And if we don’t find an after going through , then there is no solution.
It’s pretty straightforward, and a nice little implementation bonus is that we can use the input as a regular expression pattern, since a period represents any character in regular expressions.
To see how feasible this might be, let’s try to get some idea of how large might be.
An elementary upper bound holds because each of the entries in the super grid is restricted to possibilities. This is something that computers can handle, and it looks like a brute force approach will work.
Note that for “classic” sudoku, the corresponding upper bound is which is not something that computers can handle.
And, we can do much better than that. By considering just the upper left sub grid, there are possibilities. A neighboring sub grid is then restricted to values, so that we have an upper bound of There’s now no question: this can be done by brute force.
It’s easy enough to code this up, find all the elements of , and count them to get . I did just that and you can see the code on github. Just execute “python list_all_22.py | wc -l” at the command line to get . It takes seconds on my computer.
And, of course, I’m not the first person who’s been down this road. This result is well known, and can be seen at numerous places, including wikipedia.
To finish up this post, I’d like to mention a few related items.
Firstly, the same reasoning I used to find a a bound of in the by case can be used to find a bound of for the by case. And, the actual value of in the classic by case is known: it’s Brute force isn’t going to cut it.
Secondly, generalized sudoku super grids are square, but the sub grids can be rectangular. An by sudoku consists of a super grid of rows and columns using the numbers . The super grid is viewed as an by grid where each cell is an by sub grid. The case where is the case of by latin squares, which have been studied in mathematics for over two centuries. Sudoku is a fairly recent puzzle, but it’s not completely without precedent.
Thirdly, by sudoku puzzles are out there. One source is at worksheets.com
Finally, a big shout out to udacity. I’ve had an account there for five years, have tried out a number of their courses, and am very impressed with their quality.