Revista Integración, temas de matemáticas.
Vol. 24 Núm. 1 (2006): Revista Integración, temas de matemáticas
Artículos científicos

La dificultad de jugar sudoku

J. Andrés Montoya
Escuela de Matemáticas, Universidad Industrial de Santander, Bucaramanga, Colombia.

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.