Sudoku is a simple constraint resolution problem. The static constraints describe the rules of the game. The dynamic constraints are specified by the initial state of the board.

You seem to be implying that for some initial state (a partially filled board), there'll be only one correct solution (filled board).I'm quite sure that's not the case.

It's surely the case that for some problems where the board is mostly filled, that there is only one correct solution; I'd need to see a damn nifty proof to believe that is the case for all conceivable (and valid) starting states.

-David

If you are given a Sudoku grid to solve (such as in a newspaper or a puzzle book) and there is more than one solution to it, then you've gotten a decidedly inferior offering, some would say an invalid one (as would I).

I'm at a loss as to how you got from "only considered to be correct" to "all possible starting states". And proving that, for example, a standard grid with only a single digit filled in can be "solved" in more than one way is trivial.

But I would disagree with lidden if that was an implied assertion that a program for solving a Sudoku need not be able to deal with such flawed offerings. Indeed, it should probably be able to produce at least two solutions so that you can include them when you write to the source of the puzzle to complain. :)

- tye