How are Sudoku puzzles created?

Question

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?

Answer 1

I would not have been sure, but Linux Ubuntu came with a sudoku program and a fair amount of information. The point, as far as computer involvement, is that any puzzle can be solved fairly quickly by the backtracking method, which was already old when I took Pascal in college in the 1970's. This includes confirming that there is only one solution...

Oh, since you brought it up, some of the best techniques are for puzzles with unique solutions. I think there is some sort of world championship, where puzzles may have more than one answer. Annoying.

Ubuntu judges the difficulty of a puzzle based entirely on the amount of effort to solve by backtracking. Meanwhile, many machine puzzles become trivial with a handful of human style tricks. I found many of these on computer developer pages; the best of these is the BUG principle, although it does not come up that often. I also made up some... The best collection, but not the best puzzles, was Mensa Guide to Solving Sudoku, by Peter Gordon, puzzles by Frank Longo. They discuss a solving technique by David Eppstein of MO.

The bad news has been this: in one edition of Ububtu, there was a button that said "Would you like to make more puzzles?" If I clicked on that, it would ask how many, then create that many new puzzles, quite random. However, on my old machine, with Ubuntu updates, I can't do that any more. Ubuntu thinks that it is creating new puzzles in background but it really isn't. On the other hand, both my printer and scanner work.