RESOLVENDO SUDOKUS GENERALIZADOS ATRAVÉS DE ALGORITMOS DE BACKTRACKING E DE DANCING LINKS

Allan Cruz; João Dallyson de S. Almeida; Pamela Cruz

Autores

Allan Cruz Universidade Federal do Maranhão
João Dallyson de S. Almeida Universidade Federal do Maranhão
Pamela Cruz Universidade de Coimbra

Palavras-chave:

Sudoku, Backtracking, Dancing Links, Algoritimo

Resumo

Este trabalho apresenta uma implementação da resolução de sudokus generalizados através de algoritmos de backtracking e Dancing Links. Foram implementados dois algoritmos, um utilizando a técnica de backtracking e outro utilizando a técnica de Dancing Links. Os algoritmos foram testados em diferentes tamanhos de sudoku (9x9, 16x16 e 25x25) e o tempo de execução foi medido. Os resultados mostraram que o algoritmo de Dancing Links é mais eficiente que o algoritmo de backtracking para a resolução de sudokus generalizados.

Referências

ABULUAIH, S. et al. Fog of Search Resolver for Minimum Remaining Values Strategic Colouring of Graph. International Conference on Soft Computing in Data Science. Anais...Springer, 2018.

COSTA, O. DA. A matemática recreativa no ensino Básico. PhD Thesis—[s.l: s.n.].

COTA, A. C. DA S. Euler e os números pentagonais. Master’s Thesis—[s.l.] Universidade Federal do Rio Grande do Norte, 2011.

DITTRICH, M.; PREUSSER, T. B.; SPALLEK, R. G. Solving Sudokus through an Incidence Matrix on an FPGA. 2010 International Conference on Field-Programmable Technology. Anais...IEEE, 2010.

DREAMSTIME. Sudoku com solução livra para usar se. , 2018. Disponível em: <https://pt.dreamstime.com/fotos-de-stock-royalty-free-sudoku-com-solução-livra-para-usar-se-image9264088>

FELGENHAUER, B.; JARVIS, F. Mathematics of Sudoku I. 2006.

FISCHER, T. A necessary solution condition for Sudoku. arXiv preprint arXiv:1210.6343, 2012.

GUNTHER, J.; MOON, T. Entropy minimization for solving Sudoku. IEEE transactions on signal processing, v. 60, n. 1, p. 508–513, 2011.

HARRYSSON, M.; LAESTANDER, H. Solving sudoku efficiently with dancing links. , 2014.

HAYNES, I. W. Analysis of generalized sudoku puzzles: A mixture of discrete techniques. PhD Thesis—[s.l.] University of South Carolina, 2008.

KAPANOWSKI, A. Python for education: the exact cover problem. arXiv preprint arXiv:1010.5890, 2010.

KNUTH, D. E. Dancing links. arXiv, , 2000. Disponível em: <http://arxiv.org/abs/cs/0011047>. Acesso em: 10 jul. 2022

MAIA, P. A. DE A. Jogos na aprendizagem matemática: Uma proposta com Sudokus, Malba Tahan e Tangram. 2012.

MAJI, A. K.; PAL, R. K. Sudoku solver using minigrid based backtracking. 2014 IEEE International Advance Computing Conference (IACC). Anais...IEEE, 2014.

MCKAY, B. D.; WANLESS, I. M. On the Number of Latin Squares. Annals of Combinatorics, v. 9, n. 3, p. 335–344, 2005.

NOGUEIRA, R. Quadrados mágicos. Ciência de Garagem, 2015. Disponível em: <https://cienciadegaragem.blogspot.com/2015/09/quadrados-magicos.html>. Acesso em: 10 jul. 2022

RAI, D.; INGLE, M.; CHAUDHARI, N. POLYNOMIAL 3-SAT REDUCTION OF SUDOKU PUZZLE. International Journal of Advanced Research in Computer Science, v. 9, n. 3, 2018.

RUSSELL, P. N. Artificial Intelligence: A Modern Approach by Stuart. Russell and Peter Norvig contributing writers, Ernest Davis...[et al.], 2010.

SCHMIDL, D. et al. Suitability of Performance Tools for OpenMP Task-Parallel Programs. Em: KNÜPFER, A. et al. (Eds.). Tools for High Performance Computing 2013. Cham: Springer International Publishing, 2014. p. 25–37.

SIMONIS, H. Sudoku as a constraint problem. CP Workshop on modeling and reformulating Constraint Satisfaction Problems. Anais...Citeseer, 2005.

SKIENA, S. The Algorithm Design Manual. Springer Publishing Company. Incorporated, , 2008.

TAKANO, K.; DE FREITAS, R.; DE SÁ, V. G. P. O jogo de lógica Sudoku: modelagem teórica, NP-completude, algoritmos e heurısticas. XXXIV Concurso de Trabalhos de Iniciação Científica da Sociedade Brasileira de Computação, 2015.

TSAO, H. EVOLUTIONARY MATHEMATICS AND ARTS FOR TALK ELEGANCY INVESTIGATION. Evolutionary Progress in Science, Technology, Engineering, Arts, and Mathematics (STEAM), p. 1–68, 2019.

VIDEL, M.; PALO, M. Scaling of popular Sudoku solving algorithms. , 2014.

YILDIRIM, H.; KRISHNAMOORTHY, M.; DEO, N. A study of the Sudoku graph family. Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. Anais...2008.