La dificultad de jugar sudoku

Abstract

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.

Keywords

• máquinas de Turing
• clases de complejidad
• algoritmos eficientes
• costos computacionales