Featured Research

from universities, journals, and other organizations

Solving Sudokus: Coloring By Numbers

Date:
June 8, 2007
Source:
American Mathematical Society
Summary:
In a recent article, mathematicians explain the use of tools from the branch of mathematics called graph theory to systematically analyze Sudoku puzzles. They also find that analyzing Sudokus leads to some unsolved problems in graph theory.

Have you ever been trying to solve a Sudoku puzzle and been gripped by a sinking feeling that maybe you were stuck with a lemon? That maybe the puzzle you are struggling with actually has no solution at all? And, if you do find a solution, how can you be sure it's the only one? What if half an hour ago you had written 5 instead of 3---would you then have gone down a path to a completely different solution?

These questions and others are explored in the article "Sudoku Squares and Chromatic Polynomials", by Agnes M. Herzberg and M. Ram Murty, which appears in the June/July 2007 issue of the Notices of the AMS. The authors use tools from the branch of mathematics called graph theory to systematically analyze Sudoku puzzles. They also find that analyzing Sudokus leads to some unsolved problems in graph theory.

In this context, a "graph" is a collection of nodes connected by line segments (this object is also sometimes called a "network"). We can think of the 81 squares in a Sudoku puzzle as 81 nodes in a graph. We will also represent each of the numbers one through nine by a different color. In a Sudoku graph, two nodes are connected by a line segment if the two squares they represent are in the same row, column, or 3 by 3 subgrid. Since no row, column, or 3 by 3 subgrid can contain more than one instance of each number, the graph will have no connected nodes of the same color. (For example, suppose we represent 1 with red. Two red nodes connected with a line segment would mean a row, column, or 3 by 3 subgrid had two 1's in it, which is forbidden in Sudoku.)

In the language of graph theory, a colored graph with no connections between same-colored nodes is a called a "proper coloring." What Sudoku solvers do every day is try to extend a partially-colored graph (the original puzzle with open squares means the graph representing it has yet-to-be-colored nodes) to a proper coloring.

With this analogy between Sudoku puzzles and graphs in place, Herzberg and Murty are able to use tools from graph theory to prove theorems about Sudokus. For example, they prove that the number of ways of extending a partial coloring of a graph is given by a polynomial. If the value of this polynomial is zero for a given Sudoku puzzle, then the puzzle has no solution; if the value is 1, then the puzzle has only one solution; and so forth. They also prove that, in order for any Sudoku puzzle to have only one solution, at least 8 of the 9 numbers must appear as given entries in the puzzle; if only 7 numbers are given, then the puzzle has at least two solutions. And this brings up an unsolved mathematical question: "It would be extremely interesting to determine under what conditions a partial coloring can be extended to a unique [proper] coloring," Herzberg and Murty write.

Some Sudokus are harder than others, with the really difficult ones containing very few given entries. What is the minimum number of given entries needed to ensure that a puzzle has a unique solution" Herzberg and Murty give an example of a Sudoku puzzle with just 17 given entries that has only one solution. So the minimum number is at least 17. But could it be 16---or something even smaller" No one knows. One might think that a puzzle with many given entries is likelier to have a unique solution, but this is not necessarily the case. The article gives an example of a puzzle with 29 given entries that actually has two different solutions.

And if you have been wondering when your newspaper will run out of Sudoku puzzles, the authors argue that the number of distinct Sudoku puzzles is somewhere around 5.5 billion---enough to keep Sudoku afficianados busy for a long time to come.

The article "Sudoku Squares and Chromatic Polynomials" is available on the web site of the AMS Notices at the URL http://www.ams.org/notices/200706/tx070600708p.pdf.


Story Source:

The above story is based on materials provided by American Mathematical Society. Note: Materials may be edited for content and length.


Cite This Page:

American Mathematical Society. "Solving Sudokus: Coloring By Numbers." ScienceDaily. ScienceDaily, 8 June 2007. <www.sciencedaily.com/releases/2007/06/070608093815.htm>.
American Mathematical Society. (2007, June 8). Solving Sudokus: Coloring By Numbers. ScienceDaily. Retrieved April 17, 2014 from www.sciencedaily.com/releases/2007/06/070608093815.htm
American Mathematical Society. "Solving Sudokus: Coloring By Numbers." ScienceDaily. www.sciencedaily.com/releases/2007/06/070608093815.htm (accessed April 17, 2014).

Share This



More Computers & Math News

Thursday, April 17, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

German Researchers Crack Samsung's Fingerprint Scanner

German Researchers Crack Samsung's Fingerprint Scanner

Newsy (Apr. 16, 2014) German researchers have used a fake fingerprint made from glue to bypass the fingerprint security system on Samsung's new Galaxy S5 smartphone. Video provided by Newsy
Powered by NewsLook.com
Twitter, Apple Social Data Purchases Likely to Spur More Mergers and Acquisitions

Twitter, Apple Social Data Purchases Likely to Spur More Mergers and Acquisitions

TheStreet (Apr. 16, 2014) The social media data space is likely to see more mergers and acquisitions following Twitter Inc.'s acquisition of tweet analyzer Gnip Inc. on Tuesday and Apples Inc.'s purchase of Topsy Labs Inc. back in December. One firm in particular, the U.K.'s DataSift Inc., could be on the list of potential buyers. Among other social media startups that could be ripe for picking is Banjo, whose mobile app provides aggregated content by topic and location. Banjo could also be a good fit for Twitter. Video provided by TheStreet
Powered by NewsLook.com
Bitcoin Exchange Mt. Gox to Liquidate After Rebuilding Rejected

Bitcoin Exchange Mt. Gox to Liquidate After Rebuilding Rejected

TheStreet (Apr. 16, 2014) Bitcoin exchange Mt. Gox has agreed to liquidate after a Japanese court rejected its plans to rebuild, according to a report by the Wall Street Journal. Mt. Gox filed for bankruptcy protection in February after announcing about 850,000 bitcoins, worth around $454 million at today's rates, may have been stolen by hackers. It has since recovered 200,000 of the missing bitcoins. The court put Mt. Gox's assets under a provisional administrator's control until bankruptcy proceedings begin. Video provided by TheStreet
Powered by NewsLook.com
BlackBerry: The Crash That Launched 1,000 Startups

BlackBerry: The Crash That Launched 1,000 Startups

Reuters - Business Video Online (Apr. 16, 2014) Tech startups in BlackBerry's hometown of Waterloo, Ontario, are tapping talent from the struggling smartphone company and filling the void left in the region by its meltdown. Reuters correspondent Euan Rocha visits the region that could become Canada's Silicon Valley. Video provided by Reuters
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins