Implemente o menor solucionador de Sudoku usando adivinhação. Como recebi alguns pedidos, adicionei isso como uma pergunta alternativa para aqueles que desejam implementar um solucionador de sudoku de força bruta.
Quebra-cabeça Sudoku:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 3 | 1 |
B| 6 | | 5
C| 5 | | 9 8 3
-+-----------------------
D| 8 | 6 | 3 2
E| | 5 |
F| 9 3 | 8 | 6
-+-----------------------
G| 7 1 4 | | 9
H| 2 | | 8
I| | 4 | 3
Responda:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7
Regras:
- Suponha que todos os labirintos sejam solucionáveis apenas pela lógica.
- Todas as entradas terão 81 caracteres. Os caracteres ausentes serão 0.
- Saída da solução como uma única sequência.
- A "grade" pode ser armazenada internamente da maneira que desejar.
- A solução deve usar uma solução de adivinhação de força bruta.
- As soluções devem ser resolvidas dentro de um prazo razoável.
Exemplo de E / S:
>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
code-golf
game
puzzle-solver
sudoku
snmcdonald
fonte
fonte
Respostas:
k (72 bytes)
O crédito é para Arthur Whitney, criador da linguagem k.
fonte
Python, 188 bytes
Esta é uma versão mais resumida da minha submissão vencedora para o CodeSprint Sudoku , modificada para entrada da linha de comando em vez de stdin (conforme o OP):
Se você estiver usando Python 2,
'%d'%5**18
poderá ser substituído por`5**18`
para salvar 3 bytes.Para torná-lo mais rápido, você pode substituir
'%d'%5**18
por qualquer permutação'123456789'
a um custo de 1 byte.Se você quer que ele para aceitar a entrada em stdin em vez disso, você pode substituir
import sys;f(sys.argv[1])
comf(raw_input())
, trazendo-o para baixo para 177 bytes .EDIT: Aqui está um link para uma explicação mais detalhada.
fonte
Python, 197 caracteres
fonte
Resposta em D:
Com a entrada de amostra, são necessários .033s no meu Phenom II X6 1090T quando compilados com
dmd -w
(ou seja, sem otimizações) e são necessários .011s quando compilados comdmd -w -O -inline -release
(ou seja, com otimizações).fonte
J, 103
tempo de execução esperado: O (bilhões de anos)
fonte
Perl, 120 bytes
Lembro-me de jogar golfe em 2008 ... De fato, ele parou de funcionar no perl 5.12, pois a configuração implícita de @_ by split foi removida. Portanto, tente apenas isso em um perl suficientemente antigo.
Execute com a entrada em STDIN:
sudoku.pl
:fonte
Perl, 235 caracteres
Esta é uma versão em golfe de algo que eu publiquei há muitos anos na lista de discussão Fun With Perl : um regexp de resolução de sudoku.
Basicamente, ele controla a entrada em 81 linhas, cada uma contendo todos os números que podem ocorrer no quadrado correspondente. Em seguida, constrói um regexp para corresponder a um número de cada linha, usando referências anteriores e asserções negativas à cabeça para rejeitar soluções que violam as restrições de linha, coluna ou região. Em seguida, ele combina a string com o regexp, permitindo que o mecanismo de regexp do Perl faça o trabalho duro de teste e retorno.
Surpreendentemente, é possível criar um único regexp que funcione para qualquer entrada, como meu programa original. Infelizmente, é muito lento, então eu baseei o código golfado aqui na versão hardcoded-givens ( encontrada mais tarde no thread do FWP ), que ajusta o regexp para rejeitar antecipadamente quaisquer soluções que ele saiba que violarão mais tarde uma restrição. Isso o torna razoavelmente rápido para sudokus de nível fácil a moderado, embora os mais difíceis ainda possam demorar um pouco para serem resolvidos.
Execute o código com
perl -M5.010
para ativar osay
recurso Perl 5.10+ . A entrada deve ser fornecida na entrada padrão e a solução será impressa na saída padrão; exemplo:fonte
Script de café de 1 liner
solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0
Aqui está a versão maior com uso de amostra :
fonte
solve
, removendo muitos espaços em branco (eu sei que é significativo, mas em muitos lugares isso pode ser removido), usando símbolos em vez de palavras (como em!=
vez deisnt
), usando recuo em vez dethen
palavra-chave, substituindo[0...9]
por[0..8]
.Clojure - 480 bytes
O tamanho explodiu, mas pelo menos é um número bonito. Eu acho que poderia ser melhorado muito usando apenas 1D-vetor. De qualquer forma, o caso de teste leva um pouco menos de quatro segundos no meu laptop. Eu pensei que seria apropriado definir uma função, pois é uma linguagem funcional, afinal.
Exemplos:
Uma versão levemente não-gasta (e mais bonita):
fonte
PowerShell ,
244242218215 bytesExperimente online!
O script encontra todas as soluções para um sudoku.
Desenrolado:
Casos de teste:
fonte
D (322 caracteres)
Para cada quadrado não resolvido, ele cria uma matriz de opções disponíveis e, em seguida, faz um loop sobre ele.
com espaço em branco:
fonte
Perl (195 caracteres)
Todo o crédito é do criador aqui , e a explicação também pode ser encontrada lá.
fonte
J, 94 bytes
Funciona exatamente da mesma maneira que a versão K, ou seja, com um BFS (para que ele produza todas as soluções). Ele imprime espaços entre os dígitos de saída, mas o programa K também. Não estou contando "s =:", pois isso está apenas nomeando a função (assim como eu não contaria o nome do arquivo em outro idioma).
fonte