Searching for the smallest, hardest Sudoku

sudoku

This Sudoku has 30 clues, but enthusiasts have found examples with only 17.

Sudoku are popular puzzles that can be seen in newspapers and puzzle books all around the world. The aim is to have a number in each one of the 81 boxes that make up the puzzle, while following certain rules. Some of the boxes start out with numbers in them already to act as clues. These clues make sure there is only one solution to the puzzle.

Most Sudoku have around 25 clues, but enthusiasts have long been interested in how few clues a Sudoku could have and still lead to only one answer. There are several Sudoku with only 17 clues, but no one had ever found a 16 clue Sudoku, so Gary McGuire from University College Dublin decided to look for one.

His strategy was simple – write down every possible answer, and then check to see if any of them could be posed as a 16 clue puzzle. Although the strategy was simple, it wasn’t going to be easy – there are 6 670 903 752 021 072 936 960 different possible answer grids to be checked.

Gary’s first task was to reduce the number of answer grids to check. He noticed that many answer grids were very similar. For example, some were exactly the same, only rotated, and others had some of the columns swapped. If he checked one of each group of similar grids, he wouldn’t need to check the partners. Using these similarities, he reduced the number of possibilities to check down to 5 472 730 538. This number was still large, but much more manageable.

He then wrote a computer program to check each possible grid to see if it had a 16 clue problem. The program worked by finding smaller areas in the puzzle that definitely needed a clue. He rewrote his program several times to make it faster, until he was satisfied.

Finally, he broke the calculations into lots of smaller jobs, and sent them off to the university’s super-computer. About one year after the calculations started, the final job was finished. He didn’t find any 16 clue Sudoku, leading him to conclude that Sudoku puzzles with fewer than 17 clues don’t exist.