Short Sharp Science

Exhaustive search solves fiendish Sudoku mystery

Jacob Aron, reporter
(Image: Per Lindgren/Rex Features)

Relax, Sudoku fans. There is now a limit to how hard the fiendish number puzzle can get. Mathematicians have discovered that a Sudoku puzzle must provide at least 17 starting numbers, or clues, in order to be valid. Any fewer will not produce a unique answer.

It is easy to see that there must be some minimum number of clues required for a valid puzzle. Imagine a starting 9x9 grid with just a single "1" filled in - it's clear that this could correspond to many different answers. However, no one knew the exact number of clues required.

Now a team lead by Gary McGuire at University College Dublin, Ireland have proved it is not possible to create a 16-clue puzzle with a unique answer, so the minimum number of clues must be 17.

Their work ends an exhaustive search that has run for a quite a few years. Sudoku aficionados had already found nearly 50,000 17-clue puzzles, but no one had managed to find a completely unique 16-clue puzzle. The closest anyone had got was a 16-clue puzzle with just two possible solutions.

McGuire and colleagues solved the problem using a piece of software that can check any completed Sudoku grid for the presence of n-clue puzzles buried within it. To understand how this works, think of starting with a filled-out grid and gradually removing digits until you achieve a valid starting grid with n digits.

An earlier version of their software took an hour to search a single completed grid, but their latest revision can check for 16-clue puzzles in just a few seconds. That is important because there are around 6.7 x 10 ²¹ such grids to check, though exploiting various mathematical symmetries reduces that number to just under five and a half billion. After a search that tested all the possibilities and lasted the whole of 2011, the team discovered no 16-clue puzzles, which implies there are no 15 or fewer clue puzzles either, so the minimum must be 17.

Besides solving a Sudoku mystery, the team say their work could also be applied to solving the vertex cover problem, which arises in the branch of mathematics known as graph theory and has applications in gene sequencing and software testing.

http://www.newscientist.com/