O solucionador de Sudoku em uma linha de Arthur Whitney (2011)

Algoritmo de resolução de Sudoku

• Explicação do problema de Sudoku

  • O quebra-cabeça Sudoku é composto por caixas 3×3 em uma grade 3×3, e cada célula está vazia ou contém um número de 1 a 9.
  • Cada caixa 3×3, cada uma das 9 linhas e cada uma das 9 colunas deve conter os 9 números sem repetição.
  • São fornecidos um problema de exemplo e um método de resolução.

• Visão geral do algoritmo

  • A matriz é tratada como vetor, e linhas, colunas e regiões do Sudoku são representadas por vetores de índice.
  • Realiza verificações básicas do quebra-cabeça e encontra a solução filtrando os elementos possíveis.
  • Se uma célula estiver vazia, avança para a próxima lista; se uma célula contiver vários números, escolhe a partir do grupo mais restrito e adiciona à lista.
  • Quando todas as células contêm um único número, a solução foi encontrada.

• Notas técnicas

  • Solução fornecida por Veli-Matti Jantunen, com a possibilidade de usar ⍺ para representar retângulos de Sudoku.
  • O resultado retorna um vetor com todas as soluções, ⍬ se não houver nenhuma, e '' se houver erro.
  • O algoritmo é simples: trata a matriz como vetor e encontra a solução filtrando os elementos possíveis.

• Outras abordagens

  • São apresentados códigos alternativos de David Crossley e Arthur Whitney.
  • São descritos diferentes estilos de código e abordagens.

• Exemplos e uso

  • São fornecidos vários exemplos de resolução de problemas de Sudoku.
  • Também é fornecida uma função para separar as caixas internas e facilitar a leitura do problema.

Resumo do GN⁺

• São apresentados vários algoritmos e estilos de código para resolver Sudoku.
• O quebra-cabeça Sudoku é útil para desenvolver raciocínio lógico e capacidade de resolução de problemas.
• Diferentes abordagens podem aumentar a flexibilidade na resolução de problemas.
• Como quebra-cabeças com funcionalidades semelhantes ao Sudoku, são recomendados Kakuro e KenKen.

[GN⁺]

Comentários do Hacker News

• K é uma linguagem criada por Arthur Whitney com base em APL e Scheme, com ênfase em velocidade, capacidade de processamento de arrays e uma gramática expressiva
• Ao medir a complexidade do código, compara-se o número de linhas de código e o grau de compactação
  • O código em APL parece dados binários compactados, e há admiração por quem consegue entendê-lo
• Linhas de código não são uma boa métrica, porque cada linguagem as utiliza de forma diferente
  • Considerar o número de nós da árvore sintática, a profundidade e os fatores de ramificação é um método melhor de medição
• A clareza do problema é importante, e linguagens iversonianas (incluindo J e K) se diferenciam de outras linguagens
  • Soluções de uma linha são surpreendentes e úteis para descrever e executar arrays com eficiência
• Há quem ache que programas em K deveriam terminar com QED, e se pergunta sobre a relação com a KQED
  • A KQED é uma afiliada da PBS na Bay Area
• Há curiosidade sobre se linguagens como APL/k ajudam a pensar sobre problemas de forma mais eficiente
• Aprender APL e linguagens de arrays ajudou com outras linguagens, mas acabou não sendo algo usado no dia a dia
  • Em APL, se você não souber um método específico de resolver certo problema, fica difícil resolvê-lo
• Existem soluções melhores do que algumas soluções ineficientes vistas em certos handbooks de design de algoritmos
  • Em 2015, foi escrito um post de blog sobre isso
• A solução de Sudoku com Scryer Prolog é fácil de ler e poderosa, com excelente capacidade de resolução por restrições
  • Scryer Prolog é um Prolog moderno, compatível com ISO e com ótimo desempenho