Sudoku

How would you design a program to solve Sudoku puzzles?

How about the following data structure as a starting point?

    7 0 0 5 1 0 0 0 0
    5 0 0 8 0 9 0 0 0
    4 6 1 0 0 0 0 0 0
    0 0 0 0 9 0 0 8 2
    0 1 0 0 0 0 0 4 0
    2 4 0 0 3 0 0 0 0
    0 0 0 0 0 0 1 7 3
    0 0 0 3 0 7 0 0 9
    0 0 0 0 8 5 0 0 6
    
How about a matrix data structure where each cell is initialized with the digits 1 through 9, and then all digits already "spoken for" are removed?

Below is a representation of such a data structure. The numbers printed are the number of possible digits remaining at each location.

    1 4 4 1 1 4 6 4 2
    1 2 2 1 4 1 5 4 3
    1 1 1 2 2 2 6 4 3
    2 3 4 4 1 3 4 1 1
    4 1 6 3 4 3 5 1 2
    1 1 5 3 1 3 4 4 3
    3 4 6 4 3 3 1 1 1
    3 3 5 1 3 1 4 2 1
    3 4 5 4 1 1 2 1 1
    
impl