Voltar
Artigo Acesso aberto Produção Nacional
BIBTEX RIS

Metaheurísticas simulated annealing e busca tabu aplicadas na resolução do quebra-cabeça sudoku

2013; Linguagem: Português

10.5540/03.2013.001.01.0064

ISSN

2359-0793

Autores

Simone Silva Frutuoso de Souza, Rubén Romero,

Tópico(s)

graph theory and CDMA systems

Resumo

O quebra-cabeça Sudoku é considerado um problema NP-difícil, e por este fato desperta a atenção de pesquisadores. É um jogo muito popular, jogado por milhões de pessoas, sendo de difícil resolução dependendo das condições inicias do quebra-cabeça. Neste artigo apresentam-se duas metodologias para resolver o quebra-cabeça Sudoku: as metaheurísticas Simulated Annealing e Busca Tabu. Os algoritmos foram desenvolvidos na linguagem C++ Builder 6.0, utilizando interface gráfica. Para evidenciar a eficácia destas metodologias foram realizados vários testes, sendo possível comprovar que as metodologias encontram a solução ótima para diferentes níveis de dificuldade: fácil, médio, difícil (sudoku com dimensão 3x3) e super-sudoku (sudoku com dimensão 4x4) para o quebra-cabeça sudoku.

Referência(s)