GaimeGuy said:
False. Sudoku and Nonograms (Picross) are both NP-complete problems. You're realistically going to have to do at least a little bit of searching (that is, guessing how to fill in a square and then checking ahead to see how the puzzle pans out) for the vast majority of problems, although those you'll find in magazines or video games will typically have only one solution and be solvable by logic alone, as they are designed for humans.
False "False." is false.
All Sudoku games are solvable with pure logic.
Any process of "If this box is X, then this one is Y, and this one is Z, but I know that can't be Z, so that first box it can't be X." is a logical process, and can be generalized into a rule that you can add to your toolset to solve the puzzle. The typical "need to guess" cell in a Sudoku puzzle is simply a branching series of conditional logic. Because A4 is this, F4 is this or this, and F6 is (this or this) OR (this or this), etc.. A "guess and check" tactic on F4 is never necessary, but it is often much faster.
After a certain point, guessing is far easier (for peasants, programmers, and processors), than some of the crazy generalized log rules you have to come up with in some cases.
I wrote a Sudoku solving application for one of my classes.
By using simple to complex logical rules in order, then switching to guessing (a search algorithm) past a certain complexity threshold, you get the best performance. With pure, unordered logic, some very hard puzzles can take several minutes to solve. By applying logical rules in order of computational complexity, you can speed that up to a few seconds. You can get that down to a fraction of a second if you just search after a certain complexity point.
Any other game where you are solving for a specific state can be done in the same way.
Complexity / hardness has nothing to do with whether or not something is solvable with logic.