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

 (dfns.dyalog.com)
1 pontos por GN⁺ 2024-10-07 | 1 comentários | Compartilhar no WhatsApp
  • Em Dyalog APL, sudoku retorna todas as matrizes de solução possíveis a partir de uma matriz de puzzle com 0 nas células vazias, e implementa o mesmo problema de várias formas no estilo APL/K
  • O alvo padrão é o Sudoku 9×9, em que cada bloco 3×3, linha e coluna deve conter os números de 1 a 9 sem repetição
  • A entrada prob contém 1-9 nas células preenchidas e 0 nas vazias, e o argumento esquerdo opcional shape também permite especificar blocos não quadrados como 2×3 e 3×4
  • O algoritmo de solução de Veli-Matti Jantunen vetoriza a matriz, cria índices de linhas, colunas e blocos, reduz os candidatos e expande primeiro a partir do grupo mais restritivo
  • Os exemplos s33 e s22 têm 3 soluções cada, e 3 4 sudoku s34 tem 2 soluções; junto deles são apresentados o one-liner em K 5 de Arthur Whitney e várias reimplementações em APL

Entrada de Sudoku e resultado da função sudoku

  • Um puzzle de Sudoku é uma grade em que blocos 3×3 são dispostos em uma matriz 3×3, e cada célula está vazia ou contém um número de 1 a 9
  • A solução deve satisfazer as três restrições de não repetição
    • Cada bloco 3×3 deve conter os números de 1 a 9 sem repetição
    • Cada linha de 9 células deve conter os números de 1 a 9 sem repetição
    • Cada coluna de 9 células deve conter os números de 1 a 9 sem repetição
  • A matriz prob usa os números 1-9 nas células preenchidas e 0 nas vazias
  • O argumento esquerdo opcional shape especifica o formato dos blocos quando o puzzle não usa o padrão quadrado
    • Em uma matriz 6×6 com subáreas 2×3, a chamada tem a forma 2 3 sudoku mat
  • O resultado é um vetor contendo todas as matrizes de solução
    • Se não houver solução, retorna ⍬
    • Situações de erro podem ser indicadas por ''; a documentação diz que isso seria “algo que não deveria acontecer, mas pode ocorrer quando há um número absurdamente grande de resultados”

Fluxo da solução de Veli-Matti Jantunen

  • O algoritmo trata a matriz de Sudoku como um vetor e representa linha, coluna e região de Sudoku com vetores de índice
  • Depois de passar nas verificações básicas, ele examina uma alternativa por vez na lista de candidatos
  • Em cada etapa, filtra os elementos possíveis de todas as células
    • Se existir ao menos uma célula sem valor possível, o candidato a solução é descartado
    • Se uma célula tiver dois ou mais números candidatos, ele escolhe uma célula no grupo mais restritivo e adiciona à lista as combinações candidatas dessa célula
    • Se todas as células ficarem com apenas um número, isso é tratado como solução e o algoritmo passa ao próximo candidato
  • Na mesma seção também há a função Shuffle, que embaralha uma tabela de Sudoku existente em outra tabela

O one-liner de Arthur Whitney e implementações alternativas

  • A implementação alternativa de sudoku por David Crossley recebe como entrada uma configuração N×N e considera os casos em que o tamanho do bloco N*÷2 é inteiro
    • A entrada deve ser uma disposição válida em que algumas células contêm números de 1 a N e o restante é 0
    • Cada linha, coluna e bloco deve conter todos os números de 1 a N no resultado
    • A implementação inclui funções auxiliares como valid, search, rules, sole, singles, uniques, matches, NinN e setup
  • A solução de Arthur Whitney em K 5 é apresentada como código de uma linha
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last fornece uma implementação de sudoku que transpõe o código de Whitney para uma D-function
  • A reescrita de Morten Kromberg define explicitamente alguns componentes de K, adotando uma forma mais próxima da original
    • Como a versão em K, ela recebe e retorna um vetor de 81 elementos, e não uma matriz
  • A implementação Sudoku de Roger Hui é mais generalizada e também lida com puzzles não quadrados
    • svec cria o vetor de solução, e pvex e pvec expandem as disposições possíveis
    • avl produz a lista de números possíveis, e emt encontra os índices de linha e coluna das células vazias
    • rcb, box, cmap e CMAP constroem as relações de conflito entre linhas, colunas e blocos

Puzzles de exemplo e número de soluções

  • s33 é um problema de exemplo 9×9, e o resultado de sudoku s33 tem 3 soluções
  • A função sbox divide os blocos internos e mostra a grade de Sudoku de forma mais legível
    • 0 é exibido como ponto (·)
    • A saída é uma matriz de caracteres com os limites dos blocos desenhados
  • s22 é um problema de exemplo 4×4, e o resultado de sbox¨ sudoku s22 tem 3 soluções
  • s34 é um problema de exemplo com blocos 3×4
    • 3 4 sbox s34 mostra o problema com a divisão dos blocos
    • O resultado de 3 4 sudoku s34 tem 2 soluções

Links de referência e itens relacionados

Leituras relacionadas

1 comentários

 
GN⁺ 2024-10-07
Comentários do Hacker News

  • Essa linha foi escrita em K. K é uma linguagem criada por Arthur Whitney com base em APL e Scheme
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • Às vezes estimo a complexidade do código comparando a quantidade de linhas com a saída abaixo
    tar -cf - . | gzip | base64 | wc -l
    Ou seja, é como olhar “quão bem ele comprime?”. Quando vejo APL, lembro de quando você manda por engano a saída do gzip para o terminal
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    É impressionante que haja gente que vá acompanhando um código desses e ainda pergunte “consegue achar o bug?”. Parece dados binários compactados em que todo mundo já tem o mesmo dicionário

    • Tenho uma curiosidade sincera sobre como programadores APL encaram manutenibilidade e legibilidade. Imagino se eles comentam o código com muito cuidado ou mantêm documentação separada
    • Se a pergunta é “consegue achar o bug?”, algumas coisas aparecem de cara. Há erros de sintaxe, como uma aspa simples sem fechamento e um ∘ sem operando à direita, e n n←⍴⍵ parece sinalizar que ⍵ é esperado como bidimensional, já que define n duas vezes, mas dependendo da intenção _ n←⍴⍵ ou n←⊃⌽⍴⍵ seriam mais naturais
      Além disso, ⊥ dá erro se ⍴⍵ não for um único inteiro ou um vetor vazio, então no fim não é diferente de n←⍴⍵, o que só confunde mais. Várias vírgulas redundantes e ↑⍵ também poderiam ser removidos, e a expressão inteira fica praticamente igual a p←(n+1)⍴⊂⍳n×n←⍴⍵, uma estrutura que devolve n+1 vetores 1..n²
      Apesar da aparência estranha, depois que você aprende os símbolos e as operações básicas, APL é surpreendentemente direto. Só que leva tempo para ficar fluente, e quando você chega a esse ponto parece um superpoder
    • Considerando que há bilhões de pessoas que leem e escrevem caracteres que não são ingleses, não sei se o fato de existir gente que lê APL é algo tão especial ou surpreendente assim

  • É verdade que os defensores da linguagem enfatizam velocidade, facilidade para processamento de arrays e uma sintaxe expressiva
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • Só não sei se manutenibilidade também entra como vantagem

  • Contagem de linhas de código é uma métrica ruim, porque cada linguagem usa linhas de um jeito diferente
    Uma medida melhor poderia ser contar o número de nós da árvore sintática com base em símbolos não terminais significativos, como “constante” ou “chamada de função”. Melhor ainda se também fossem considerados a profundidade dessa árvore e seu fator de ramificação

    • Não consigo concordar com a ideia simplista de que só a semântica importa. A experiência de uso da linguagem, a clareza, o modo de pensar e a expressividade também importam, e o tamanho visual do código influencia isso
      Uma solução em uma linha ocupa pouquíssimo espaço na tela, o que é uma grande vantagem ao lidar com problemas complexos. Mover os olhos dentro da tela é bem menos custoso do que alternar entre arquivos e rolar a página, e a carga cognitiva importa
      Mesmo sem conhecer K, quando as constantes aparecem lado a lado parece que se está usando uma representação direta dos dados do problema. Se a cultura de K incentiva esse tipo de código e inclina o pensamento para a diretividade e a simplicidade, eu gostaria de trazer esse molho especial para a equipe
    • Funções embutidas e APIs de bibliotecas do sistema estragam esse tipo de métrica. Por exemplo, HQ9+ se sai muito bem pelo menos para imprimir “Hello, world!”
      https://cliffle.com/esoterica/hq9plus/
    • A métrica preferida para medir quantidade de informação é simplesmente o número de bits, como na teoria da informação algorítmica
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • Esse one-liner claramente foi feito como brincadeira, e ninguém está defendendo racionalmente que ele seja um código fácil de ler. Discutir definições aqui é perder o ponto. A questão é que “em K é possível escrever código extremamente denso”

  • Muitas vezes me perguntei se usar linguagens como APL/K realmente permite que o programador pense no problema de forma mais eficiente

    • Como programador de kdb+/Q, acho que depende do tipo de problema. Ao lidar com arrays de dados, é sem dúvida mais fácil pensar e escrever avg a+b para somar dois arrays e depois tirar a média
      Em uma linguagem que não seja centrada em arrays, provavelmente seriam necessárias verificações de limites, um grande loop for e variáveis temporárias para guardar soma e contagem. A diferença é que algo que em uma linguagem como C daria algo como 6 linhas, em Q se resolve em 6 caracteres
      Dito isso, toda linguagem tem recursos que ajudam a raciocinar melhor sobre determinados problemas. Linguagens funcionais com tipos algébricos de dados e pattern matching, como OCaml ou F#, são melhores que um grande switch ou if-else-if, e linguagens com açúcar sintático como async/await são vantajosas para lidar com concorrência
    • Em classes de problemas que são facilmente vetorizáveis, linguagens centradas em arrays tornam o raciocínio e a solução mais eficientes. Isso porque permitem abstrair os detalhes de estruturas de dados e iteração
      Quando eu trabalhava como quant, usei bastante kdb+/q por mais de 5 anos em estratégias de média frequência, mas quando migrei para trading de alta frequência que não era fácil nem eficiente de vetorizar, como cálculos de livro de ofertas, continuar usando uma linguagem centrada em arrays passou, na verdade, a complicar o raciocínio sobre o problema
    • Em uma apresentação sobre Dyalog, uma linguagem moderna da família APL, ouvi a afirmação de que essa notação facilita reconhecer certos idiomas
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      Esse trecho estava no contexto de compiladores, mas a apresentação como um todo trata Dyalog e APL como sistemas de notação matemática. O fluxo central é que otimizar expressões matemáticas pode ser mais fácil do que otimizar código comum
    • Hillel Wayne trata desse tema de vez em quando na newsletter dele. Fiquei convencido de que ele realmente pensa melhor em alguns problemas usando linguagens de array, mas ainda não consigo imaginar bem como é essa experiência
    • O lado bom do estilo das linguagens de array é que, ao discutir variações de algoritmos, os trechos de código relevantes têm poucos caracteres e cabem diretamente no texto. Em linguagens tradicionais verticais, que exigem várias ou dezenas de linhas para dizer a mesma coisa, é preciso ficar alternando entre blocos de código e explicações

  • Uma das coisas mais importantes aqui é que o gerador de problemas no topo é muito claro. Essa é a diferença entre as linguagens de notação ao estilo Iverson, incluindo J e K, e outras linguagens
    Ele não tem a elegância e a força da solução em uma linha, mas é bem limpo e compreensível mesmo sem comentários rigorosos. Ainda assim, acho que lamp não é um bom símbolo de comentário
    A solução em uma linha é impressionante, e a programação tácita é incrivelmente fascinante. A ideia de usar a compressão singular das linguagens baseadas em glifos para descrever e executar programação funcional, e então aplicar isso novamente a arrays inteiros, é genial
    https://www.jsoftware.com/papers/fork.htm

    • Só porque dá para escrever tudo em uma linha sem espaços não quer dizer que você deva fazer isso
      Claro que, se você remover essa capacidade, pode forçar as pessoas a escrever código mais verboso, mas isso reduz muito o ponto forte delas como ferramentas interativas. Linguagens ao estilo Iverson conseguem escrever código muito curto, o que é útil para trabalho interativo. Nesse caso, o código nem chega a ser salvo, então é de fato código write-only
      Ao escrever código que vai para um arquivo, você escolhe o estilo que quiser; nesse caso, recomendo escrever de forma menos comprimida. Ainda assim, mesmo em um estilo verboso, linguagens ao estilo Iverson oferecem código muito mais curto do que a maioria das linguagens

  • A maioria das pessoas se afasta por causa dos símbolos, mas esse não foi o meu problema
    Gosto de APL e de linguagens de array, e o que aprendi me ajudou muito também ao usar outras linguagens. Mas elas não viraram minhas ferramentas do dia a dia; não por causa dos símbolos, e sim porque, depois de mexer nelas de forma esporádica por uns 3 ou 4 anos, esbarrei em uma barreira que não consegui superar
    Em outras linguagens, geralmente existe uma abordagem geral para ir resolvendo um problema, ainda que de forma aproximada, e depois, quando você encontra o “truque” daquele problema, pode refatorar para algo mais elegante e eficiente. Em APL, pareceu que não havia esse desvio provisório: ou você conhece o truque, ou não conhece
    Não sei bem se isso é realmente assim, se ao aprender truques suficientes você desenvolve uma intuição para resolver problemas, se no fim tudo continua sendo só uma coleção de truques, ou se eu simplesmente não li algum documento essencial de estratégia

    • Essa sensação não está errada. É muito fácil ficar com essa impressão ao aprender linguagens de array. Alguém experiente pode olhar para um problema e dizer “por que resolveu de um jeito tão complicado, era só usar ⍸⍣¯1?”, mas é bem possível que ninguém jamais tenha explicado que ⍸ tem uma operação inversa nem como usá-la
      Mesmo usando essas linguagens há anos, ainda acho um pouco intimidadoras algumas paredes de código que programadores de array produzem. Entendo por que escrevem assim, mas, pessoalmente, prefiro que o código tenha um pouco de espaço em branco
      Estou criando uma linguagem de array baseada em APL, e uma das metas iniciais foi tornar o estilo imperativo um cidadão de primeira classe, sem punir iniciantes que usam coisas como instruções if. Vejo esse estilo como algo mais ou menos no meio do caminho entre o estilo APL puro e linguagens imperativas comuns
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • A barreira de que você falou é um problema real nos caminhos atuais de entrada em APL. Fiz uma palestra exatamente sobre esse tema no ano passado, e definitivamente não é culpa individual
      Mas também não é uma limitação da linguagem em si. Na minha experiência, o processo de atravessar essa barreira foi justamente o momento em que o paradigma começou a se encaixar. Só depois de passar cerca de 500 horas hackeando, ao longo de um ano, em um protótipo de parser de YAML é que as peças começaram a fazer sentido
      O essencial parece ser uma combinação de princípios de design orientado a dados, formas concretas de aplicar as características iversonianas de uma boa notação à arquitetura de software, e familiaridade com idiomas e com a maneira como eles expressam conceitos do domínio
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • Há um vídeo sobre este tema
    https://www.youtube.com/watch?v=DmT80OseAGs
    A solução pode ser testada diretamente em https://tryapl.org/

  • Pode ser interessante comparar essa linha única com soluções de code golf em várias linguagens de programação
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • Curiosamente, a solução em primeiro lugar para um problema específico — resolver Sudoku por força bruta — é justamente um trecho em K. A segunda colocada é uma solução em J feita a partir da solução em K
      https://codegolf.stackexchange.com/a/5030