Construisez un solveur Killer Sudoku

9

Vous pensiez que le sudoku ordinaire était difficile, essayez maintenant Killer Sudoku !

Dans le jeu de Killer Sudoku, vous ne recevez aucun numéro. Au lieu de cela, on vous donne des régions qui totaliseraient un certain nombre. Prenons l'exemple suivant, de Wikipedia:

puzzle sudoku tueur

Et sa solution:

killer sudoku puzzle solution

Le programme que vous écrivez prendra un format composé d'une séquence de 81 lettres représentant des régions, suivie d'une séquence de chiffres. Ensuite, chaque nombre dans la séquence représente la somme des nombres dans chacune des régions de lettres, en commençant par "A", "B", etc.

Il affichera ensuite une séquence de 81 chiffres représentant la solution.

Par exemple, l'exemple de puzzle ci-dessus aurait l'entrée suivante:

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

Et la sortie résultante serait:

215647398368952174794381652586274931142593867973816425821739546659428713437165289

Vous pouvez supposer que l'entrée est valide et que les régions apparaîtront toujours dans l'ordre par A, B, ..., Y, Z, a, b, ..., z.

(Le code le plus court qui fonctionne gagne.)

Joe Z.
la source
Comment gagnez-vous le concours? Code le plus court? Code le plus rapide?
beary605
Code le plus court. [a raté la limite de caractères par 1 caractère.]
Joe Z.
Et s'il y a plus de 52 régions, alors quoi?
M. Lister
Vous pouvez supposer qu'il n'y aura pas plus de 45 régions.
Joe Z.
1
Un nombre peut-il se répéter dans une cage?
Peter Taylor

Réponses:

4

R - 378 caractères

En supposant

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 caractères:

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

prend environ une heure sur mon modeste PC pour atteindre la solution attendue, après 2 964 690 itérations.


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
flodel
la source
4

GolfScript, 138 caractères

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

Ceci est un solveur de sudoku tueur dans GolfScript. Il attend l'entrée sur STDIN sur deux lignes comme indiqué dans l'exemple ci-dessus.

Veuillez noter: Étant donné que la description du puzzle ne fait aucune restriction sur le temps d'exécution, j'ai préféré une petite taille de code à la vitesse. Le code teste toutes les configurations de grille 9 ^ 81 pour une solution qui peut prendre un certain temps sur un ordinateur lent ;-)

Howard
la source
Pouvez-vous le vérifier? : P
Joe Z.
@JoeZeng, il semble assez facile de le modifier pour 4x4. Voici un cas de test:AABBCADEFFDDGGGG 6 7 4 8 2 3 10
Peter Taylor
@PeterTaylor Votre cas de test a quatre solutions valides différentes.
Joe Z.
4

Ruby, 970 caractères

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]

Le code rubis ci-dessus est opposé à mon abonnement GolfScript. Il est assez long (et pas encore entièrement golfé), mais optimisé pour la vitesse. Le sudoku tueur donné ci-dessus est résolu en moins d'une seconde (avec ma version java d'origine, il ne s'agissait que de quelques milli secondes). Le solveur lui-même est une implémentation de base de l'algorithme DLX de Knuth.

L'entrée doit être donnée sur deux lignes sur STDIN. Exemple (en ligne ):

> 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
Howard
la source