I'm not sure that I fully understand your question, but yes, I have built a solver. For each square it keeps track of what it can be and what it can't be. Simple deduction yields the answers. Much in the same way that a human would. No guessing is needed.

If you would like the program, just email me at joshuaarogers at gmail dot com. (Notice there is an a between joshua and rogers). I hope that it helps. Thanks.

Well, it turns out that it happens quite often that you cannot solve a puzzle via pure "flagging" alone. Take this example:

000|200|304
061|300|092
302|050|000
---+---+---
420|805|100
108|000|207
005|9X2|046
---+---+---
000|090|701
610|004|980
509|001|000

It becomes quite obvious that the X should be the number 1. Unfortunately, simply "flagging" what a blank can/cannot be doesn't provide you with a definate answer in this case, without doing a block uniqueness test. (Since it is the only square in the given block that can be the value 1, it must be the value 1). Unfortunately, by simply marking the squares that cannot be one from the row/column/coexist on same block rules, you cannot deduce this without another step.

Of course, this is easily fixed by occasionally doing a uniqueness test for all of the squares and updating them accordingly. But then you run into puzzles like this: (websudoku evil puzzle #8,873,319,999)

040|050|000
600|000|005
020|000|867
---+---+---
000|001|300
090|384|050
006|700|000
---+---+---
387|000|010
500|000|002
000|070|090

The algorithm so far can only fill in the puzzle to this point, then dies because of a lack of information:

040|050|000
600|000|005
025|000|867
---+---+---
050|001|300
090|384|050
036|705|000
---+---+---
387|000|010
509|000|002
000|070|090

So, no, you cannot solve the puzzle simply by "flagging" possible solutions using the core rules.

Here is the python program I've been using so far to solve the puzzles:

I'm going to look into the more advanced solution methods and add them to the program.

EDIT:

Yes, if the constrant's are not local, it is quite difficult to solve the puzzle using bits (or sets, as I have in the above example) alone without adding some more "interesting" logic.

EDIT2:

As for the more simple puzzle, it looks like this above program takes only 3 passes to solve it (three rounds through the while loop in the solve function) . And it only takes 3 passes before it realizes it cannot complete the harder puzzle as well.

Well, you could always just learn python. It is great for just hacking up stuff. I will admit though, some of the stuff I used in the above program is rather odd (yield, lambda's, [foo for bar in foobar()], reduce, filter)... . I'll be the first to admit some of those functions don't apply cleanly in C though (you can do a lot of them in C++ using the STL). (No, I'm not saying you can't do them in C, I'm saying that you can't do them this easily in C)

What you get which can solve all Sudoku's is a good search with back-tracking. I think you could use an A* and measure the distance to the goal by the number of local constraints. So that it gets "spot on" if there are only local constraints all the way to the solved puzzle. In that case you will also get an optimal search (as it's one of the features of a correctly implemented A*).