Combinações de Kakuro

Como não consigo fazer aritmética mental, luto frequentemente com o quebra- cabeça de Kakuro , que exige que a vítima calcule repetidamente quais números distintos no intervalo de 1 a 9 (inclusive) somam outro número no intervalo de 1 a 45 quando você sabe como muitos números existem. Por exemplo, se você quiser saber como obter 23 de 3 números, a única resposta é 6 + 8 + 9. (Essa é a mesma idéia que o Killer Sudoku, se você estiver familiarizado com isso).

Às vezes, você terá outras informações, como a de que o número 1 não pode estar presente; portanto, para atingir 8 em apenas 2 números, você pode usar apenas 2 + 6 e 3 + 5 (você não pode usar 4 + 4, porque eles são não distinto). Como alternativa, pode ser que você já tenha encontrado um 3 na solução e, portanto, algo como 19 em 3 números deve ser 3 + 7 + 9.

Sua tarefa é escrever um programa que lista todas as soluções possíveis para um determinado problema, em uma ordem estrita, em um layout estrito.

Entrada

Sua solução pode receber as entradas como uma única string ASCII através de stdin, um argumento de linha de comando, um argumento para uma função, um valor deixado na pilha ou qualquer loucura que sua linguagem esotérica favorita empregue. A cadeia está no formato

number_to_achieve number_of_numbers_required list_of_rejected_numbers list_of_required_numbers

Os 2 primeiros argumentos são números inteiros típicos de zero a zero na base 10, nos intervalos de 1 a 45 e 1 a 9, respectivamente (usar um ponto decimal seria uma entrada inválida); as duas listas são apenas dígitos alinhados, sem delimitação em nenhuma ordem específica sem repetição ou '0' se forem listas vazias. Não pode haver dígitos compartilhados entre as listas (exceto 0). Os delimitadores são espaços únicos.

Resultado

Sua saída deve começar com uma linha que contenha o número de soluções possíveis. Seu programa deve imprimir soluções delimitadas por quebra de linha classificadas por cada dígito cada vez mais significativo, onde cada dígito é colocado na posição em que estaria se você listasse os números de 1 a 9. Os exemplos abaixo esperam que isso fique mais claro.

Se uma entrada inválida for fornecida, não me importo com o que o seu programa faz, embora prefira que não zere meu setor de inicialização.

Exemplos

Para este exemplo de entrada

19 3 0 0

O resultado esperado seria

5
 2     89
  3   7 9
   4 6  9
   4  78 
    56 8 

Observe os espaços no lugar de cada número "ausente", eles são necessários; Eu não estou incomodado com espaços que não têm um número depois deles (como os 9s ausentes acima). Você pode assumir que o que quer que esteja imprimindo usará uma fonte de espaço mono. Observe também a ordem, na qual as soluções com um dígito menor menor são listadas primeiro e, em seguida, aquelas com o menor dígito menor, etc.

Outro exemplo, baseado no exposto acima

19 3 57 9

O resultado esperado seria

2
 2     89
   4 6  9

Observe que todo resultado contém 9 e nenhum resultado contém 5 ou 7.

Se não houver soluções, por exemplo

20 2 0 0

Então você deve apenas produzir uma única linha com um 0.

0

Intencionalmente, fiz a análise da entrada parte da diversão desta pergunta. Isso é código-golfe, que a solução mais curta vença.

GolfScript, 88 caracteres

~[[]]10,:T{{1$+}+%}/\{\0+`-!}+,\{0`+\`&!}+,\{\,=}+,\{\{+}*=}+,.,n@{1T>''*T@-{`/' '*}/n}/

Uma implementação direta no GolfScript. Recebe entrada do STDIN ou da pilha.

O código pode ser testado aqui .

Código com alguns comentários:

### evaluate the input string
~                     

### build all possible combinations of 0...9
[[]]              # start with set of empty combination
10,:T             #
{                 # for 0..9
  {1$+}+%         #   copy each item of set and append current digit to this copy
}/                # end for

### only keep combination which the digits given as last argument (minus 0)
\{                # start of filter block
  \0+`            #   add zero to combination and make string out of it
  -!              #   subtract from last argument -> check argument contains any
                  #     excess characters
}+,               # end of filter block


### remove any combination which contains either 0 or any digit from 2nd last argument
\{                # start of filter block
  0`+             #   take argument and append 0
  \`              #   stringify combination
  &!              #   check if no characters are common
}+,               # end of filter block

### filter for correct length
\{                # start of filter block
  \,              #   calc length of combination
  =               #   check if equal to second argument
}+,               # end of filter block

### filter for correct sum
\{                # start of filter block
  \{+}*           #   sum all digits of combination
  =               #   compare with first argument
}+,               # end of filter block

### output
.,                # determine size of set
n                 # append newline
@{                # for each combination in set
  1T>''*          #   generate "123456789"
  T@-             #   generate anti-set of current combination  
  {`/' '*}/       #   replace (in the string) each digit within the 
                  #   anti-combination with a space characters
  n               #   append newline
}/                # end for

JavaScript (E6) 172 180 275 296

Como uma função (testável) com 1 argumento de string e retornando a saída solicitada. Para ter uma mudança real na saída, retorne com alert (), a mesma contagem de bytes, mas cuidado, a fonte do alerta não é monoespaçada.

F=i=>{
  [t,d,f,m]=i.split(' ');
  for(l=0,r='',k=512;--k;!z&!h&!o&&(++l,r+=n))
    for(z=n='\n',h=d,o=t,b=i=1;i<=9;b+=b)
      z-=~(b&k?(--h,o-=i,n+=i,f):(n+=' ',m)).search(i++);
  return l+r
}

Teste no console do FireFox ou FireBug

console.log(['19 3 0 0','19 3 57 9','19 3 57 4','20 2 0 0'].map(x=>'\n'+x+'\n' +F(x)).join('\n'))

Saída de teste:

19 3 0 0
5
 2     89
  3   7 9
   4 6  9
   4  78 
    56 8 

19 3 57 9
2
 2     89
   4 6  9

19 3 57 4
1
   4 6  9

20 2 0 0
0

Ungolfed

F=i=>{
  [target, digits, forbidden, mandatory]=i.split(' ')

  result = '', nsol=0
  for (mask = 0b1000000000; --mask > 0;)
  {
    cdigits = digits
    ctarget = target
    bit = 1
    numbers = ''
    for (digit = 9; digit > 0; bit += bit, digit--)
    {

      if (bit & mask)
      {
        if (forbidden.search(digit)>=0) break;
        cdigits--;
        ctarget -= digit;
        numbers = digit + numbers;
      }
      else
      {
        if (mandatory.search(digit)>=0) break;
        numbers = ' '+numbers;
      }
    }
    if (ctarget==0 && cdigits == 0)
    {
        result += '\n'+numbers
        nsol++
    }
  }
  return nsol + result
}

Mathematica, 239 bytes

(Admito que comecei a trabalhar nisso enquanto ainda estava na caixa de areia.)

{t,n,a,b}=FromDigits/@StringSplit@i;Riffle[c=Cases[Union/@IntegerPartitions[t,n,Complement[r=Range@9,(d=IntegerDigits)@a]],k_/;(l=Length)@k==n&&(b==0||l[k⋂d@b]>0)];{(s=ToString)@l@c}~Join~((m=#;If[m~MemberQ~#,s@#," "]&/@r)&/@c),"\n"]<>""

Ungolfed

{t, n, a, b} = FromDigits /@ StringSplit@i;
Riffle[
  c = Cases[
    Union /@ IntegerPartitions[
      t, n, Complement[r = Range@9, (d = IntegerDigits)@a
       ]
      ],
    k_ /; (l = Length)@k == 
       n && (b == 0 || l[k ⋂ d@b] > 0)
    ];
  {(s = ToString)@l@c}~
   Join~((m = #; If[m~MemberQ~#, s@#, " "] & /@ r) & /@ c),
  "\n"] <> ""

Ele espera que a string de entrada seja armazenada i.

É bastante simples. Primeiro, analise a entrada. Então, eu costumo IntegerPartitionsdescobrir como posso dividir o primeiro número nos números permitidos. Depois, filtro todas as partições que usam duplicatas ou não contêm os números necessários. E, em seguida, para cada solução que eu criar uma lista a partir 1de 9e converter os atuais números em sua representação de cadeia e os outros em espaços. E então concatenar tudo.

Groovy - 494 caracteres

Resposta grande e sem inspiração, mas usa o Google Guava para gerar o "conjunto de energia".

Golfe:

@Grab(group='com.google.guava', module='guava', version='17.0')
m=(args.join(" ")=~/(\d+) (\d+) (\d+) (\d+)/)[0]
i={it as int}
n=i(m[1])
r=i(m[2])
j=[]
m[3].each{if(i(it))j<<i(it)}
q=[]
m[4].each{if(i(it))q<<i(it)}
d=1..9 as Set<Integer>
t=[]
com.google.common.collect.Sets.powerSet(d).each{x->
if(x.sum()==n&&x.size()==r&&x.disjoint(j)&&x.containsAll(q)) {
s="";for(i in 0..8){if(x.contains(i+1)){s+=(i+1) as String}else{s+=" "}};t<<s}
}
p={println it}
p t.size()
t.sort().reverse().each{p it}

Amostras de execuções:

$ groovy K.groovy 19 3 0 0 
5
 2     89
  3   7 9
   4 6  9
   4  78 
    56 8 
$ groovy K.groovy 19 3 5 0 
4
 2     89
  3   7 9
   4 6  9
   4  78 
$ groovy K.groovy 19 3 5 9
3
 2     89
  3   7 9
   4 6  9
$ groovy K.groovy 20 2 0 0 
0

Ungolfed:

@Grab(group='com.google.guava', module='guava', version='17.0')

m=(args.join(" ")=~/(\d+) (\d+) (\d+) (\d+)/)[0]
i={it as int}
n=i(m[1])
r=i(m[2])

j=[]
m[3].each{if(i(it))j<<i(it)}
q=[]
m[4].each{if(i(it))q<<i(it)}

d=1..9 as Set<Integer>
t=[]

com.google.common.collect.Sets.powerSet(d).each{ x ->
    if(x.sum()==n && x.size()==r && x.disjoint(j) && x.containsAll(q)) {
        s=""
        for(i in 0..8) {
            if(x.contains(i+1)){s+=(i+1) as String}else{s+=" "}
        }
        t<<s
    }
}

p={println it}
p t.size()
t.sort().reverse().each{p it}