Построить убийцу судоку Солвер

9

Вы думали, что обычное судоку было трудно, теперь попробуйте Killer Sudoku !

В игре Killer Sudoku вам вообще не дают никаких чисел. Вместо этого вам дают регионы, которые, как говорят, складываются до определенного числа. Рассмотрим следующий пример из Википедии:

пазл убийца судоку

И его решение:

решение головоломки убийца судоку

Программа, которую вы напишите, будет иметь формат, состоящий из последовательности из 81 буквы, представляющей регионы, за которой следует последовательность чисел. Затем каждое число в последовательности представляет собой сумму чисел в каждой из буквенных областей, начиная с «A», «B» и т. Д.

Затем он выведет последовательность из 81 цифры, представляющую решение.

Например, в приведенном выше примере головоломки будет иметь следующий вход:

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

Вы можете предположить, что ввод действителен, и что регионы всегда будут отображаться в порядке A, B, ..., Y, Z, a, b, ..., z.

(Самый короткий код, который работает, выигрывает.)

Джо З.
источник
Как вы выиграли конкурс? Самый короткий код? Самый быстрый код?
beary605
Кратчайший код. [пропустил ограничение на 1 символ.]
Джо З.
А если там более 52 регионов, то что?
Мистер Листер
Можно предположить, что не будет более 45 регионов.
Джо З.
1
Может ли число повторяться в клетке?
Питер Тейлор

Ответы:

4

R - 378 символов

Если предположить,

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 символов:

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

на моем скромном ПК требуется около часа, чтобы достичь ожидаемого решения после 2 964 690 итераций.


Де-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
flodel
источник
4

GolfScript, 138 символов

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

Это решатель убийц судоку в GolfScript. Он ожидает ввода в STDIN в две строки, как указано в примере выше.

Обратите внимание: поскольку описание головоломки не накладывает никаких ограничений на время выполнения, я предпочел небольшой размер кода, а не скорость. Код проверяет все 9 ^ 81 сеточные конфигурации для решения, которое может занять некоторое время на медленном компьютере ;-)

Говард
источник
Вы можете это проверить? : P
Джо З.
@JoeZeng, это выглядит достаточно легко, чтобы настроить его для 4x4. Вот тестовый пример:AABBCADEFFDDGGGG 6 7 4 8 2 3 10
Питер Тейлор
@PeterTaylor Ваш тестовый пример имеет четыре различных правильных решения.
Джо З.
4

Рубин, 970 знаков

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]

Приведенный выше код рубина противоположен моей подписке на GolfScript. Это довольно долго (и еще не полностью гольф), но оптимизировано для скорости. Приведенный выше убийственный судоку решается за считанные секунды (с моей оригинальной версией Java это было всего несколько миллисекунд). Сам решатель является базовой реализацией алгоритма Кнута DLX.

Ввод должен быть представлен в виде двух строк на STDIN. Пример ( онлайн ):

> 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
Говард
источник