For example, they prove that the number of ways of extending a partial
coloring of a graph is given by a polynomial. If the value of this
polynomial is zero for a given Sudoku puzzle, then the puzzle has no
solution; if the value is 1, then the puzzle has only one solution;
and so forth. They also prove that, in order for any Sudoku puzzle to
have only one solution, at least 8 of the 9 numbers must appear as
given entries in the puzzle; if only 7 numbers are given, then the
puzzle has at least two solutions. And this brings up an unsolved
mathematical question: "It would be extremely interesting to determine
under what conditions a partial coloring can be extended to a unique
[proper] coloring," Herzberg and Murty write.

http://www.scientificblogging.com/news/how_sudoku_can_help_you_solve_the_mysteries_of_graph_theory