Implement a Non-Guessing Sudoku Solver Implement the shortest Sudoku solver.
Sudoku Puzzle:
 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A|   3   |     1 |
B|     6 |       |   5
C| 5     |       | 9 8 3
-+-----------------------
D|   8   |     6 | 3   2
E|       |   5   |
F| 9   3 | 8     |   6
-+-----------------------
G| 7 1 4 |       |     9
H|   2   |       | 8
I|       | 4     |   3

Answer:
 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7

Rules:

Assume all sudokus are solvable by logic only.
All input will be 81 characters long. Missing characters will be 0.
Output the solution as a single string.
The &quot;grid&quot; may be stored internally however you wish.
The solution must use a non-guessing solution. (see Sudoku Solver)

Example I/O:
&gt;sudoku.py &quot;030001000006000050500000983080006302000050000903800060714000009020000800000400030&quot;
832591674496387251571264983185746392267953418943812765714638529329175846658429137
RUBY (449 436 chars)

I=*(0..8)
b=$*[0].split('').map{|v|v&lt;'1'?I.map{|d|d+1}:[v.to_i]};f=b.map{|c|!c[1]}
[[z=I.map{|v|v%3+v/3*9},z.map{|v|v*3}],[x=I.map{|v|v*9},I],[I,x]
].map{|s,t|t.map{|i|d=[a=0]*10;s.map{|j|c=b[i+j];c.map{|v|d[v]+=1if !f[i+j]}
v,r=*c;s.map{|k|b[i+k].delete(v)if j!=k}if !r 
s[(a+=1)..8].map{|k|s.map{|l|b[i+l]-=c if l!=k&amp;&amp;l!=j}if c.size==2&amp;&amp;c==b[i+k]}}
v=d.index 1;f[i+k=s.find{|j|b[i+j].index v}]=b[i+k]=[v]if v}}while f.index(!1)
p b*''


Example:

C:\golf&gt;soduku2.rb 030001000006000050500000983080006302000050000903800060714000009020000800000400030
"832591674496387251571264983185746392267953418943812765714638529329175846658429137"


quick explanation:
Board b is an array of 81 arrays holding all the possible values for each cell.
The array on line three holds [offset,start_index] for each group (boxes,rows,columns).
Three tasks are performed while iterating through the groups.


The value of any cell of size 1 is removed from the rest of the group.
If any pair of cells contain the same 2 values, these values are removed from the rest of the group.
The count of each value is stored in d - if there is only 1 instance of a value, we set the containing cell to that value, and mark the cell fixed in f


Repeat until all cells are fixed.