Artículo Original
Publicado 2006-05-17
Palabras clave
- máquinas de Turing,
- clases de complejidad,
- algoritmos eficientes,
- costos computacionales
Cómo citar
Montoya, J. A. (2006). La dificultad de jugar sudoku. Revista Integración, Temas De matemáticas, 24(1), 1–15. Recuperado a partir de https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/249
Resumen
Se prueba que el juego sudoku es NP–completo, si se consideran tableros de tamaño n2 para todo número natural n. Esto explica, en parte, por qué es que resulta tan difícil jugar sudoku.
Descargas
Los datos de descargas todavía no están disponibles.
Referencias
[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.