The bit you're missing is not the propagation, it's the memoisation. Roughly summarised, norvig's alrogithm is:
1. Construct a 9x9 Array of possibility arrays containing the numbers 1-9.
2. When a possibility array is reduced to 1 element, remove this number from all related arrays (row, column, box).
3. Reduce the arrays to 1 number as specified by the initial puzzle.
4. If, after propagation all possibility arrays have 1 item, the puzzle is solved
5. Otherwise,choose one of the shortest possiblity arrays and try a value, backtrack if this leads to an unsolvable puzzle
The key points are the memoisation of possiblities, and choosing cells with the smallest number of possibilities for the search.
I have a suduko solver. It is what I consider "brute force", though it does not look any further down boards that do not satisfy the constraints of the game (i.e. values unique in rows, columns, 9-cells). Typically it executes in < 0.5 seconds. Can you supply a "hard" puzzle that will take too much time?