UTILIZANDO METAHEURÍSTICAS PARA RESOLVER O QUEBRA-CABEÇA SUDOKU
DOI:
https://doi.org/10.36557/pbpc.v4i2.384Keywords:
Metaheuristic, Sudoku, Optimization, Simulated Annealing, Tabu SearchAbstract
The Sudoku puzzle is considered an NP-hard problem, and this fact caught the attention of researchers. It is a very popular game, played by millions of peoples, although it is difficult to solve depending on the initial conditions of the puzzle. This paper presents two methodologies to solve the Sudoku puzzle, i.e., metaheuristics Simulated Annealing and Tabu Search. The algorithms were developed in C++. To demonstrate the effectiveness of these methodologies were performed several tests and it was possible to prove that with the methodologies can found the optimal solution of different levels of difficulty and size of the puzzle.
Downloads
References
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
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Simone Silva Frutuoso de Souza
This work is licensed under a Creative Commons Attribution 4.0 International License.
Você tem o direito de:
- Compartilhar — copiar e redistribuir o material em qualquer suporte ou formato para qualquer fim, mesmo que comercial.
- Adaptar — remixar, transformar, e criar a partir do material para qualquer fim, mesmo que comercial.
- O licenciante não pode revogar estes direitos desde que você respeite os termos da licença.
De acordo com os termos seguintes:
- 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.
- 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.
