Baue einen Killer Sudoku Solver

9

Sie dachten, normales Sudoku sei schwer, versuchen Sie es jetzt mit Killer Sudoku !

Im Spiel Killer Sudoku erhalten Sie überhaupt keine Zahlen. Stattdessen erhalten Sie Regionen, die sich zu einer bestimmten Anzahl summieren sollen. Betrachten Sie das folgende Beispiel aus Wikipedia:

Killer Sudoku Puzzle

Und seine Lösung:

Killer Sudoku Puzzle Lösung

Das Programm, das Sie schreiben, hat ein Format, das aus einer Folge von 81 Buchstaben besteht, die Regionen darstellen, gefolgt von einer Folge von Zahlen. Dann repräsentiert jede Zahl in der Sequenz die Summe der Zahlen in jedem der Buchstabenbereiche, beginnend mit "A", "B" usw.

Es wird dann eine Folge von 81 Ziffern ausgegeben, die die Lösung darstellen.

Das obige Beispielpuzzle hätte beispielsweise die folgende Eingabe:

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

Und die resultierende Ausgabe wäre:

215647398368952174794381652586274931142593867973816425821739546659428713437165289

Sie können davon ausgehen, dass die Eingabe gültig ist und die Bereiche immer in der Reihenfolge A, B, ..., Y, Z, a, b, ..., z angezeigt werden.

(Der kürzeste Code, der funktioniert, gewinnt.)

Joe Z.
quelle
Wie gewinnt man den Wettbewerb? Kürzester Code? Schnellster Code?
Beary605
Kürzester Code. [verpasste das Zeichenlimit um 1 Zeichen.]
Joe Z.
Und wenn es mehr als 52 Regionen gibt, was dann?
Herr Lister
Sie können davon ausgehen, dass es nicht mehr als 45 Regionen geben wird.
Joe Z.
1
Kann sich eine Zahl innerhalb eines Käfigs wiederholen?
Peter Taylor

Antworten:

4

R - 378 Zeichen

Vorausgesetzt

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

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

Nach 2.964.690 Iterationen dauert es auf meinem bescheidenen PC ungefähr eine Stunde, bis die erwartete Lösung erreicht ist.


De-Golf gespielt:

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
quelle
4

GolfScript, 138 Zeichen

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

Dies ist ein Killer-Sudoku-Löser in GolfScript. Es wird eine Eingabe in STDIN in zwei Zeilen erwartet, wie im obigen Beispiel angegeben.

Bitte beachten Sie: Da die Beschreibung des Puzzles keine Einschränkungen für die Ausführungszeit enthält, habe ich eine kleine Codegröße der Geschwindigkeit vorgezogen. Der Code testet alle 9 ^ 81 Grid-Konfigurationen auf eine Lösung, die auf einem langsamen Computer einige Zeit dauern kann ;-)

Howard
quelle
Können Sie das überprüfen? : P
Joe Z.
@ JoeZeng, es sieht einfach genug aus, um es für 4x4 zu optimieren. Hier ist ein Testfall:AABBCADEFFDDGGGG 6 7 4 8 2 3 10
Peter Taylor
@PeterTaylor Ihr Testfall hat vier verschiedene gültige Lösungen.
Joe Z.
4

Ruby, 970 Zeichen

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]

Der obige Ruby-Code steht im Gegensatz zu meinem GolfScript-Abonnement. Es ist ziemlich lang (und noch nicht vollständig golfen), aber auf Geschwindigkeit optimiert. Das oben angegebene Killer-Sudoku ist in weniger als einer Sekunde gelöst (mit meiner ursprünglichen Java-Version waren es nur wenige Millisekunden). Der Solver selbst ist eine grundlegende Implementierung des DLX-Algorithmus von Knuth.

Die Eingabe muss in zwei Zeilen auf STDIN erfolgen. Beispiel ( 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
Howard
quelle