Research and Innovation Articles
Published 2006-05-17
Keywords
- máquinas de Turing,
- clases de complejidad,
- algoritmos eficientes,
- costos computacionales
How to Cite
Montoya, J. A. (2006). La dificultad de jugar sudoku. Revista Integración, Temas De matemáticas, 24(1), 1–15. Retrieved from https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/249
Abstract
It is proven that the play sudoku is NP–complete, if the size of boards are considered to be n 2 for every natural number n. This partly explains why it is difficult to play sudoku.
Downloads
Download data is not yet available.
References
[1]Colbourn C.“The complexity of completing partial latin squares”.DiscreteApplied Mathematics,8(1984), 151–158.
[2]Cook S.“The complexity of theorem proving procedures”.Proceedings, ACMSymposium on Theory of Computing, (1971), 151–158
.[3]Papadimitriou C. H.Computational Complexity.Addison-Wesley, 1994.
[2]Cook S.“The complexity of theorem proving procedures”.Proceedings, ACMSymposium on Theory of Computing, (1971), 151–158
.[3]Papadimitriou C. H.Computational Complexity.Addison-Wesley, 1994.