Build a Killer Sudoku Solver You thought regular sudoku was hard, now try Killer Sudoku!

In the game of Killer Sudoku, you aren't given any numbers at all. Instead, you're given regions that are said to add up to a certain number. Consider the following example, from Wikipedia:



And its solution:



The program you write will take a format consisting of a sequence of 81 letters representing regions, followed by a sequence of numbers. Then each number in the sequence represents the sum of the numbers in each of the letter regions, starting from "A", "B", etc.

It will then output a sequence of 81 digits representing the solution.

For example, the example puzzle above would have the following input:

AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc
3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17


And the resulting output would be:

215647398368952174794381652586274931142593867973816425821739546659428713437165289


You may assume that the input is valid, and that the regions will always appear in order by A, B, ..., Y, Z, a, b, ..., z.

(Shortest code that works wins.)
GolfScript, 138 characters
n%~[~]:N;1/:P.&amp;:L;9..*?{(.[{.9%)\9/}81*;]:§;L{.`{\~@@=*}+[P§]zip%{+}*\L?N==}%§9/..zip+\3/{{3/}%zip{{+}*}%}%{+}*+{.&amp;,9=}%+1-,!{§puts}*.}do;

This is a killer sudoku solver in GolfScript. It expects input on STDIN in two rows as given in the example above.
Please note: Since the puzzle description does not make any restrictions on execution time I preferred small code size over speed. The code tests all 9^81 grid configurations for a solution which may take some time on a slow computer ;-)