# Mathematicians use computer to solve minimum Sudoku solution problem

##### January 6, 2012 by Bob Yirka weblog

(PhysOrg.com) -- Over the past several years, Sudoku, as most people know, has become wildly popular. Where once mainstream newspapers carried only crossword puzzles, they now also carry a Sudoku puzzle as well. But along with that popularity, has come increased scrutiny and competition between people to see if certain properties of the puzzle can be found. For example, in any given Sudoku puzzle, how many clues must be given in order to have just one unique solution to the problem? Most Sudoku enthusiasts will answer 17, because nobody has ever been able to find one with 16 or less; which is fine, except that people as a general rule like some sort of proof of such things. Thus, it should not come as much of a surprise to anyone that a team of mathematicians have not only set out to prove what everyone thinks they know, but have succeeded in their endeavor.

Sudoku, for the uninitiated, is a whereby a square is created with 9x9 rows and columns of boxes to be filled in with numbers (1 through 9). The puzzle is further divided into nine 3x3 sections. The trick to solving the puzzle is that each row and column cannot have repeating numbers and neither can any of the 3x3 sections. Also, when a puzzle is created, a certain number of the boxes are prefilled, creating in essence, a unique puzzle each time. Thus, to solve the puzzle, all a person has to do is figure out how to fill in the rest of the boxes.

The thing about Sudoku puzzles though, is that those that make them can pre-fill as many boxes as they choose, the more clues they give, generally, the easier the puzzle will be to solve. Thus, creators who want to make their puzzles as hard as possible want to fill in the fewest possible clues that will still allow for a unique single solution.

To prove that 17 is the magic number, Gary McGuire and colleagues at University College, Dublin, took the brute force approach. After all with every there is a solution, to find it, all a computer would have to do is try every possible scenario for every possible configuration. Unfortunately, that approach would take too long, so the team had to figure out a way to trim down the number of possibilities they’d have to check for.

Throwing out grids that are equivalent helps, that reduces the number of tests dramatically. But that’s still not enough, so the team wrote a software routine that tests to see if certain subsets of the puzzle are equivalent to others, which would mean not having to test for the others if the first are found. This reduced the amount of testing as well. But even so, it took almost all of a full year of computing to test all of the possible scenarios.

But when the program stopped, the researchers had their answer. To create a Sudoku puzzle that is unique, you have to give at least 17 clues.

Explore further: Discovery could lead to more difficult Sudoku puzzles

More information: There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem, arXiv:1201.0749v1 [cs.DS] arxiv.org/abs/1201.0749

Abstract
We apply our new hitting set enumeration algorithm to solve the sudoku minimum number of clues problem, which is the following question: What is the smallest number of clues (givens) that a sudoku puzzle may have? It was conjectured that the answer is 17. We have performed an exhaustive search for a 16-clue sudoku puzzle, and we did not find one, thereby proving that the answer is indeed 17. This article describes our method and the actual search.
The hitting set problem is computationally hard; it is one of Karp's twenty-one classic NP-complete problems. We have designed a new algorithm that allows us to efficiently enumerate hitting sets of a suitable size. Hitting set problems have applications in many areas of science, such as bioinformatics and software testing.

via ArxivBlog

## Related Stories

#### Discovery could lead to more difficult Sudoku puzzles

February 13, 2010

(PhysOrg.com) -- A new analysis of number randomness in Sudoku matrices could lead to the development of more difficult and multi-dimensional Sudoku puzzles. In a recent study, mathematicians have found that the way that ...

#### Toy Robot to Solve Sudoku (w/ Video)

September 3, 2009

(PhysOrg.com) -- A Swedish programmer, Hans Andersson, has used a Lego Mindstorms NXT kit to develop a robot to solve Sudoku puzzles.

#### Computer defeats humans at crossword

September 1, 2006

Crossword-solving computer program WebCrow has defeated 25 human competitors in a puzzle competition in Riva del Garda, Italy.

#### DARPA Shredder Challenge sizzling but no winner yet

November 22, 2011

(PhysOrg.com) -- With only days left until the December 4 Shredder Challenge deadline, DARPA is still asking the sharpest-minded computer scientists and simply the curious if anyone among them has the skills to reconstruct ...

#### Physicist's algorithm simplifies biological imaging -- and also solves Sudoku puzzles

March 2, 2006

Cornell physicist Veit Elser has been engrossed recently in resolving a pivotal question in biological imaging. So he hasn't had much time for brainteasers and number games.

#### Computer software sets new record for solving jigsaw puzzle

May 24, 2010

(PhysOrg.com) -- Completing jigsaw puzzles is a challenging and popular hobby, but now scientists from the Massachusetts Institute of Technology (MIT) in the U.S. and Tel Aviv University in Israel have for the first time ...

## Recommended for you

#### AT&T buying HBO and CNN owner Time Warner for \$85.4 billion

October 22, 2016

Grab some popcorn—AT&T wants to take you to the movies.

#### Ongoing cyber attack hits Twitter, Amazon, other top websites (Update)

October 21, 2016

Major internet services including Twitter, Spotify and Amazon suffered service interruptions and outages on Friday as a US internet provider came under sustained cyber attack.

#### 3-D printing and origami techniques combined in development of self-folding medical implants

October 21, 2016

Researchers at TU Delft have made flat surfaces that are 3-D printed and then 'taught' how to self- fold later. The materials are potentially very well suited for all kinds of medical implants. They report on their findings ...

#### From ancient fossils to future cars: Energy-efficient batteries from silicon in diatomaceous earth

October 21, 2016

Researchers at the University of California, Riverside's Bourns College of Engineering have developed an inexpensive, energy-efficient way to create silicon-based anodes for lithium-ion batteries from the fossilized remains ...

#### Scientists explore use of 3-D printing to speed up target production for testing material strength

October 21, 2016

Advanced 3-D printing promises to redefine manufacturing in critical industries such as aerospace, transportation and defense, and now, Lawrence Livermore National Laboratory is exploring the use of 3-D printing to achieve ...

#### Algorithm could help analyze fetal scans to determine whether interventions are warranted

October 21, 2016

Researchers from MIT, Boston Children's Hospital, and Massachusetts General Hospital have joined forces in an ambitious new project to use magnetic resonance imaging (MRI) to evaluate the health of fetuses.

##### mhenriday
not rated yet Jan 08, 2012
Despite proofs of this type, related ultimately to the ancient Greek proof that the square root of 2 is not a rational number, someone of your acquaintance within the next day or so is sure to mouth that demonstrably false cliché to the effect that «you can't prove a negative»....

Henri
##### mhenriday
not rated yet Jan 08, 2012
Despite this proof and others like it - ultimately related to the ancient Greek proof that the square root of 2 is not a rational number, within the next couple of days someone of your acquaintance is likely to mouth that demonstrably false cliché to the effect that «you can't prove a negative»....

Henri
##### mhenriday
not rated yet Jan 08, 2012
Despite this proof and others like it - ultimately related to the ancient Greek proof that the square root of 2 is not a rational number, within the next couple of days someone of your acquaintance is likely to mouth that demonstrably false cliché to the effect that «you can't prove a negative»....

Henri
##### antialias_physorg
not rated yet Jan 08, 2012
ultimately related to the ancient Greek proof that the square root of 2

this has nothing to do with it.

The adage that you can't prove a negative is only relevant if the entirety of your searchspace cannot be tested. With the brute force approach used here they did test it.

That said I would have guessed that information theory might have sufficed to show that the amount contained in 16 clues is not enough to contain all the information inherent in a completed sudoku puzzle.