[glenjamin]

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.