Visite também: Currículo ·  Efetividade BR-Mac

O que é LinuxDownload LinuxApostila LinuxEnviar notícia


Um resolvedor automático de Sudoku – em AWK

Sou fã declarado da linguagem AWK e tenho meu próprio artigo de introdução à linguagem, publicado em 2001, para comprovar. Admito que gostaria de ser faixa-preta em Python, Ruby, Perl ou alguma outra linguagem com um ecossistema mais completo e que me permitisse manipular e gerar fluxos de texto com um pouco mais de estruturação e apoiado por bibliotecas de funções mais poderosas, mas o fato é que não sou, e que o AWK vem me atendendo, ano após ano, mesmo sem dispor de tudo o mais que estas outras linguagens me ofereceriam.

E como todo admirador, acabo achando graça em coisas feitas em AWK que não me chamariam a atenção se fossem em outras linguagens. É o caso deste resolvedor de Sudoku em AWK, por exemplo.

Resolver o popular quebra-cabeças é um bom passatempo para bastante gente que conheço, mas a mim nunca encantou. Já a idéia de implementar um algoritmo (suficientemente simples) que o resolva me seduz bem mais, e o fato de já haver diversas implementações (será que o Aurélio já fez um em SED?) não me desmotiva ;-)

No caso deste “Sudoku Solver” em AWK, implementado de forma elegante e razoavelmente bem documentado no próprio código, a entrada e a saída dos dados ocorrem em um formato que lembra um pouco o século passado, mas a lógica seguida é bem interessante, embora a linguagem seja admitidamente datada.

Vale mais pela curiosidade do que pela funcionalidade, mas se você estava em busca de um algoritmo para praticar algo em sua linguagem preferida, fica a dica para o caso de chover muito no final de semana ;-)


• Publicado por Augusto Campos em 2010-01-15

Comentários dos leitores

Os comentários são responsabilidade de seus autores, e não são analisados ou aprovados pelo BR-Linux. Leia os Termos de uso do BR-Linux.

    chuck (usuário não registrado) em 15/01/2010 às 5:25 pm

    eu já criei um sudoku.py com qt.

    Mas ficou tão bagunçado que tenho até vergonha de disponibilizar

    Ian Liu Rodrigues (usuário não registrado) em 15/01/2010 às 9:49 pm

    As vezes, quanto mais se joga, mais base se tem para criar um algoritmo eficiente ;-)
    Se não me engano o Sudoku se enquadra nos problemas NP-Completos (ou melhor, o n-Sudoku), então um outro desafio interessante é criar um algoritmo que resolve o tabuleiro com NxN casas.

    Fabio (usuário não registrado) em 16/01/2010 às 8:31 pm

    Segue minha versão de resolvedor em Python:

    http://tecnocom.blogspot.com/2009/12/resolvendo-sudoku-em-python.html

    Silveira Neto (usuário não registrado) em 17/01/2010 às 8:46 am

    Só um nota, sudoku é um problema não polinomial, pro tamanho de entrada do sudoku o tempo de computação cresce exponencialmente. Mesmo o melhor algoritmo de Sudoku não resolveria qualquer Sudoku em tempo polinomial (um tempo que você pode esperar). Mas dá pra resolver esses Sudoku normais de 9×9 e menores num tempo razoável.

    Também não é só uma questão de achar um algoritmo melhor. Como ele é um problema np-Completo [2] , o problema 3SAT [3] pode ser reduzido num problema de Sudoku. Um algoritmo polinomial pro Sudoku seria também um algoritmo polinomial pro 3Sat e portanto também pra toda a classe de problemas NP.

    De toda forma, eu não vejo graça em jogar sudoku. =P

    [1] Matemática do Sudoku: http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

    [2] Artigo de 2002 que provou que Sudoku era NP-Completo: http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf

    [3] Boolean satisfiability problem http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

Este post é antigo (2010-01-15) e foi arquivado. O envio de novos comentários a este post já expirou.