Profile

Mr. Kit Bond

Contact Details


Bio

Mathematicians Solve the Problem of Sudoku Clues

Irish scientists have solved the so-called Sudoku clue problem. A preprint of their article appeared on the arXiv.org website.

Sudoku online is a puzzle, which is a 9 by 9 square, divided into 3 by 3 sub-squares. In the cells, it is necessary to arrange the numbers from 1 to 9 so that in any column, row or sub-square there are no two identical ones. In a typical puzzle, several clue numbers have already been placed, and the fewer such clues, the more difficult the puzzle is.

As part of the new work, scientists have answered the question of how many such tips are required for Sudoku to have an unambiguous solution. As it turned out, there should be at least 17 hints. It is noteworthy that an example of a problem with 16 hints, which has exactly two solutions, was already known.

For the work, scientists used a rather powerful algorithm for cutting off unnecessary options. To do this, they described the so-called bad sets - a set of numbers in a filled table, which can be replaced by another (hence the ambiguity). Then they counted how many of these bad sets could be "killed" by this or that clue.

As a result, the search was reduced to a little less than 5.5 billion options (there are about 1021 correct options for filling out Sudoku puzzles). These calculations, which were preceded by two years of testing the algorithm, were done on a supercomputer. As a result, scientists have found that 16 clues (or fewer) are not enough to "kill" all bad sets, so it is impossible to come up with a puzzle with so many clues and an unambiguous solution.

According to scientists, the scheme they created for reducing the number of options using bad sets can be used in other areas of research - for example, bioinformatics or automated software testing.