Now we all agree that pure logic vs trial-and-error is a somewhat fuzzy area, but it occurred to me that when it comes to software, we can be a little more definitive.
I decided to experiment with a stripped down DFS solver, using these simple data structures:
- Grid(R,C) (contains cell values)
- Domain(R,C,N) ( 1 if cell can be N, otherwise 0)
- Hsum(R,C) (horizontal sum for cell)
Vsum(R,C) (vertical sum for cell)
This elementary DFS solver has a domain-shaver that uses just one test function, CanBe(R,C,N), which returns 1 if this cell can be N. This function tests the horizontal and vertical runs containing the given cell, using the current domains, to see if there is at least one combination of values which has N in position R,C.
So this solver has no "frills" like hidden/naked pairs, triples, etc.
I then ripped out the recursion, leaving a purely iterative solver that just keeps shaving until it draws blood - ie. nothing changes. If all cells are set, it has a solution, otherwise it fails.
An interesting question now arises - can we take any well-formed puzzle (that has a unique solution), and change the clues (sums) so that the puzzle becomes pure, ie. that can be solved by this simple process?