Sudoku solver

[Dave Angel]

On 03/27/2015 05:25 AM, Chris Angelico wrote:
> On Fri, Mar 27, 2015 at 8:07 PM, Frank Millman <frank at chagford.com> wrote:
>> There seems to be disagreement over the use of the term 'trial and error'.
>> How about this for a revised wording -
>>
>> "It should be possible to reach that solution by a sequence of logical
>> deductions. Each step in the sequence must uniquely identify the contents of
>> at least one cell based on the information available. Each time a cell is
>> identified, that adds to the information available which can then be used to
>> identify the contents of further cells. This process continues until the
>> contents of all cells have been identified."
>>
>> Any puzzle that cannot be solved by this method does not qualify as a true
>> Sudoku puzzle.
>
> That's reasonable wording. Another way to differentiate between the
> "trial and error" that we're objecting to and the "logical deduction"
> that we're liking: Avoid backtracking. That is, you never guess a
> number and see if the puzzle's solvable, and backtrack if it isn't; at
> every step, the deductions you make are absolute certainties.
>
> They might, in some cases, not result in actual result numbers (you
> might deduce that "either this cell or that cell is a 2"), but it's a
> certainty, based solely on the clue numbers given.
>

I like that wording.  It fits what I meant by trial and error.

Frank:

But now I have to disagree about "true Sudoku puzzle."  As we said 
earlier, it might make sense to say that puzzles that cannot be solved 
that way are not reasonable ones to put in a human Sudoku book.  But why 
isn't it a "true Sudoku puzzle"?

Isn't the fact that one resorts to trial and error simply a consequence 
of the fact that he/she has run out of ideas for more direct rules and 
the data structures to support them?

The simpler rules can be built around a list of possible values for each 
cell.  More complex rules can have a more complex data structure for 
each cell/row/column/box.  And when you run out of ideas for all those, 
you use guess and backtrack, where the entire board's state is your data 
structure.
-- 
DaveA