La dificultad de jugar sudoku

• Montoya, J. Andrés ^[1]
  1. [1] Universidad Industrial de Santander

     Universidad Industrial de Santander

     Colombia

     
• Localización: Integración: Temas de matemáticas, ISSN 0120-419X, Vol. 24, Nº. 1, 2006 (Ejemplar dedicado a: Revista Integración, temas de matemáticas), págs. 1-15
• Idioma: español
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

       

  • English

     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.

• Referencias bibliográficas
  • Citas [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.