London, Jan 7 (ANI): Sudoku fans would be happy to learn that there is now a limit to how hard the fiendish number puzzle can get.
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, reveal Mathematicians.
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, Gary McGuire at University College Dublin, Ireland, and his team 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, New Scientist reported.
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.
To solve the problem, McGuire and colleagues use a piece of software that can check any completed Sudoku grid for the presence of n-clue puzzles buried within it.
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.
After an exhaustive search that has run for a quite a few years, the team discovered no 16-clue puzzles, which implies there are no 15 or fewer clue puzzles either, so the minimum must be 17.
In addition to 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. (ANI)
|
|
Comments:
