Challenge: Golf a sudoku solver. Bonus points to fast solutions as well. Correct solutions must provide all solutions to a given starting position (test data provided below).

If you want, you can use any/all of the following infrastructure:

1. @grid - starts with the initial position (with 0's for empty squares).
2. %search - contains 81 entries, indexed by 0-80, each pointing to an arrayref of 21 entries. These entries are squares that cannot contain the same value as the key.
3. sudoku_print() - a method that prints the sudoku board as listed in @grid.
4. Assume that the input has already been parsed into @grid.

I'll post my solutions in a response to this post.

Some samples are:

-,-,4,-,-,2,-,-,3
-,2,-,-,9,-,7,1,5
7,-,-,3,1,-,4,-,-
-,1,-,-,-,-,2,-,9
-,4,-,2,7,-,-,-,6
2,8,-,5,-,-,-,-,-
5,-,-,-,-,3,6,-,4
-,3,1,-,-,8,-,-,2
4,6,-,-,5,-,-,3,1

-,-,5,-,-,-,-,4,-
-,-,-,8,-,-,-,-,6
3,-,2,-,-,1,-,-,-
-,-,-,-,-,4,-,2,-
-,-,9,-,-,-,5,-,-
-,6,-,3,-,-,-,-,-
-,-,-,-,-,-,-,-,3
-,-,-,-,-,5,-,-,-
-,1,-,-,-,-,6,8,-

-,-,-,-,-,-,-,-,-
-,-,-,-,-,3,-,8,5
-,-,1,-,2,-,-,-,-
-,-,-,5,-,7,-,-,-
-,-,4,-,-,-,1,-,-
-,9,-,-,-,-,-,-,-
5,-,-,-,-,-,-,7,3
-,-,2,-,1,-,-,-,-
-,-,-,-,4,-,-,-,9

(This input has two solutions. Both are required to be correct.)
9,-,6,-,7,-,4,-,3
-,-,-,4,-,-,2,-,-
-,7,-,-,2,3,-,1,-
5,-,-,-,-,-,1,-,-
-,4,-,2,-,8,-,6,-
-,-,3,-,-,-,-,-,5
-,3,-,7,-,-,-,5,-
-,-,7,-,-,5,-,-,-
4,-,5,-,1,-,7,-,8
[download]