9
0
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.)
How do you win the competition? Shortest code? Fastest code? – beary605 – 2013-01-25T03:08:43.933
Shortest code. [missed the char limit by 1 character.] – Joe Z. – 2013-01-25T03:15:20.117
And if there are more than 52 regions, then what? – Mr Lister – 2013-01-25T09:17:16.067
You can assume there will not be more than 45 regions. – Joe Z. – 2013-01-25T12:01:33.410
Your "U" region is larger in your example input than in the picture – Dr. belisarius – 2013-01-25T16:40:47.123
Sorry; I've fixed it. – Joe Z. – 2013-01-25T17:34:48.330
And in your output string there is a
6
instead of3
(in the seventh row). – Howard – 2013-01-25T18:47:40.087Stupid fat-fingering. Thanks. – Joe Z. – 2013-01-25T18:52:13.120
1Can a number repeat within a cage? – Peter Taylor – 2013-01-29T15:40:08.967
You can treat the answer as no, as that is the rule usually followed by Killer Sudoku puzzlemakers. – Joe Z. – 2013-01-29T16:16:34.410