Você pensou que o sudoku normal era difícil, agora tente o Killer Sudoku !
No jogo do Killer Sudoku, você não recebe nenhum número. Em vez disso, você recebe regiões que se somam a um determinado número. Considere o seguinte exemplo, da Wikipedia:
E sua solução:
O programa que você escreve assumirá um formato que consiste em uma sequência de 81 letras representando regiões, seguida por uma sequência de números. Cada número na sequência representa a soma dos números em cada uma das regiões das letras, começando por "A", "B" etc.
Em seguida, ele produzirá uma sequência de 81 dígitos representando a solução.
Por exemplo, o exemplo de quebra-cabeça acima teria a seguinte entrada:
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
E a saída resultante seria:
215647398368952174794381652586274931142593867973816425821739546659428713437165289
Você pode assumir que a entrada é válida e que as regiões sempre aparecerão na ordem de A, B, ..., Y, Z, a, b, ..., z.
(O código mais curto que funciona ganha.)
fonte
Respostas:
R - 378 caracteres
Assumindo
378 caracteres:
leva cerca de uma hora no meu PC modesto para alcançar a solução esperada, após 2.964.690 iterações.
De-golfe:
fonte
GolfScript, 138 caracteres
Este é um solucionador de sudoku matador no GolfScript. Ele espera entrada no STDIN em duas linhas, conforme fornecido no exemplo acima.
Observe: Como a descrição do quebra-cabeça não restringe o tempo de execução, eu preferi o tamanho pequeno do código à velocidade. O código testa todas as configurações da grade 9 ^ 81 em busca de uma solução que pode levar algum tempo em um computador lento ;-)
fonte
AABBCADEFFDDGGGG
6 7 4 8 2 3 10
Ruby, 970 caracteres
O código ruby acima é o oposto da minha assinatura GolfScript. É bastante longo (e ainda não totalmente jogado), mas otimizado para velocidade. O sudoku assassino dado acima é resolvido em menos de um segundo (com a minha versão java original, eram apenas alguns mili segundos). O solucionador em si é uma implementação básica do algoritmo DLX de Knuth.
A entrada deve ser dada como duas linhas no STDIN. Exemplo ( online ):
fonte