Skip to Content
Uncategorized

Best of 2012: Mathematicians Solve Minimum Sudoku Problem

In January, a year-long calculation proved there are no 16-clue puzzles in Sodoku, confirming the long held belief that the smallest number of starting clues a puzzle can contain is 17

“Sudoku is a number puzzle consisting of a 9 x 9 grid in which some cells contain clues in the form of digits from 1 to 9. The solver’s jobs is to fill in the remaining cells so that each row, column and 3×3 box in the grid contains all nine digits.

There’s another unwritten rule: the puzzle must have only one solution. So grids cannot contain just a few starting clues.

It’s easy to see why. A grid with 7 clues cannot have a unique answer because the two missing digits can always be interchanged in any solution. A similar argument explains why grids with fewer clues must also have multiple solutions.

But it’s not so easy to see why a grid with 8 clues cannot have a unique solution, or indeed one with 9 or more clues.

That raises an interesting question for mathematicians: what is the minimum number of Sudoku clues that produces a unique answer?

This is a question that has hung heavy over the Sudoku community, not least because they think they know the answer. Sudoku fanatics have found numerous examples of grids with 17 clues that have a unique solution but they have never found one with 16 clues.

That suggests the minimum number is 17 but nobody has been able to prove that there isn’t a 16-clue solution lurking somewhere in puzzle space.

Enter Gary McGuire and pals at University College Dublin. These guys have solved the problem using the tried and trusted mathematical technique of sheer brute force.

Continued…

Keep Reading

Most Popular

Russian servicemen take part in a military drills
Russian servicemen take part in a military drills

How a Russian cyberwar in Ukraine could ripple out globally

Soldiers and tanks may care about national borders. Cyber doesn't.

Death and Jeff Bezos
Death and Jeff Bezos

Meet Altos Labs, Silicon Valley’s latest wild bet on living forever

Funders of a deep-pocketed new "rejuvenation" startup are said to include Jeff Bezos and Yuri Milner.

ai learning to multitask concept
ai learning to multitask concept

Meta’s new learning algorithm can teach AI to multi-task

The single technique for teaching neural networks multiple skills is a step towards general-purpose AI.

mouse engineered to grow human hair
mouse engineered to grow human hair

Going bald? Lab-grown hair cells could be on the way

These biotech companies are reprogramming cells to treat baldness, but it’s still early days.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.