In the last section, we counted ways of completing an empty Sudoku puzzle. Suppose your best friend gives you a self-made Sudoku puzzle like the following one.

After a while of staring at it and not getting anywhere, you might wonder if the puzzle “actually has a solution” (what do we mean by that anyway?). It would be nice to know answers to the following questions: is there an easy way to decide if there is more than one way of completing the grid? Is there an easy way to decide if it is possible to complete a given grid?

The answer is disappointing. In general, it is very hard to decide (without the use of a computer) if a Sudoku puzzle has a solution, and if there are several ways of completing a partially filled-in grid.

Uniqueness of solutions

In activity 4, we learned that a 9x9 Sudoku with only four empty cells still need not have a unique solution. On the other hand, we show in activity 5 that every solvable 9x9 Sudoku with no more than 3 empty cells has at most one solution.

Here is one more interesting conjecture: the smallest number of of filled-in cells that is needed for a 9x9 puzzle with a unique solution is  probably 17 (http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Ordinary_Sudoku). Several puzzles have been found that need only 17 filled-in cells for a unique solution, and it is very unlikely (based on an extensive search using computers) that puzzles which have a unique solutions with only 16 clues or less exist.

Aside from those results, there are no easy-to-use criteria to decide whether a Sudoku has a unique solution or not. However, Sudoku puzzles in newspapers or books usually contain puzzles with unique solutions only.

Existence of solutions

Given a Sudoku puzzle, can we decide in a systematic way if there is at least one way of filling it in? Yes, we can. However, in many cases it’s quite a lot of work. We will learn about a suitable method in one of the later sections.