Quantcast
ZME Science
  • News
  • Environment
  • Health
  • Future
  • Space
  • Features
    Menu
    Natural Sciences
    Health
    History & Humanities
    Space & Astronomy
    Technology
    Culture
    Resources
    Natural Sciences

    Physics

    • Matter and Energy
    • Quantum Mechanics
    • Thermodynamics

    Chemistry

    • Periodic Table
    • Applied Chemistry
    • Materials
    • Physical Chemistry

    Biology

    • Anatomy
    • Biochemistry
    • Ecology
    • Genetics
    • Microbiology
    • Plants and Fungi

    Geology and Paleontology

    • Planet Earth
    • Earth Dynamics
    • Rocks and Minerals
    • Volcanoes
    • Dinosaurs
    • Fossils

    Animals

    • Mammals
    • Birds
    • Fish
    • Reptiles
    • Amphibians
    • Invertebrates
    • Pets
    • Conservation
    • Animals Facts

    Climate and Weather

    • Climate Change
    • Weather and Atmosphere

    Geography

    Mathematics

    Health
    • Drugs
    • Diseases and Conditions
    • Human Body
    • Mind and Brain
    • Food and Nutrition
    • Wellness
    History & Humanities
    • Anthropology
    • Archaeology
    • Economics
    • History
    • People
    • Sociology
    Space & Astronomy
    • The Solar System
    • The Sun
    • The Moon
    • Planets
    • Asteroids, Meteors and Comets
    • Astronomy
    • Astrophysics
    • Cosmology
    • Exoplanets and Alien Life
    • Spaceflight and Exploration
    Technology
    • Computer Science & IT
    • Engineering
    • Inventions
    • Sustainability
    • Renewable Energy
    • Green Living
    Culture
    • Culture and Society
    • Bizarre Stories
    • Lifestyle
    • Art and Music
    • Gaming
    • Books
    • Movies and Shows
    Resources
    • How To
    • Science Careers
    • Metascience
    • Fringe Science
    • Science Experiments
    • School and Study
    • Natural Sciences
    • Health
    • History and Humanities
    • Space & Astronomy
    • Culture
    • Technology
    • Resources
  • Reviews
  • More
    • Agriculture
    • Anthropology
    • Biology
    • Chemistry
    • Electronics
    • Geology
    • History
    • Mathematics
    • Nanotechnology
    • Economics
    • Paleontology
    • Physics
    • Psychology
    • Robotics
  • About Us
    • About
    • The Team
    • Advertise
    • Contribute
    • Privacy Policy
    • Contact
No Result
View All Result
ZME Science

No Result
View All Result
ZME Science

Home → Research → Studies

Mathematician solves sudoku dilema: 17 minimum clues for a solution

Tibi Puiu by Tibi Puiu
January 9, 2012
in Science, Studies

One of my favorite past times is filling sudoku puzzles. There’s something about this seemingly simple, yet challenging, dance of digits up and down, left and right that manages to keep me highly entertain though a perfectly balanced mixture of thrill and frustration. If you think you’re good enough to solve any kind of sudoku, be aware that some combinations are impossible to solve.

Sudoku Gary McGuire, a mathematician of University College Dublin, has pain-stakingly devised an algorithm through which he has scientifically proven that a sudoku puzzle can’t have less than 17 clues, since puzzles with 16 or fewer clues do not have a unique solution. Your typical newspaper sudoku has around 25 clues, on the safe side – just enough not to get bored, while keeping frustration amounted from failing to see the solution at bay.

Gasp! It suddenly hit me that some ZME readers might not know what a sudoku is in the first place. Well, I must make haste before I continue to explain how the game works. Very simple: sudoku involves filling in a 9×9 grid of squares, according to a set of rules (each 3×3 box needs to be filled with each number from 1-9, the same goes for the every column and line of the 9×9 grid). To kick things off and be able to find a solution, the puzzle has some boxes filled out in a particular order – these are your clues, the fewer you have, the harder the game gets.

Back to science. Professor McGuire presented his work at the recent conference in Boston, where his findings where heralded valid and deemed as an important advance in the growing field of Sudoku mathematics, which is more important than one might think. I’ll get to that soon enough.

There have been literary thousands of 16 clues sudoku trials, however it was found that in every instance, there could be found only one solution – but how to demonstrate this? Gary McGuire developed a “hitting set algorithm” to definitively prove the theory. This algorithm looks for what McGuire calls “unavoidable sets”, couples of filled in values in the completed values which when interchanged can result in multiple solutions. By replacing these unavoidable sets values and positions with clue values the computing task at hand becomes a lot less complex, though still very though.

“The approach is reasonable and it’s plausible. I’d say the attitude is one of cautious optimism,” says Jason Rosenhouse, a mathematician at James Madison University in Harrisonburg, Va., and the co-author of a newly released book on the mathematics of Sudoku.

To run this algorithm for solutions, brute force is the only option. Even with the unavoidable sets algorithm in place,  which took two years to tweak, McGuire and his team used about 700 million CPU hours at the Irish Centre for High-End Computing in Dublin, searching through possible grids with the hitting-set algorithm. The work, says McGuire, has implications beyond Sudoku itself.

“Hitting set problems have applications in many areas of science, such as bioinformatics and software testing,” he says.

McGuire’s paper was published in a recent edition of the journal Nature.

via

Was this helpful?


Thanks for your feedback!

Related posts:
  1. Amateur mathematician Aubrey de Grey, known for his work on anti-aging, solves decades-old problem
  2. Renowned mathematician claims “simple” solution to 160-year-old problem
  3. New AI solves most Captcha codes, potentially causing a “huge security vulnerability”
  4. AI solves, explains, and proposes new university-level math problems
  5. The minimum and maximum possible temperatures
Tags: MathematicsSudoku

ADVERTISEMENT
  • News
  • Environment
  • Health
  • Future
  • Space
  • Features
  • Reviews
  • More
  • About Us

© 2007-2021 ZME Science - Not exactly rocket science. All Rights Reserved.

No Result
View All Result
  • News
  • Environment
  • Health
  • Future
  • Space
  • Features
    • Natural Sciences
    • Health
    • History and Humanities
    • Space & Astronomy
    • Culture
    • Technology
    • Resources
  • Reviews
  • More
    • Agriculture
    • Anthropology
    • Biology
    • Chemistry
    • Electronics
    • Geology
    • History
    • Mathematics
    • Nanotechnology
    • Economics
    • Paleontology
    • Physics
    • Psychology
    • Robotics
  • About Us
    • About
    • The Team
    • Advertise
    • Contribute
    • Privacy Policy
    • Contact

© 2007-2021 ZME Science - Not exactly rocket science. All Rights Reserved.

Don’t you want to get smarter every day?

YES, sign me up!

Over 35,000 subscribers can’t be wrong. Don’t worry, we never spam. By signing up you agree to our privacy policy.

✕
ZME Science News

FREE
VIEW