Sobre el problema de las N-reinas
Hay una diferencia entre el problema de las N-reinas (poner N reinas en un tablero NxN sin que se maten) y el problema de Completar N-reinas (algunas reinas están colocadas y hay que poner el resto, si es posible).
Recientemente se ha demostrado que Completar N-reinas es NP-completo (ver artículo), eso quiere decir que resolverlo en tiempo polinómico supondría el premio del millón de dólares del instituto Clay
No hay que confundir los dos problemas, por lo visto es lo que ha ocurrido … (ver nota)