To ftg, I’d ask, what is the computational complexity of solving SAT (with inputs given in conjunctive normal form, let us say) via ordinary backtracking search? And what is the computational complexity of solving SAT via multiplying out from CNF to DNF?
I assert that in fact the work done in both cases is precisely isomorphic. But nevermind such a strong claim. Is it not the case that the computational complexity is the same in both cases? Can we at least agree on that?
Indistinguishable, thanks for bringing up that paper again. I’d like to point out again that that paper shows that there is a bright line difference between sudoku that can be solved with one-block elimination strategies and those that require multi-block elimination strategies. I believe that that is the exact distinction that some people are trying to make in this thread.
Chronos, your partial puzzle only requires one-block elimination strategies. The example I posted in post 89 is pretty much the simplest non-trivial example of a sudoko that requires multi-block elimination strategies. There is a real difference between these things.
I urge anyone to work through the example in post 89 to fully understand the difference or read the paper to see that this difference is rigorously defined.
I would have to disagree with this. See, when you “look at what is known, and thereby deduce the next square,” you are still engaged in trial and error, it’s just that the trials are simple enough that they don’t require much thought and don’t require you to write anything down.