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

• How do you win the competition? Shortest code? Fastest code? – beary605 Jan 25 '13 at 3:08
• Shortest code. [missed the char limit by 1 character.] – Joe Z. Jan 25 '13 at 3:15
• And if there are more than 52 regions, then what? – Mr Lister Jan 25 '13 at 9:17
• You can assume there will not be more than 45 regions. – Joe Z. Jan 25 '13 at 12:01
• Can a number repeat within a cage? – Peter Taylor Jan 29 '13 at 15:40

## R - 378 characters

Assuming

x="AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc"
y="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"


378 characters:

z=strsplit
v=sapply
R=rep(1:9,9)
C=rep(1:9,e=9)
N=1+(R-1)%/%3+3*(C-1)%/%3
G=z(x,"")[[1]]
M=as.integer(z(y," ")[[1]])[order(unique(G))]
s=c(1,rep(NA,80))
i=1
repeat if({n=function(g)!any(v(split(s,g),function(x)any(duplicated(x,i=NA))))
S=v(split(s,G),sum)
n(R)&&n(C)&&n(N)&&n(G)&&all(is.na(S)|S==M)}){if(i==81)break;i=i+1;s[i]=1}else{while(s[i]==9){s[i]=NA
i=i-1};s[i]=s[i]+1}
s


takes about an hour on my modest PC to reach the expected solution, after 2,964,690 iterations.

De-golfed:

ROWS   <- rep(1:9, 9)
COLS   <- rep(1:9, each = 9)
NONETS <- 1 + (ROWS - 1) %/% 3 + 3 * (COLS - 1) %/% 3
CAGES  <- strsplit(x, "")[[1]]
SUMS   <- as.integer(strsplit(y, " ")[[1]])[order(unique(CAGES))]

is.valid <- function(sol) {

has.no.repeats <- function(sol, grouping) {
!any(vapply(split(sol, grouping),
function(x) any(duplicated(x, incomparables = NA)),
logical(1)))
}
has.exp.sum <- function(sol, grouping, exp.sums) {
sums <- vapply(split(sol, grouping), sum, integer(1))
all(is.na(sums) | sums == exp.sums)
}

has.no.repeats(sol, ROWS  ) &&
has.no.repeats(sol, COLS  ) &&
has.no.repeats(sol, NONETS) &&
has.no.repeats(sol, CAGES ) &&
has.exp.sum(sol, CAGES, SUMS)
}

sol <- c(1L, rep(NA, 80)) # start by putting a 1
i <- 1L                   # in the first cell
it <- 0L

repeat {
it <- it + 1L
if (it %% 100L == 0L) print(sol)
if(is.valid(sol)) {         # if everything looks good
if (i == 81L) break         # we are either done
i <- i + 1L                 # or we move to the next cell
sol[i] <- 1L                # and make it a 1
} else {                    # otherwise
while (sol[i] == 9L) {      # while 9s are found
sol[i] <- NA             # replace them with NA
i <- i - 1L              # and move back to the previous cell
}
sol[i] <- sol[i] + 1L       # when a non-9 is found, increase it
}                           # repeat
}
sol


### GolfScript, 138 characters

n%~[~]:N;1/:P.&:L;9..*?{(.[{.9%)\9/}81*;]:§;L{.{\~@@=*}+[P§]zip%{+}*\L?N==}%§9/..zip+\3/{{3/}%zip{{+}*}%}%{+}*+{.&,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 ;-)

• Can you verify it? :P – Joe Z. Jan 29 '13 at 16:17
• @JoeZeng, it looks easy enough to tweak it for 4x4. Here's a test case: AABBCADEFFDDGGGG 6 7 4 8 2 3 10 – Peter Taylor Jan 30 '13 at 13:32
• @PeterTaylor Your test case has four different valid solutions. – Joe Z. Jan 30 '13 at 18:37

### Ruby, 970 characters

A,B=gets,gets.split
L=[]
R=[]
U=[]
D=[]
N=[]
C=[]
S=[]
O=[0]*81
z='A'
(0..324).map{|j|U<<j;D<<j;R<<(j+1)%325;L<<(j+324)%325;N<<j;C<<j;S<<0}
X=->s,j,c,cf,n{j<81?(z==A[j]?(0..8).map{|i|X[s-1-i,j+1,c+[i],cf+[1+j,1+81+27*i+j/9,1+81+27*i+9+j%9,1+81+27*i+18+j/3%3+j/27*3],n+[i+1]]}:X[s,j+1,c,cf,n+[0]]if s>=0):(h=U.size;cf.uniq.sort.map{|l|N<<n;L<<(L[h]||h);R<<h;U<<U[l];D<<l;C<<l;S[l]+=1;L[R[-1]]=R[L[-1]]=U[D[-1]]=D[U[-1]]=L.size-1}if s==0)}
Y=->c{L[R[c]]=L[c];R[L[c]]=R[c];i=D[c];(j=R[i];(U[D[j]]=U[j];D[U[j]]=D[j];S[C[j]]-=1;j=R[j])while j!=i;i=D[i])while i!=c}
Z=->c{i=U[c];(j=L[i];(S[C[j]]+=1;U[D[j]]=j;D[U[j]]=j;j=L[j])while j!=i;i=U[i])while i!=c;L[R[c]]=c;R[L[c]]=c}
B.map{|k|X[k.to_i,0,[],[],[]];z=z=='Z'?'a':z.next}
s=->k{c=R[0];c<1?(\$><<(O[0,k].map{|s|N[s]}.transpose.map &:max)*""):(g=S[b=c];g=S[b=c]if S[c]<g while 0<c=R[c];Y[b];r=D[b];(O[k]=r;j=R[r];(Y[C[j]];j=R[j])while j!=r;s[k+1];r=O[k];c=C[r];j=L[r];(Z[C[j]];j=L[j])while j!=r;r=D[r])while r!=b;Z[b])}
s[0]


The above ruby code is opposite to my GolfScript subscription. It is quite long (and not yet fully golfed), but optimized for speed. The killer sudoku given above is solved in well under a second (with my original java version it was only a few milli seconds). The solver itself is a basic implementation of Knuth's DLX algorithm.

Input must be given as two lines on STDIN. Example (online):

> 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

215647398368952174794381652586274931142593867973816425821739546659428713437165289
`