Copy the below 9×9 grid and complete it so that each row, each column, and each 3×3 box with a wide margin contains each of the numbers 1 to 9 exactly once.
Since you are reading an article on Sudoku puzzles’ mathematics, this is probably an easy exercise for you already. On this webpage, we will not focus on how to solve the New York Times puzzle faster than the person sitting next to you (although we will learn some advanced solving tricks), but on aspects of Sudoku that are interesting from a mathematical perspective. By a Sudoku puzzle, we will mean a 9×9 grid puzzle like the one above, unless something different is stated explicitly.
You might wonder how many possible different 9×9 grids there are. What about N2 x N2 grids for any positive number N? And when will the New York Times run out of Sudoku puzzles? We will count Sudoku puzzles in section 1. Just like a Sudoku solver presented with an incredibly hard puzzle, a Mathematician will be interested in when puzzles have unique solutions. Section 2 is the beginning of a discussion on the existence and uniqueness of answers to Sudoku puzzles. In sections 3 and 4, we look at solving algorithms for Sudoku puzzles. One of them will be relatively straightforward in theory but impossible to use without a computer. At the same time, the other is more complicated but enables a human being to solve any Sudoku puzzle with a solution. Section 5 explains how Sudoku puzzles are related to graphs and why this connection is so useful.
I encourage you to attempt the activities that you can find throughout the sections. You can see the outlines of solutions in section 6 and some further information sources in section 7.
What do you get out of all of this? A new way of looking at Sudoku puzzles, the right to claim that there is no Sudoku puzzle you can’t beat. And, unless you have taken university-level Math or Computer Science classes before, mastery of some mathematical concepts for which you will find applications again and again in your life. Have fun!
Counting Sudokus
A first look at counting Sudokus
How many (complete!) 9×9 grids are there, i.e., how many different ways can one fill an empty 9×9 Sudoku grid while following the Sudoku rules?
Let’s do a rough estimate. Suppose we have an empty grid and fill it in, ensuring that each of the numbers from 1 to 9 appears exactly once in each row, column, and 3×3 box with thick margins.
Each cell must contain a number between 1 and 9, i.e., there are nine different possibilities. There will be significantly fewer possibilities in most cases since it is not allowed to have two copies of the same number in any row, column, or 3×3 box with a thick rim. But let us ignore this detail and state that for each cell, there are no more than nine ways of filling it in.
Now imagine filling the grid in, starting with the top-left cell and then proceeding row by row, from left to right. Filling in just the first cell, we have nine choices. Filling in the second choice, we have no more than nine options. For each of the possibilities that we could choose when filling in the first cell, there were no more than nine possibilities for filling in the second cell. In total, that gives us at most 9×9 different ways of filling in the first two cells. For the third cell, we again have no more than nine various ways of filling it in. For each of the 9×9 combinations we could choose for the first two cells, there are nine ways of filling in the third cell. Therefore there are at most 9x9x9 ways of filling in the first three cells.
We can continue the argument for all other cells, observing that there are at most 9^81 ways of filling in the first n cells. There are 9×9 cells on our Sudoku grid. Thus no more than 981 different complete Sudoku grids of size 9×9. A useful calculator will tell you that 981 is approximately 2×10^77, or, in words, two hundred quattuorvigintillion. That’s not too far from the number of atoms in the universe (Observable Universe).
Let’s put our result into context: we have only shown no more than complete 9^81 Sudoku grids of size 9×9. In reality, there could be many fewer. Mathematicians call an estimate like ours an “upper bound”: we have not computed the actual number of complete 9×9 Sudoku grids, but we have shown that there are no more than 9^81.
Improved Count
Activity 1: Modify the argument from above to show no more than (9x8x7x6x5x4x3x2x1)^9 = 362880^9, i.e., about 1.1×10^50 different 9×9 complete Sudoku grids. Use the fact that each row can contain each number at most once.
To understand the idea for completing activity one better, we could draw up a 9×9 table like the following one. Each entry of the table is no smaller than the number of ways of filling in the corresponding cell on a Sudoku board if you fill in the panel from left to right, top to bottom.
To estimate how many ways of filling in the board, there can at most be, we multiply the maximal number of ways that there are of filling in each of the cells. It is now easy to see where the product (9x8x7x6x5x4x3x2x1)^9 comes from.
Doing the previous activity, you were probably surprised to see that using the information that each row must contain each number from 1 to 9 exactly once improved our upper bound a lot. That was because once you have filled most of a row in, there is a little choice left for completing the remaining cells in that row! For example, once you have completed the first eight cells of the first row, there was only one number left that you are allowed to put into the 9th cell of the row. For that reason, there were exactly as many ways of filling in the first eight cells of the top row as there were ways of filling in the entire top row. Your solution for activity 2 took this into account. Simultaneously, the original (very rough) estimate answering the question from the top of the page just used that the total number of possibilities could not increase by a factor larger than 9.
Activity 2 (harder): Look again at your work from activity 1. Aside from the last cell in each row, there are at least 12 more cells where it is evident that there is only one way of filling it in if you fill in row by row, left to right, starting at the top. Draw up an empty Sudoko grid and place crosses in those 12 cells. Which number of possibilities did you use for each of those cells in your work for activity 1? Call those numbers N1, N2, …, N12. Use the product of the numbers N1 to N12 together with the upper bound from activity 2 to explain why (9x8x7x6x5x4x3x2x1)^9/(9x8x73x6x5x43x3x2) = 3.8×10^41 is an upper bound for the number of complete 9×9 Sudoku puzzles. We have established that there are, in fact, no more than 3.8×10^41 full Sudoku grids!
Clever Counting
We are now pretty comfortable using Sudoku’s rules to eliminate ways of filling in a Sudoku grid. Let’s compute one more upper bound. It will be significantly better than anything we have done so far. Below is a 9×9 table. The number in each cell is the number of ways in which I can fill in that cell while making sure that each number from 1 to 9 occurs at most once in each row. We again proceed row by row, from left to right, top to bottom. Once I have filled in a cell, I have one choiceless in the next cell along the row!
Here is another 9×9 table. The number in each cell is the number of ways in which I can fill in that cell while making sure that each digit occurs at most once in each column. If there are already some numbers in a given column, then I have a smaller choice for the next cell in that column to fill in!
Here is another 9×9 table. The number in each cell is the number of ways in which I can fill in that cell while making sure that each digit occurs at most once in each 3×3 box with a wide margin.
For each cell in the 9×9 Sudoku grid, we now have several ways of filling it in if we observe the rule about rows (table 1), the rule about columns (table 2), and the rule about 3×3 boxes (table 3). So how many ways of filling a given cell are there? Well, however many there are, there can’t be more than the number in the corresponding box of table 1, nor more than the number in the corresponding box of table 2, nor more than the number in the corresponding box of table 3! Let’s draw another table. In each cell, we will put the smallest number of the corresponding cells in tables 1, 2, and 3. Here is the table with the smallest numbers:
There are no more than nine ways of filling in the first cell in the top row and no more than eight filling methods in the second cell. There are no more than eight ways of filling in the second cell for each possibility for the first cell. There are, therefore, at most 9×8=72 ways of filling in the first two cells. According to the table, there are no more than seven choices for the third cell, thus no more than 9x8x7 ways of filling in the first three cells. Proceeding this way row by row, we end up multiplying all 81 entries of table 4. The product is about 1.5×10^31, quite a bit better than our previous upper bound!
Brute-force counting
In 2005, Bertram Felgenhauer and Frazer Jarvis used a computer to calculate that the actual number of complete Sudoku grids is 6,670,903,752,021,072,936,960, that’s about 6.7×10^21. Their method is too involved to describe here, but I encourage you to read their 5-page paper if you know the programming language C++. It’s available at Frazer Jarvis’ paper.
You might wonder why even our best upper bound was much bigger than the actual number of complete Sudoku grids. The answer is that for each cell, we only used the restrictions imposed by the condition on the row, or the column, or on the 3×3 box. To get an exact count of all complete Sudoku puzzles, we would have had to proceed much more carefully rather than just an upper bound. That is explored in the next activity.
Activity 3: This example illustrates why our last estimate (part “Clever counting”) was still far from the actual number of complete Sudoku grids. Below is a Sudoku grid that is partially filled. How many ways are there of filling in the red box (if you fill the grid row by row, left to right, top to bottom), and how does this compare with the number of ways we had in the corresponding box of table 4 in “Clever counting”?
How many clues?
In the last section, we counted ways of completing an empty Sudoku puzzle. Suppose your best friend gives you a self-made Sudoku puzzle like the following one.
After a while of staring at it and not getting anywhere, you might wonder if the puzzle “actually has a solution.” It would be nice to know answers to the following questions: is there an easy way to decide if there is more than one way of completing the grid? Is there an easy way to determine if it is possible to construct a given grid?
The answer is disappointing. In general, it is tough to decide (without the use of a computer) if a Sudoku puzzle has a solution and if there are several ways of completing a partially filled-in grid.
Uniqueness of solutions
Activity 4: Complete the Sudoku puzzle on the right as much as possible. What (surprising?) fact do you observe?
Activity 5: Assume you are given a 9×9 Sudoku in which only three cells are empty, and all other cells were filled incorrectly. Also, assume that the puzzle has at least one solution. Explain why there can be at most one solution.
In activity 4, we learned that a 9×9 Sudoku with only four empty cells still need not have a unique solution. On the other hand, we show in activity five that every solvable 9×9 Sudoku with no more than three empty cells has at most one solution.
Here is one more exciting conjecture: the smallest number of filled-in cells needed for a 9×9 puzzle with a unique solution is probably 17 (Mathematics of Sudoku). Several puzzles have been found that require only 17 filled-in cells for a unique solution. It is doubtful (based on an extensive search using computers) that puzzles that have unique solutions with only 16 clues or less exist.
Aside from those results, there are no easy-to-use criteria to decide whether a Sudoku has a unique solution or not. However, Sudoku puzzles in newspapers or books usually contain puzzles with unique solutions only.
Existence of solutions
Given a Sudoku puzzle, can we decide systematically if there is at least one way of filling it in? Yes, we can. However, in many cases, it’s quite a lot of work. We will learn about a suitable method in one of the later sections.
Solving Algorithms (I)
In this section, we will explore algorithms that solve Sudoku puzzles. A vital aspect of an algorithm is that it terminates. For a Sudoku solving algorithm, that means that the procedure will eventually end and tell us if a given Sudoku has a solution and if yes, then we want to know at least one answer (there could be many). Note that “looking at the puzzle and trying to figure it out” would not qualify as an algorithm since the solver might never finish.
The “Simple Solving Algorithm”
Our Sudoku counting methods from an earlier section suggest a very simple Sudoku solving algorithm. Before you read on, think a couple of minutes and try to come up with it yourself.
Here is the first solving algorithm. Since it’s straightforward, we will call it the “Simple Solving Algorithm.” We start with a partially filled Sudoku board and assume that the Sudoku is not yet complete for simplicity’s sake.
- Enumerate all empty cells in typewriter order (left to right, top to bottom)
- Our “current cell” is the first cell in the enumeration.
- Enter a 1 into the current cell. If this violates the Sudoku condition, try entering a 2, then a 3, and so forth, until
- a) the entry does not violate the Sudoku condition, or until
- b) you have reached 9 and still violate the Sudoku condition.
- In case
- a) if the current cell was the last enumerated one, then the puzzle is solved. If not, then go back to step 2 with the “current cell” being the next cell.
- b) if the current cell is the first cell in the enumeration, then the Sudoku puzzle does not have a solution. If not, then erase the 9 from the current cell, call the previous cell in the enumeration the new “current cell,” and continue with step 3.
If you know MATLAB (or any imperative programming language), you might like to look at my MATLAB implementation of the algorithm. It’s not optimized for speed but readability. The code comes in two parts: anydouble.m, which checks whether there are any numbers that appear twice in any row, column, or 3×3 box, and solve_sudoku.m, the main file. To solve a Sudoku puzzle, download the two files, enter the Sudoku matrix that you want the algorithm to solve at the top of solve_sudoku.m (an example for the formatting is included in the file), save, and run solve_sudoku.m.
I tested my code using the following puzzle. It’s rating is “fiendish”.
The Sudoku solver took about 5 minutes to come up with the following solution:
Activity 6: Implement the simple solving algorithm in your chosen programming language. Matlab has many useful built-in functions that would help you (for example, the “find” function), but this is also a fun exercise if you have a basic knowledge of C, Java, or even some functional programming language.
Activity 7: Explain in a paragraph or two why our algorithm will find a solution to any Sudoku puzzle with a solution. Also, explain how we could modify the algorithm to find every answer to a given puzzle.
Two simple-minded approaches
The previous activity suggests that we have found a solving algorithm that is very useful in theory. In practice, it turns out that the algorithm is relatively slow: my implementation in Matlab was about as fast as a human on most puzzles, sometimes a lot slower. Indeed, nothing I could impress my dad with. Something else is annoying about this algorithm: it’s virtually impossible to do on paper. There are just too many numbers that need to be entered and erased.
We will now look at some solving methods that work well on paper. Our ultimate goal is to introduce an algorithm that allows a person to solve any Sudoku puzzle on paper or say (with confidence!) that there is no solution.
When you did your first Sudoku puzzle, you probably noticed that you could solve some Sudoku puzzles by taking each number from 1 to 9 in turn and observing that a particular field can only contain a specific number. In other words, you check which numbers may go into a specific cell. If there is only one candidate, then you enter that number. It is natural to go through all cells in the typewriter order, make this check, and enter the corresponding field number. Some puzzles can be solved in this way. However, there might be a point where you get stuck with this method: once you have considered each cell at least once since last entering a number, you can be sure that this method will not solve the puzzle for you. Let’s call this method the candidate-checking way.
There is another method that immediately comes to mind to the beginner Sudoku solver: look at a particular column (or row, or box). You know that each column, row, and the box must contain the number 1 at the end. Check-in how many places you can enter the number 1 without violating the Sudoku condition. If there is only one such cell, then you can enter the 1 in that cell. Now do the same check for number 2. Once you are done with all numbers up to 9, repeat the process with the next column. Once you are done with all columns, do the rows and then the boxes. As with the previous method, some puzzles cannot be solved using only this method: once you have considered each column, row, and box at least once since entering a number, you will not make any more progress using this method alone. Since this method involves finding a place for each number, we will call this the place-finding way.
Having run through the place-finding method once, you can go back to the candidate-checking method: if you have filled some more cells since last trying the first method, there is a chance that it will now allow you to fill some more cells. Once you get stuck again, try the place-finding way again. Switching back and forth between the two place-finding methods and the candidate-checking method will enable you to solve many of the Sudoku puzzles you find in newspapers and magazines. It’s a relatively fast way of solving Sudokus.
Activity 8: Find a Sudoku puzzle in a magazine or online (google “Sudoku free”) that is labeled “hard.” Try using the previous paragraph (and no other methods!) to solve the puzzle. Hint: Remember that if you have looked at all columns, rows, and 3×3 boxes once since last making any progress with either of the two methods, you can be confident that switching between candidate-checking and place-finding will not solve the puzzle.
Solving Algorithms (II)
Crook’s pencil-and-paper algorithm
You probably noticed in the previous activity that there are indeed Sudokus that cannot be solved using method 2 or 3. James Crook, professor emeritus of Computer Science at Winthrop University, came up with an algorithm that will solve any Sudoku puzzle and be done on paper. The following discussion is, in part, adapted from his article “A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles.“
Crook uses a hybrid approach, a sophisticated combination of our simple solving algorithm, the place-finding method, the candidate-checking method, and the method of preemptive sets, which we will learn about in a minute. Remember that the candidate-checking and place-finding methods are friendly and fast but sometimes fail. Our simple solving algorithm can solve everything, but it is not very easy to do for humans because there are many combinations to check. Crook’s method of preemptive sets reduces the number of combinations cleverly.
Definition: The markup of a cell is a list of numbers that the cell may contain, given the numbers that are already in the cells of its row, column, and box.
Markups will help be an essential tool in our algorithm. We will often write the markup in small print in the bottom right corner of a cell.
Let’s think again about the simple solving algorithm worked: for each cell, we entered numbers between 1 and 9 into cells cell by cell. If we found that our choices violated the Sudoku condition, we erased one or more digits, entered new numbers, and tried again. As a result, there were many situations where we tried many numbers, which all lead to violations, before finding the correct one. In an improved version of the simple solving algorithm, one could first mark up the puzzle, and then for each cell does not try numbers 1 to 9 in increasing order, but only the numbers from the markup: this means that there are fewer checks to do, thus less work. Here is another modification:
- First, use the candidate-checking and place-finding methods on the puzzle.
- Mark it up.
- Finally, use the simple solving algorithm to deal with whatever could not be solved using the other methods.
That is, in part, what Crook’s algorithm does.
Definition: A preemptive set is a list of m numbers, 2 ≤ m ≤ 8, each of them between 1 and 9, together with a list of m cells, with the property, no numbers other than the m numbers from the list can occupy the m cells.
To refer to cells, Crook uses a notation where, for example, c(2,1) refers to the cell in row 2 from the top, column 1 from the left. He denotes preemptive sets by first listing the numbers belonging to it, and then the cells that they might occupy: For example, {[4,7], [c(2,1),c(2,9)]} refers to the preemptive set consisting of the numbers 4 and 7 lie in the cells c(2,1) and c(2,9).
Here is an easy-to-prove but extremely useful theorem about preemptive sets:
Theorem (Occupancy theorem): Suppose that x is a number that appears in a preemptive set, which lies entirely in one column (or row, or 3×3 box). Then there can be no x in that column (or row, or 3×3 box) outside of the preemptive set.
Activity 9: Explain in a paragraph why the Occupancy theorem is true.
Suppose that we are solving a Sudoku puzzle and have discovered a preemptive set. Suppose the preemptive group lies entirely within one column (or row, or 3×3 box). In that case, the occupancy theorem allows us to cross out any numbers that appear in the preemptive set from the markups of cells outside of preemptive sets in that column (or row, or 3×3 box). We now have three methods of working towards solutions of Sudoku puzzles that work well on paper: methods 1 and 2 and the method of preemptive sets, which allows us to cross numbers out in the markups of cells.
We can now state Crook’s algorithm for solving Sudoku puzzles on paper:
- Use methods 2 and 3 alternatingly to complete the puzzle as much as possible until those methods lead no further.
- Mark up all empty cells of the unknown.
- Look at each column, row, and 3×3 box and try to break it down into preemptive sets. Try to break preemptive sets with several elements down into smaller preemptive sets. Whenever you have found a preemptive group, cross out numbers in cells’ markups whenever the Occupancy theorem allows it. Try to use methods 2 and 3 again if you could cross out numbers from the markups of any cells. Repeat this process until you can find no more preemptive sets or until the Sudoku rule is violated.
- There are now several possibilities:
- a. If you have solved the Sudoku puzzle, then you are done.
- b. If you violated the Sudoku condition, then the Sudoku does not have any solutions, and you are done.
- c. If neither is the case, then proceed to step 5.
- Choose an empty cell, call it the “current cell,” and enter a number from its markup. Assign the current cell a colored pen that you have not used before. Note the current cell, the number you entered, and the pen’s color on a separate sheet of paper.
- Look at each column, row, and 3×3 box and try to break it down into preemptive sets. Try to break preemptive sets with several elements down into smaller preemptive sets. Whenever you have found a preemptive set, cross out numbers in the markups of cells whenever the occupancy theorem allows it. Try to use methods 2 and 3 again if you could cross out numbers from the markups of any cells. Whenever you enter a number, use the current color, i.e., the pen chosen in step 5. Repeat this process until you can find no more preemptive sets, or until the Sudoku rule is violated or a cell whose markup is empty (contains no numbers).
- There are now several possibilities:
- If you have solved the Sudoku puzzle, then you are done.
- If a cell whose markup is empty, then the choice you made in step 5 does not lead to a solution. Erase everything you have entered using the current color and erase the number you entered in step 5 from the individual cell’s markup. The the markup if this cell is now not empty, go to step 5. Otherwise, repeat the erasing for the previous color (remember that you have a list of cells with their corresponding colors and entries): erase all entries made using the color and erase the number entered in the corresponding cell. Repeat until you end up with a non-empty markup. If this state is not reached, then the puzzle does not have a solution, and you are done. If you do get the state, go to step 5.
- If none of the previous cases applies, go to step 5.
Crook’s algorithm in an example
To illustrate the algorithm, we will solve below (difficult) Sudoku, which Crook discusses in his paper. The puzzle itself is from the book “Solving Sudoku” by Michael Mepham.
After steps 1 and 2 of the algorithm, the Sudoku board looks as follows:
In part 3 of the algorithm, we immediately find the preemptive set {[4,7], [c(2,1),c(2,9)]}. By the occupancy theorem, we may eliminate 4 and from the markups of all cells in the top-right 3×3 box. That exposes the 9 as the only candidate for cell c(2,7), so we enter the 9.
Continuing to look for preemptive sets, we find the preemptive set {[2,4,9],[c(4,4),c(4,6),c(4,7)]}, and after removing the respective numbers from the markups in row 4, we find the preemptive set {[1,3,8],[c(4,1),c(4,2),c(4,8)]}.
Looking over the board one more time, we see no other preemptive sets and that methods 2 and 3 would not allow us to enter any additional numbers into cells either. We thus move on to step 5 of the algorithm.
At this point, it is a good idea to copy the entire Sudoku board with the markup and continue working on a separate sheet of paper. When choosing a cell to enter a number from its markup, it is usually best to select a cell with a markup consisting of as few digits as possible (why, and what is the exception to this rule?). In our case, there are several cells with a markup consisting of 2 numbered. For instance, we could enter a 7 into c(2,1) using a red pen.
In step 6 of the algorithm, we use methods 2 and 3 to enter the numbers 7,4,4,8 and 8 into the cells c(2,1, c(3,2), c(2,9), c(6,2), and c(7,9), respectively. At this point, we get a violation of the Sudoku condition since the middle 3×3 box on the right cannot contain the number 8. As a result, we erase everything we worked out in red, erase 7 from the markup of c(2,1) and proceed to step 5. (In practice, it is probably easier to copy the state of the puzzle before we started using red onto a new sheet of paper.)
In step 5, we observe that the markup of cell c(2,1) now only contains one number, so we choose this cell and enter 4. In step 6, we write 7 into cells c(3,2) and c(2,9). We can now find any additional preemptive sets or make progress with methods 2 or 3, so we go back to step 5.
This time, we choose cell c(9,8) and enter the number 4 from its markup in green color. This time we are lucky: the use of methods 2 and 3, as well as the method of preemptive pairs, will solve the puzzle for us in step 6 of the algorithm. One way of completing the puzzle is as follows:
cell entry
c(7,8) 8
c(8,9) 4
c(8,3) 8
c(6,9) 8
c(4,2) 4
c(2,9) 7
c(2,1) 4
c(3,2) 7
c(7,2) 6
c(7,3) 3
c(7,1) 7
c(8,5) 7
c(9,5) 3
c(6,2) 4
c(5,2) 1
c(5,1) 6
c(4,1) 3 (using the preemptive pair {[1,3],[c(1,9),c(3,9)]})
c(6,8) 3
c(1,5) 4
c(7,9) 5
c(3,8) 4
c(3,7) 5
c(5,8) 9
c(4,8) 1
c(5,7) 4
c(5,3) 2
c(4,7) 2
c(6,4) 2
c(7,6) 4
c(4,6) 9
c(4,4) 4
c(7,5) 2
c(3,5) 9
c(3,4) 1
c(1,6) 3
c(3,6) 2
c(1,9) 1
c(3,9) 3
c(8,6) 1
c(9,4) 9
c(9,1) 1
c(8,1) 9
We have thus found the following solution for the puzzle:
Activity 10: Use the Crooks algorithm to solve the Sudoku puzzle below. It was published by Krazydad and is the first puzzle in a Krazydad’s first book of super-tough puzzles. You will likely spend several hours on this. The puzzle has a unique solution. After some trying, I solved the puzzle by guessing (the correct) numbers for just two cells in step 5 of Crook’s algorithm, but there might be even faster ways of solving the puzzle.
Sudokus as Graphs
While there are mathematical aspects to Sudoku, this game is not one of the main objects studied by research mathematicians and probably never will be. Techniques like the enumeration of possibilities, or the estimates from section 1, are very general and can be used in various settings.
Graphs, which are studied at an introductory level in some high school classes, are yet another way in which theory about Sudokus was developed on an abstract level many years before the puzzles became popular in the western culture.
What is a graph?
Definition: A graph is a collection of points, also called vertices, together with lines connecting (some of) them, also called edges.
Graphs can have one vertex or many and may or may not have edges. Below is an example of a graph (picture by David Eppstein, public domain). While a graph is an abstract object, the vertices and edges often represent something, for example, town and roads connecting them:
Activity 11:
- If this is the first time you encounter graphs, run a picture search for “graph math” on the web to find some further examples of graphs.
- Find out what a “directed graph “is.
- Give an example of a system or situation one could model well with a directed graph.
- Do the same for a “weighted graph.”
How to represent a Sudoku as a graph
Enumerate the 81 cells of the Sudoku board with numbers from 81. The graph associated with a Sudoku puzzle consists of 81 vertices (one for each cell of the board), together with edges as follows: an edge connects two vertices if they correspond to them in the same column, row, or 3×3 box. We have thus represented the Sudoku grid as a graph. It would be a giant graph with 81 vertices and several hundred edges if one wanted to draw it, so let us think about it without attempting to produce a graphical representation. What about the numbers in the cells of the Sudoku puzzle? How do we represent those? Assign each number from 1 to 9 a color. Now color the vertices corresponding to the cell that contains a given number in the color of the number.
It is now easy to see that completing a Sudoku puzzle without violating the Sudoku condition is equivalent to coloring the corresponding graph’s vertices while ensuring that no two adjacent vertices have the same color.
Why is this representation useful?
Graphs have been studied for several hundred years (Wikipedia). Euler worked on the Königsberg Bridge problem in 1735. Check out the Wikipedia article. It’s a fun problem that can be solved without any higher mathematics). Nowadays, graph algorithms are used when a routing tool calculates the optimal route from one city to another or when an electric company wants to figure out if it needs to build more power lines. While those are just two examples, It is clear that in these settings, graph theory has a robust economic relevance. As a result, graph theory has become one of the major fields of modern mathematical research.
Due to the general nature of many theories in mathematics, a lot of knowledge that has been established in graph theory applies to Sudoku puzzles. However, it was not developed with Sudokus in mind. To give an example: In 2007, the mathematicians Herzberg and Murty developed a method to calculate the number of ways in which one can color the vertices of a partially colored graph in such a way that no two adjacent vertices have the same color. This result was not developed with puzzles in mind. Still, it applies immediately to Sudoku puzzles once one has recognized that a Sudoku puzzle can be presented as a graph coloring problem. Once you know that Herzberg and Murty’s method exists, you can use their work without much more thinking to figure out how many solutions a given Sudoku puzzle has.
Activity 12: Some famous problems in graph theory are the Chinese postman problem, the shortest path problem, the traveling salesman problem, and the max-flow min-cut theorem. Find out what each of them is about—state where you see applications of them outside mathematics.
Solutions to Activities
Activity 1: This is almost completely solved in the two paragraphs below the activity.
Activity 2: The 12 comfortable places are: the last cell to be filled in each 3×3 box with a thick margin (unless they happen to be at the end of a row, in which case we already observed that there is at most one possibility), as well as the last cell to be filled in each column (unless they happen to be at the end of a row, or the last cell to be filled in a 3×3 bow, in which case we already observed that there is at most one possibility). As a result, the numbers N1 to N12 are 7,4,7,4,9,8,7,6,5,4,3,2. Their product is (9x8x73x6x5x43x3x2), and our earlier estimate for the number of complete Sudoku puzzles was thus too big by a factor of at least (9x8x73x6x5x43x3x2). Thus a better estimate is (9x8x7x6x5x4x3x2x1)^9 / (9x8x73x6x5x43x3x2) = 3.8×10^41.
Activity 3: The red cell can contain no numbers other than 1 and 3 since all other numbers appear in the same row or box. However, in the “Clever counting” section, we estimated no more than 4 ways of filling the cell in. Therefore, our estimate is too big by at least a factor of 2.
Activity 4: Having completed the puzzle as much as possible, there should now only be 4 empty cells, with the puzzle looking as follows:
It is interesting to note that although only four entries are missing, the puzzle’s solution is still not unique.
Activity 5: If a puzzle has just 3 empty cells, then at least one of them must be alone in its row or column (make sure you understand why). Since the puzzle has a solution by assumption, there is a way of filling this cell in. Moreover, there is only one way of filling it since this cell is the only empty one in its row or column. Fill it in. There are now just two empty cells in the entire puzzle. They are both either the only empty ones in their row or the only empty ones in their column. Now an argument like the one for the first of the three empty cells shows a unique way of filling the two cells in.
Activity 6: You’re on your own since I can’t provide solutions for many programming languages.
Activity 7: The algorithm tries to fill the puzzle cell by cell, trying all possible numbers until all possibilities have been exhausted or until a solution has been found. Therefore, if there is a solution, the algorithm will find it. To make the algorithm find all solutions, don’t stop once you have found the first one! More specifically, once you are in step 4a of the algorithm and are at the last cell in the enumeration, copy down the solution. Then erase the number you entered in the previous cell of the enumeration, then make the second-to-last cell of the enumeration the new current cell, and continue with step 3 of the algorithm.
Activity 8: The activity’s main point is to observe that hard Sudokus can usually not be solved by switching back and forth between candidate-checking and place-finding.
Activity 9: Let’s assume without loss of generality that the preemptive set under discussion lies entirely in row 1. Then the solution will have the number x in one of the cells belonging to the preemptive set. But each number may only occur once per row, so the solution cannot contain the number x in those cells of the first row that do not belong to the preemptive set.
Activity 10: This one is indeed super tough. I will not point out which step of the algorithm I am at, but you should try to keep track of this yourself to make sure that you understand that there is a method to this. First, use the place-finding and candidate-checking methods to fill in as much as you can, then mark up the puzzle. I did not find any preemptive sets, but there were several cells whose markups only contained two numbers. I chose c(6,1), which had a markup of 1 and 9, and entered a 1. That immediately allowed me to cross out the number 1 in the markups of a large number of cells, and the candidate-checking and place-finding methods allowed me to fill in several more cells. Once I could not make any more progress, I chose cell c(3,9), which had a markup of 3 and 7, and entered a 3. The place-finding and candidate-checking methods, as well as the method of preemptive sets, then lead to the following solution:
Activity 11: The first part of the activity is easy and will not be solved here. Arrows usually indicate a directed graph whose edges have a direction associated with them on the edges. For example, one could think of the cardiovascular system, which is composed of arteries and veins through which blood flows and points where two blood vessels meet. The arteries and veins correspond to edges, and the meeting points of blood vessels correspond to vertices. Since blood flows in only one direction through an artery or vein, we can associate a direction with each edge.
A weighted graph is a graph where each edge has a number (‘weight’) associated with it. For example, if you represent a network of roads as a graph, the weights could stand for roads’ lengths.
Activity 12: The Chinese postman problem is about finding the shortest path through a graph that goes through every edge at least once and ends up at the starting point. A mail carrier might be interested in answering such a question since he wants his path to be as short as possible, needs to visit every street at least once, and needs to finish his route where it began.
The shortest path problem is about finding the shortest route between two points on a graph. Routing applications need to solve problems like this all the time when they see the fastest way from one town to the other.
The traveling salesman problem is about finding the shortest path through a graph that visits every vertex at least once and starts and ends at the same point. Imagine a salesman who needs to see all of his clients and drive as short a distance as possible.
The max-flow min-cut theorem is about flows on a weighted graph: imagine you have a network of pipes, and each of them has a specific maximal capacity. You want to pump a fluid through the network from one point to a different point. The max-flow min-cut theorem helps you work out how the fluids should flow through the network to get the greatest possible throughput.
