Construye un solucionador de sudoku asesino

Pensaste que el sudoku regular era difícil, ¡ahora prueba Killer Sudoku !

En el juego de Killer Sudoku, no tienes ningún número en absoluto. En cambio, se le dan regiones que se dice que suman un cierto número. Considere el siguiente ejemplo, de Wikipedia:

Y su solución:

El programa que escriba tomará un formato que consiste en una secuencia de 81 letras que representan regiones, seguidas de una secuencia de números. Luego, cada número en la secuencia representa la suma de los números en cada una de las regiones de letras, comenzando desde "A", "B", etc.

Luego generará una secuencia de 81 dígitos que representa la solución.

Por ejemplo, el ejemplo de rompecabezas anterior tendría la siguiente entrada:

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

Y el resultado resultante sería:

215647398368952174794381652586274931142593867973816425821739546659428713437165289

Puede suponer que la entrada es válida y que las regiones siempre aparecerán en orden por A, B, ..., Y, Z, a, b, ..., z.

(El código más corto que funciona gana).

R - 378 caracteres

Asumiendo

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 caracteres:

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

tarda aproximadamente una hora en mi modesta PC para alcanzar la solución esperada, después de 2,964,690 iteraciones.

De-golf:

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 caracteres

n%~[~]:N;1/:P.&:L;9..*?{(.[{.9%)\9/}81*;]:§;L{.`{\~@@=*}+[P§]zip%{+}*\L?N==}%§9/..zip+\3/{{3/}%zip{{+}*}%}%{+}*+{.&,9=}%+1-,!{§puts}*.}do;

Este es un solucionador de sudoku asesino en GolfScript. Espera entrada en STDIN en dos filas como se muestra en el ejemplo anterior.

Tenga en cuenta: Dado que la descripción del rompecabezas no restringe el tiempo de ejecución, prefiero el tamaño de código pequeño a la velocidad. El código prueba todas las configuraciones de cuadrícula 9 ^ 81 para encontrar una solución que puede tomar algún tiempo en una computadora lenta ;-)

Rubí, 970 caracteres

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]

El código ruby ​​anterior es opuesto a mi suscripción a GolfScript. Es bastante largo (y aún no está totalmente golfizado), pero está optimizado para la velocidad. El sudoku asesino dado anteriormente se resuelve en menos de un segundo (con mi versión original de Java fue solo unos pocos milisegundos). El solucionador en sí es una implementación básica del algoritmo DLX de Knuth.

La entrada debe darse como dos líneas en STDIN. Ejemplo (en línea ):

> 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