Build A Killer Sudoku Solver
Answer :
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 ;-)
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 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] 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
Comments
Post a Comment