I recently read about the connection between solving Sudoku puzzles (and other graph coloring problems) and Groebner bases. This doesn't lead to an efficient solution technique, but it does link a popular topic with some real mathematics, e.g., the Groebner basis method in principle tells you how many solutions there are if there is more than one.
In practice, of course, any actual Sudoku has a unique solution. This raises a question that I have not yet found an answer to after looking around a bit: when a Sudoku puzzle is created, say by a computer, how is it determined that the puzzle truly has just one solution? (I am asking explicitly about the usual $9 \times 9$ puzzle, not an $n \times n$ puzzle for general $n$.) An algorithm that rapidly solves Sudoku puzzles need not be an algorithm that explains why a Sudoku puzzle has just one solution.
Also, how is it determined that a Sudoku puzzle is easy/medium/hard?