Sudoku so hard, it took one team a giant computer and an entire year to solve a single puzzle


By web gangsta | Published:

Will Shortz Presents Simply Sinister Sudoku: 200 Hard Puzzles
Will Shortz Presents Simply Sinister Sudoku: 200 Hard Puzzles

If you enjoy working on Sudoku puzzles as much as Web Watch does, then this may be of interest to you.

First, let’s talk a little bit about what Sudoku is, for those Web Watch readers who may have been living under a rock for the past 10 years:

Sudoku is a puzzle that is rumored to have been created by a puzzle creator living in Indiana, seemingly around 1979.  In 1984, it was published in a Japanese newspaper… and the rest, they say, is history.  The puzzle typically is a 9×9 square, and the object is to put the numbers 1-9 into the boxes so each row, column and 3×3 sub-block contains all the 1-9 digits.

In other words, it’s a game that’s absolutely perfect of playing on an iPad or phone.

Web Watch has learned that one way to solve these is to work square-by-square, marking each square with all the potential numbers that it could contain by marking a single, small dot for each possible number.  Each dot’s position represents the number, so a dot in the upper left-hand corner of the box would equal “1”.  A dot in the middle-upper area would be “2”, and so on.

Yes, there’s a lot of erasing and it’s time consuming to fill out entirely… but when you’re done, you should have a handful of boxes that just contain one dot.  Those single dot boxes are easily filled in… and once you begin filling in actual numbers and erasing corresponding dots in related rows/columns/3×3 grid areas, the entire puzzle becomes enormously easy to solve.

The key is that each puzzle has a unique answer, based on very specifically pre-filled boxes that the puzzle creator left for you.  The more of these clues that are present when you begin the puzzle, the easier the puzzle tends to be.  The few of these pre-filled boxes you have, the harder the puzzle can be.

So here’s the puzzle that the team of mathematicians and a giant computer were working on that took an entire year to process:

HOW FEW BOXES NEED TO BE PRE-FILLED IN ORDER TO HAVE A UNIQUE SUDOKU SOLUTION?

The answer?

17.

After 12 months of number crunching and looking at over 5.4 billion different Sudoku puzzle combinations, they determined that it is physically impossible for a puzzle to have 16 clues and still result in a unique answer.  17 clues? Not a problem — it may be a hard puzzle for the average Sudoku solver to work on, but you’re still going to end up with a single, unique puzzle answer.

But 16 clues can lead you to a situation where one of two different solutions can exist… and that’s not fair to unleash on your puzzle-loving readers.

Now Web Watch does have one problem with their conclusion:  their theory that 17 is the ultimate answer to this question is based on this:

We have performed an exhaustive search for a 16-clue sudoku puzzle, and we did not find one, thereby proving that the answer is indeed 17.

While we fully support their result and likelihood of it being true, all real scientists will tell you is that “not finding one doesn’t thereby prove” that it doesn’t exist.   Maybe they’ll review the text of their conclusion and rewrite it into better scientific terms.