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 ;-)
@brlinuxblog
Feed RSS
eu já criei um sudoku.py com qt.
Mas ficou tão bagunçado que tenho até vergonha de disponibilizar
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.
Segue minha versão de resolvedor em Python:
http://tecnocom.blogspot.com/2009/12/resolvendo-sudoku-em-python.html
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