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:
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.)