The shortest Sudoku solver is currently the following Ruby program, at 130 bytes long. It fits on 2 lines with no line longer than 80 characters. This program is about 25% shorter than the Python version! There is also an explanation of how this program works here:
def r a;!(i=a=~/0/)?p(a):([*?1..?9]-(0..80).map{|j|a[j]+(i-j)%9* (i/9^j/9)*(i/27-j/27|i%9/3-j%9/3)*9}).map{|k|r$`<<k<<$'}end;r *$*
Here is an example of using the solver to solve this puzzle:
$ ruby sudoku.rb 200370009009200007001004002050000800008000900006000040900100500800007600400089001
And the result:
"284375169639218457571964382152496873348752916796831245967143528813527694425689731"
The program is very fast for most inputs, but there are valid Sudoku puzzles that this program takes a very long time to solve (over an hour), for example:
------------- |...|...|.6.| |..7|3..|9..| |..8|9..|...| |---+---+---| |.71|...|...| |...|...|..8| |8..|.5.|6.4| |---+---+---| |.1.|2..|.9.| |2..|..4|...| |.69|...|.7.| -------------
To see this, use the following command:
ruby sudoku.rb 000000060007300900008900000071000000000000008800050604010200090200004000069000070