Bangun Solver Sudoku Pembunuh

9

Anda mengira sudoku biasa itu sulit, sekarang coba Killer Sudoku !

Dalam permainan Killer Sudoku, Anda tidak diberi nomor sama sekali. Sebagai gantinya, Anda diberikan wilayah yang dikatakan menambahkan hingga jumlah tertentu. Pertimbangkan contoh berikut, dari Wikipedia:

puzzle pembunuh sudoku

Dan solusinya:

solusi puzzle pembunuh sudoku

Program yang Anda tulis akan mengambil format yang terdiri dari urutan 81 huruf yang mewakili wilayah, diikuti oleh urutan angka. Kemudian setiap angka dalam urutan mewakili jumlah angka di masing-masing daerah surat, mulai dari "A", "B", dll.

Ini kemudian akan menampilkan urutan 81 digit yang mewakili solusi.

Sebagai contoh, contoh puzzle di atas akan memiliki input berikut:

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

Dan output yang dihasilkan adalah:

215647398368952174794381652586274931142593867973816425821739546659428713437165289

Anda dapat mengasumsikan bahwa input tersebut valid, dan bahwa wilayah akan selalu muncul dalam urutan oleh A, B, ..., Y, Z, a, b, ..., z.

(Kode terpendek yang berfungsi akan menang.)

Joe Z.
sumber
Bagaimana Anda memenangkan kompetisi? Kode terpendek? Kode tercepat?
beary605
Kode terpendek. [melewatkan batas karakter dengan 1 karakter.]
Joe Z.
Dan jika ada lebih dari 52 wilayah, lalu apa?
Tuan Lister
Anda dapat mengasumsikan tidak akan ada lebih dari 45 wilayah.
Joe Z.
1
Bisakah angka diulang dalam kandang?
Peter Taylor

Jawaban:

4

R - 378 karakter

Asumsi

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

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

Dibutuhkan sekitar satu jam pada PC sederhana saya untuk mencapai solusi yang diharapkan, setelah 2.964.690 iterasi.


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

GolfScript, 138 karakter

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

Ini adalah solver pembunuh sudoku di GolfScript. Ia mengharapkan input pada STDIN dalam dua baris seperti yang diberikan dalam contoh di atas.

Harap dicatat: Karena deskripsi puzzle tidak membatasi waktu eksekusi, saya lebih suka ukuran kode kecil daripada kecepatan. Kode ini menguji semua konfigurasi jaringan 9 ^ 81 untuk solusi yang mungkin memakan waktu lama di komputer yang lambat ;-)

Howard
sumber
Bisakah Anda memverifikasinya? : P
Joe Z.
@ Joeng, terlihat cukup mudah untuk mengubah ukurannya menjadi 4x4. Berikut ini adalah ujiannya:AABBCADEFFDDGGGG 6 7 4 8 2 3 10
Peter Taylor
@PeterTaylor Kaset uji Anda memiliki empat solusi valid berbeda.
Joe Z.
4

Ruby, 970 karakter

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]

Kode ruby ​​di atas berlawanan dengan langganan GolfScript saya. Ini cukup panjang (dan belum sepenuhnya golf), tetapi dioptimalkan untuk kecepatan. Sudoku pembunuh yang diberikan di atas diselesaikan dalam waktu kurang dari satu detik (dengan versi java asli saya hanya beberapa mili detik). Solver itu sendiri adalah implementasi dasar dari algoritma DLX Knuth.

Input harus diberikan sebagai dua baris pada STDIN. Contoh ( 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
sumber