[mzl]

Actually, for 9x9 Sudoku doing any more advanced propagation is pointless, since it will slow down the time to find the solution (assuming a reasonably fast search process). If one wants to solve 9x9 Sudokus without search, full propagation combined with shaving (hypothetical reasoning: if I assigned this square this value, woould it lead to an inconsistency) suffices as far as is known currently (no proof, just experiments, http://www.4c.ucc.ie/~hsimonis/sudoku.pdf).

For 16x16, it is more of a toss-up if one should use more advanced propagation. The solve-times are still so low though, that it doesn't really matter (tens of milliseconds). For 25x25 it starts to get interesting. In my experience, full propagation on lines, rows, and regions is needed, but more than that slows it down. Without a good heuristic (some learning process, prefferably coupled with randomized restarts), the solve-time easily goes up into hours. Wih a good heuristic, minutes seems to be a reasonable time-span to hope for.