No 16-clue Sudoku puzzles… finally proved!

I received an interesting email today from Gary McGuire containing a paper proving the result that I had long suspected — namely that there is no 16-clue Sudoku puzzle. (See this earlier blog post for some background.)

I have only skimmed the paper so far, but the basic method is clear enough – to examine each of the possible completed grids in turn and exhaustively search the grid to demonstrate that no 16-clue subgrid is uniquely completable. One way of doing this that does not involve actually solving every possible 16-clue subpuzzle is to observe that certain subsets of the cells must necessarily be “hit” by one of the 16 clues or they could simply be rearranged in the final solution. Finding so many subsets of this type that no collection of 16 cells can hit them all is then a (computer) proof that this particular grid contains no 16-clue uniquely completable subgrid.

I’ll add some more details when I have time to read the paper more carefully.

In the meantime, I won’t link to the paper yet, as while it has been uploaded to arxiv, it  won’t appear for a couple of days, presumably due to the holiday break.

Congratulations to Gary and his team!

Advertisements

2 thoughts on “No 16-clue Sudoku puzzles… finally proved!

Add yours

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Up ↑

%d bloggers like this: