UTILIZANDO METAHEURÍSTICAS PARA RESOLVER O QUEBRA-CABEÇA SUDOKU

Autores

  • Simone Silva Frutuoso de Souza UNEMAT

DOI:

https://doi.org/10.36557/pbpc.v4i2.384

Palavras-chave:

Metaheurística, Sudoku, Otimização, Simulated Annealing, Busca Tabu

Resumo

O quebra-cabeça Sudoku é considerado um problema NP-completo, e por este fato desperta a atenção de pesquisadores. É um jogo muito popular, jogado por milhões de pessoas, apesar de ser difícil de resolver dependendo das condições inicias do quebra-cabeça. Neste artigo apresentam-se duas metodologias para resolver o quebra-cabeça Sudoku, isto é, as Metaheurísticas Simulated Annealing e Busca Tabu. Os algoritmos foram desenvolvidos na linguagem C++. Para evidenciar a eficácia destas metodologias foram realizados vários testes e foi possível comprovar que com as metodologias podem ser encontradas as soluções ótimas de diferentes níveis de dificuldade e dimensão do quebra-cabeça.

Downloads

Não há dados estatísticos.

Referências

Babu, P. Pelckmans, K. and Stoica, P. (2010). Linear Systems, sparse solutions, and Sudoku. IEEE Signal Processing Letters, Vol. 17. Pg. 40-43.

Bartlett , A. and Langville, A. (2008). An integer programming model for the Sudoku problem. Online Math. Applicat., vol. 8.

Davis, T. (2010). The mathematics of Sudoku. Disponível em: http://www.geometer.org/mathcircles/sudoku.pdf.

Delahaye Jean-Paul. “The science behind Sudoku”. Scientific American. 2006. Pg. 80-87.

Gallego, R. R. A.; Escobar, Z. A. e Romero, R. "Técnicas de Optimización Combinatorial", Primera edición. grupo de Investigación en Planeamiento de Sistemas Eléctricos. Universidad Tecnológica de Pereira. Pereira abril de 2006.

Glover, F. (1986) “Future Paths for integer Programming and Links to artificial inteligence” Computers and Operations Research, Vol. 13, Nº 5, pg. 533-549.

Glover, F. and Laguna, M. (1993) “Tabu Search, Modern Heuristic Techniques for Combinatorial Problems”. Blackwell, Oxford, pg. 70–150.

Kirkpatrick, S.; Gelett, C. e Vechht, M. (1983). Optimization by simulated annealing. Science 4598, pg. 621-630.

Lewis, R. (2007). Metaheuristics can solve Sudoku puzzles, SpringerLink, Springer Science+Business Media, LLC 2007.

Majumder, A.; Kumar, A.; Das, N. and Chakraborty, N. (2010). The game of Sudoku-Advanced Backtrack approach. IJCNS – International Journal of Computer Science and Network Security, Vol. 10. Pg. 255-258.

Moon, T. K., Gunther, J. H. and Kupin, J. J. (2009) Sinkhorn Solves Sudoku, IEEE Transactions on Information Theory, Vol. 55, Nº 4, Pg. 1741-1746

Souza, M. J. F. (2010). Inteligência computacional para otimização. Notas de Aulas, Departamento de computação Universidade Federal de Ouro Preto. Acesso em 03/2012, Disponível em: http://www.iceb.ufop.br/prof/marcone.

Sudoku Essentials. (2012). Acessado em 04/2012 em: http://www.sudokuessentials.com/history-of-sudoku.html

Sudoku Made Easy. (2012). Acessado em 04/2012 em: http://www.sudokumadeeasy.com/history-of-sudoku/

Sudoku Science. (2006). A popular puzzle helps researchers dig into deep math. IEEE Spectrum, pg. 16-17.

Wikipédia. (2012). Enciclopédia Online. Acessado em 04/2012 em: http://en.wikipedia.org/wiki/Sudoku_algorithms.

Downloads

Publicado

2025-08-18

Como Citar

SILVA FRUTUOSO DE SOUZA, Simone. UTILIZANDO METAHEURÍSTICAS PARA RESOLVER O QUEBRA-CABEÇA SUDOKU . Periódicos Brasil. Pesquisa Científica, Macapá, Brasil, v. 4, n. 2, p. 251–268, 2025. DOI: 10.36557/pbpc.v4i2.384. Disponível em: https://periodicosbrasil.emnuvens.com.br/revista/article/view/384. Acesso em: 26 set. 2025.

Edição

v. 4 n. 2 (2025): Periódicos Brasil. Pesquisa Científica

Seção

Ciências Exatas e Engenharia

Licença

Copyright (c) 2025 Simone Silva Frutuoso de Souza

Creative Commons License
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.

Você tem o direito de:

  1. Compartilhar — copiar e redistribuir o material em qualquer suporte ou formato para qualquer fim, mesmo que comercial.
  2. Adaptar — remixar, transformar, e criar a partir do material para qualquer fim, mesmo que comercial.
  3. O licenciante não pode revogar estes direitos desde que você respeite os termos da licença.  

 

De acordo com os termos seguintes:

  1. Atribuição — Você deve dar o crédito apropriado , prover um link para a licença e indicar se mudanças foram feitas . Você deve fazê-lo em qualquer circunstância razoável, mas de nenhuma maneira que sugira que o licenciante apoia você ou o seu uso.
  2. Sem restrições adicionais — Você não pode aplicar termos jurídicos ou medidas de caráter tecnológico que restrinjam legalmente outros de fazerem algo que a licença permita.