Solucionador de Sudoku

[iziplay]

Escrever um solucionador Sudoku é algo que eu queria fazer há algum tempo, mas nunca tive tempo para isso. A ultima  pausa de férias entre o Natal e o Ano Novo, no entanto, me proporcionou a oportunidade perfeita.

 

O processo básico que uso para resolver quebra-cabeças é muito simples; não é nada mais complexo do que um algoritmo de rastreamento recursivo de força bruta. Como acontece com a maioria dos programas, escrever o código para a interface do usuário, para obter e retirar os dados e a verificação de erros, levou o dobro do tempo do código para calcular a solução!

Eu usei um algoritmo de rastreamento no blog antes, quando escrevi sobre labirintos . (https://datagenetics.com/blog/november22015/index.html)

 

Antes de começar, uma verificação referencial é realizada na grade de entrada para garantir que o quebra-cabeça esteja bem formado (verificando se não há conflito de dígitos em nenhuma linha, coluna ou caixa). Se houver conflitos, as células problemáticas serão marcadas em vermelho e o botão resolver será desabilitado.

Quando o botão solver é pressionado, a grade é escaneada, procurando por células em branco. Se não houver mais células em branco, temos uma solução!

Quando uma célula em branco é encontrada, eu crio uma matriz vetorial de todos os possíveis valores de dígitos candidatos que podem ser usados para esta célula. Isso é feito começando com todos os dígitos de 1 a 9 e, em seguida, removendo os candidatos com base na varredura da linha, coluna e grade dessa célula em busca de colisões. Eu itero por todos os candidatos ainda válidos, tentando cada um de volta e voltando ao problema procurando a próxima célula em branco.

O critério de sucesso é o preenchimento de cada quadrado em branco. A falha ocorre se não houver nenhum candidato possível que possa preencher o quadrado em branco no qual estamos trabalhando. Em caso de falha, redefinimos a célula atual para esvaziar e voltamos ao nível anterior para tentar o próximo caminho. Como dito acima, por questão de agilidade, paro ao encontrar a primeira solução ao invés de enumerá-las todas, mas seria uma simples mudança continuar e encontrar todas as soluções.

Como acontece com muitos algoritmos recursivos, há uma simplicidade agradável no código. A profundidade da recursão não é uma preocupação, pois, no máximo, a profundidade nunca excederá 81 níveis (em uma grade totalmente em branco), embora a árvore possa ficar larga. Outra coisa útil nessa implementação é que as alterações na matriz do quebra-cabeça podem ser feitas no local, em vez de ter que copiar e duplicar o quadro à medida que recursamos. É muito eficiente em termos de memória.

 

http://datagenetics.com/blog/january12019/b1p.png

 

 

Sem muita conversa vamos direto ao link da ferramenta

 

http://datagenetics.com/blog/january12019/index.html

 

Contatos para proposição de problemas  ou dúvidas

Nick@DataGenetics.com

[PARAFUSO]

....mas isso serve pra que exatamente ?

[iziplay]

15 horas atrás, PARAFUSO disse:

....mas isso serve pra que exatamente ?

O número de clusters de loteria únicos (grupos contendo todos os números de loteria, todos únicos) é gigantescamente maior do que o total possível de grades de Sudoku.
Logo usar as grades de Sudoku em loterias permite escolhas interessantes.

 

É usado em loterias pick 3, pick 4, pick 5 e demais loterias com até 10 saidas por sorteio. É utilizado de forma inventiva em varios países.

 

Usa-se o digito final dos sorteios de 1 a 9, quando for unidade final = 0 usar o espelho 5

 

+--+--+--++--+--+--++--+--+--+-+
| 6 | 7 | 9 || 3 | 2 | 8 || 4 | 1 | 5 |
+--+--+--++--+--+--++--+--+--+-+
| 4 | 2 | 5 || 6 | 1 | 7 || 8 | 3 | 9 |
+--+--+--++--+--+--++--+--+--+-+
| 1 | 3 | 8 || 5 | 4 | 9 || 2 | 6 | 7 |
+--+--+--++--+--+--++--+--+--+-+

+--+--+--++--+--+--++--+--+--+-+
| 5 | 8 | 2 || 7 | 3 | 1 || 6 | 9 | 4 |
+--+--+--++--+--+--++--+--+--+-+
| 9 | 4 | 6 || 8 | 5 | 2 || 1 | 7 | 3 |
+--+--+--++--+--+--++--+--+--+-+
| 3 | 1 | 7 || 9 | 6 | 4 || 5 | 2 | 8 |
+--+--+--++--+--+--++--+--+--+-+

+--+--+--++--+--+--++--+--+--+-+
| 7 | 6 | 1 || 4 | 9 | 5 || 3 | 8 | 2 |
+--+--+--++--+--+--++--+--+--+-+
| 2 | 9 | 4 || 1 | 8 | 3 || 7 | 5 | 6 |
+--+--+--++--+--+--++--+--+--+-+
| 8 | 5 | 3 || 2 | 7 | 6 || 9 | 4 | 1 |