Sudoku and Graph Theory
By Julie J. Rehmeyer
When you get stuck on a fiendishly difficult sudoku, it's hard not to wonder if the puzzle really has a solution. At another moment, aglow in the triumph of a clever deduction, you might have a sneaking suspicion that there may be a simpler, more systematic way of finding the answer. Further questions may come to mind: How many different sudoku puzzles are possible in the standard 9-by-9 format? Can a puzzle with few initial entries be easier to solve than one with more entries? What's the smallest number of initial entries necessary to guarantee that there's one, and only one, solution?
Although the puzzles are often billed as requiring no math to solve, some of the questions they raise call for mathematical analysis. Researchers are now taking up the task. An article in the June Notices of the American Mathematical Society lays a mathematical framework for addressing some basic questions about sudokus.
Each 9-by-9 sudoku grid is composed of nine 3-by-3 subgrids. Initially, some of these 81 squares contain a number, from 1 through 9, but others do not. The object is to fill in the empty squares so that each row, column, and subgrid contains all of the numbers 1 through 9, in any order. Each puzzle has only one solution.
 |
This sudoku puzzle has 17 initial entries, the smallest number known to be possible on a 9-by-9 grid. So far, no one has figured out whether or not a solvable puzzle exists with only 16 initial entries. |
Agnes M. Herzberg and M. Ram Murty of Queen's University in Kingston, Ontario have translated the problem of solving a sudoku puzzle into the language of graph theory. The 81 squares in the grid correspond to vertices in a mathematical graph. A line connects vertices that appear in the same row, column, or subgrid. This translation allowed the mathematicians to use mathematical tools developed in graph theory to understand sudoku.
Although sudoku puzzles almost always use the digits 1 through 9, any nine symbols will suffice. For example, a puzzle could have nine letters, shapes, or colors instead of numbers. When graph theorists label the vertices, they call it a "coloring." A sudoku puzzle begins with a partial coloring, since only a few spots have numbers. Once each vertex is colored and no two connected vertices have the same color, the coloring is called "proper."
Thus, in the language of graph theory, solving a sudoku means extending a partial coloring of the graph into a proper coloring.
Herzberg and Murty used techniques from graph theory to show that a mathematically simple formula exists for the number of possible solutions to a given sudoku puzzle. If the puzzle is designed correctly, it has only one possible solution. Such a formula might help a stumped puzzle-solver make sure that a certain sudoku really does have a solution, and that it has only one solution.
Unfortunately, there's a glitch: although the mathematicians proved that the formula exists, they weren't able to figure out what it is.
 |
Murty found this poorly-designed sudoku puzzle in Air Canada's in-flight magazine. Despite having 29 initial entries, it has two possible solutions. |
Herzberg and Murty have established, however, that for a puzzle to have precisely one solution, the initial entries need to include at least eight of the nine digits. Their reasoning is simple. Suppose that neither 1 nor 2 appears in the initial entries. Then in any solution, all the 1's could be switched with all the 2's, so there would be at least two valid solutions.
Sudoku puzzles are an example of a type of graph known as a Latin square, which mathematicians have studied for centuries. A Latin square is simply a grid of numbers from 1 to n arranged so that each row and each column contain precisely one instance of each number. If a Latin square contains subgrids that also contain the n numbers once each, then it's a sudoku.
How many Latin squares also happen to be sudoku puzzles? Counting up the total possible number of 9-by-9 Latin squares turns out to be quite difficult, and determining the total possible number of sudokus is even harder. In 1975, researchers determined that there are 5,524,751,496,156,892,842,531,225,600 (about 5.5 x 1027) Latin squares with a 9-by-9 configuration. And two years ago, Bertram Felgenhauer of Dresden Technical University in Germany and Frazer Jarvis of the University of Sheffield in England figured out that there are 3,546,146,300,288 (about 3.5 x 1012) meaningfully different 9-by-9 sudoku puzzles. That's a huge number, but not nearly as huge as the number of Latin squares.
But Herzberg and Murty posed a broader question. The standard 9-by-9 sudoku has nine 3-by-3 subgrids, but a sudoku can be smaller or larger. For example, a 4-by-4 sudoku has four 2-by-2 subgrids. A 16-by-16 sudoku has sixteen 4-by-4 subgrids, and generally, an n2-by-n2 sudoku would have n-squared n-by-n subgrids. How many Latin squares of these other possible sizes are also sudokus?
That question seems impossible to answer, given that no one knows how many Latin squares exist for any size larger than 11-by-11. Furthermore, no one knows how many sudoku puzzles exist for any grid size exceeding 9-by-9. Nevertheless, Herzberg and Murty managed to compute that for a randomly chosen Latin square with dimension n2-by-n2, the bigger n is, the smaller the probability that it is also a sudoku. In fact, the probability approaches zero as n gets larger.
Why expend all this mathematical energy on a little puzzle? "It's fun," Murty says.
But he also points to a couple of serious reasons. Remarkably enough, sudoku could have practical applications when viewed as a graph theory problem. For example, scheduling committee meetings for various groups in different time slots can pose a similar mathematical challenge. Each vertex represents a different committee, and two committees are joined by a line if they have a member in common. If some of the committees have already been assigned time slots, scheduling the remaining committee meetings involves extending a partial coloring to a proper coloring, so that all meetings are allotted times that don't conflict with any other meetings. Murty also points to applications in designing test fields for agricultural studies and in avoiding interference when assigning frequency channels to television stations.
Murty says that he is fascinated by sudoku puzzles because they pose a simple problem that connects with sophisticated mathematics. For example, the same tools he is using to understand sudoku are also applicable to the "four color problem." This is the classical conjecture that for any given map, only four different colors are needed to color each country (or state) so that any two countries that share a border are not the same color. It took more than a century to solve that problem.
"These questions that look innocent can have deep mathematics in them," he says. "Sudoku is one of those."
References:
Felgenhauer, B., and J. Frazer. 2005. Enumerating possible Sudoku grids. Preprint available at http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf.
Herzberg, A.M., and M.R. Murty. 2007. Sudoku squares and chromatic polynomials. Notices of the American Mathematical Society 54(June):708-717. Available at http://www.ams.org/notices/200706/tx070600708p.pdf.
Peterson, I. 2007. Sudoku class. Science News Online (Feb. 3). Available at http://www.sciencenews.org/articles/20070203/mathtrek.asp.
Peterson, I. 2006. Pentomino sudoku. Science News Online (May 13). Available at http://www.sciencenews.org/articles/20060513/mathtrek.asp.
Peterson, I. 2005. Sudoku math. Science News Online (June 18). Available at http://www.sciencenews.org/articles/20050618/mathtrek.asp.
Comments
Hi,
This is an invitation to join Sudoku World, which is a Yahoo based international meeting place for Sudoku addicts.
Sudoku World was created on June, 25, 2005, and now we are 4,985 members from 70 countries.
The age of our Sudoku World members vary from 10 to 88!!! More than 47% of the Sudoku World members are female.
Sudoku World offers:
- useful information on the game and strategy,
- an active message board with 3.644 messages.
-172 Sudoku related article links,
- 1 Sudoku World Championship puzzle link with 13 puzzles from the qualification rounds,
- 2 Sudoku Glossary, Terms and FAQ links,
- 19 links to other Japanese puzzles,
- 23 links to Sudoku forums, communities and discussion groups,
- 7 PC Sudoku links,
- 7 Sudoku Haiku links,
- 2 Sudoku humour links,
- 23 Sudoku merchandise links,
-141 Sudoku puzzle links (including 21 Japanese links),
- 2 links to Anagram Sudokus,
- 37 links to on.line Sudoku and Samurai Sudoku solvers,
- 30 links to Sudoku tutorials, solving strategies, techniques and rules links,
-154 links to Black or White Knight Sudoku puzzles and other Chess related Sudokus.
-787 printable Sudoku puzzle files including:
- 40 difficult puzzles including the final puzzle in the 2006 Sudoku World Championship,
- 3 Sudoku odd/even logo puzzles
- 22 Sudoku puzzles with only 17 given numbers,
- 2 Sudoku puzzles with 18 given numbers,
- 2 Sudoku puzzles with 19 given numbers,
-225 Japanese inspirated puzzles (many Sudoku X puzzles),
-114 assorted Sudokus (including Tanto Sudokus) - all with solutions,
- 48 mini overlapping 6x6 Sudokus - all with solutions,
- 46 Japanese Samurai Sudokus,
- 20 interesting variants with a pleasing set-up,
- 17 heart Sudokus,
- a printable heart Sudoku booklet with 79 puzzles,
- 3 Christmas tree Sudokus,
- 2 tadpole Sudokus,
- 27 Logidokus + hints document,
- 16 All Sevens, Eights or Nines puzzles,
- 5 irregular Odd/Even puzzle,
- 25 Sudoku X puzzles,
- 15 The Ones, the Twos, the Threes and the Last sets (4 Sudokus in each set),
- 1 Name Sudoku,
- 2 Wordokus,
- 2 Wordoku Xs,
- 3 Sudokus with all the solution steps,
- 1 100x100 Sudoku,
- 2 puzzles with 13 overlapping Sudokus - with solutions,
- 1 puzzle with 17 overlapping Sudokus,
- 1 puzzle with 39 overlapping Sudokus,
- 1 puzzle with 20 overlapping Sudoku Xs
- 7 Sudoku Haiku entries from our competition
- 10 Puzzles for the visually impaired.
An ended Sudoku Haiku competition with book prizes.
Instructions booklet from the 2006 Sudoku World Championship at Lucca, Italy.
Instructions booklet from the 2007 Sudoku World Championship at Prague, the Czech Republic.
Practice puzzle book from 2007 Sudoku World Championship at Prague, the Czech Republic.
- more than 20 help grids (empty Sudoku grids, Samurai Sudoku grids and smaller Sudoku collections),
- Sudoku derivations file.
- a few databases.
- 1 closed and 24 ongoing Sudoku related polls (with 5,467 placed votes).
- 866 photos in 49 albums including:
- recommended Sudoku literature section,
- Sudoku cartoons,
- Many new Japanese Sudoku puzzle variations including:
- various overlapping and Samurai Sudokus,
- Samurai puzzles,
- oversized Sudokus,
- several interesting hybrid Sudokus!!
- unsecutive numbers,
- sum Sudokus,
- product Sudoku,
- more or less Sudokus,
- neighbour Sudoku,
- 6 and 9 number arrow Sudokus,
- odd/even Sudokus,
- irregular odd/even Sudokus,
- 6, 7, 9, 10 and 12 number irregular groups Sudokus,
- 9 number open irregular groups Sudokus,
- overlapping irregular Sudokus,
- 2 irregular Samurai Sudokus,
- 1234 Sudoku,
- 12345 Sudoku,
- 1234 irregular groups Sudokus,
- extra groups Sudokus,
- disallowed Sudoku,
- 8, 9 and 12 number cube Sudokus,
- dots Sudoku,
- hexagon Sudokus in different sizes,
- total sum Sudoku,
- sum, difference, more or less Sudoku,
- more or less or equal Sudoku,
- 7, 9 and 12 number demarcated Sudokus,
- different Sudoku + variants,
- sequential Sudokus,
- colour Sudokus,
- Sudoku + variants
- Tri Sudoku,
- wordokus,
- various relay Sudokus,
- normal Sudokus where you have to solve a jigzaw puzzle first,
- 6, 8 and 10 number brick Sudokus,
- 6 and 7 number chain Sudokus,
- Dominoes Sudoku,
- 6 and 9 number Digital Sudokus,
- skyscraper Sudoku,
- 154 Chess Sudokus,
- Sudoku nets,
- star Sudokus,
- 6 and 9 number arrow sudokus,
- Killer Sudokus,
- Double Killer Sudokus,
- Logidoku Killer Sudokus,
- Letter Sudoku,
- dice Sudoku,
- different chess Sudoku variants,
- digital display Sudoku,
- different small Sudokus for children and/or beginners and
- sudoku X in various sizes and variants,
- 2x2, 4x4 and 6x6 Sudokus and
- normal 9x9 Sudokus.
You will find Sudoku World here:
http://games.groups.yahoo.com/group/Sudokuworld
You don't have to be a black belt Sudoku solver to become a member of Sudoku World, because all ages, and all standards, beginners to advanced Sudoku puzzlers, are welcome.
We even have a Kakuro section with 21 links to quality Kakuro sites. Last but not least we have 21 links to various Japanese puzzles including:
- Akari,
- Arukone,
- Edel,
- Fillomino,
- Hanjie,
- Hashiwokakero,
- Hexafex,
- Heyawake,
- Hitori,
- Kamaji,
- Masyu,
- Nurikabe,
- Ripple Effect,
- Slither Link and
- Yajilin.
We all hope to meet you there!
Kind regards,
Frank Vedel - MY days are numbered - are yours?
Posted by: Frank Vedel | July 6, 2007 03:46 PM
3.5 x 10^12 times 81 4 bit integers, say 40 bytes.
Would make a good test for a database indexing system with a total size 1.4 x 10^14 bytes. Should be able to find any solution by trying each of the four rotations of the puzzle as search keys on the total database. And:
Will find any non unique solutions.
Determine if solutions in different rotations are complementary.
Posted by: Fredrik Swartz | July 6, 2007 03:48 PM
Grammar error: plural of sudoku is still sudoku.
Dictionary.com lists sudoku and doesn't have any special notes about its plural form. If anyone has definitive indication that the plural form of sudoku is indeed sudoku rather than sudokus, I'd be very interested.--jjr
Posted by: Alpha Omicron | July 6, 2007 08:58 PM
If you want to try out something new in sudoku, try shendoku, using the sudoku rules but playing two people, one against the other, like battleshipps. They have a free version to download at http://www.shendoku.com/sample.pdf . Anything else they are bringing out or they are working on you can find at www.shendoku.com or at they´r blog www.shendoku.blogspot.com . Have fun, I am.
Posted by: armando | July 9, 2007 07:29 PM
It's a Japanese word, isn't it?
Yep. Means "unmarried numbers." --jjr
Posted by: Anton Sherwood | August 15, 2007 07:50 PM