P vs. NP - N-Queens

En agosto del 2022, hacía 20 años desde el fallecimiento de unos de los más grandes de la informática. Hablo de Edsger Wybe Dijkstra, el cual por muchos es recordado por sus punzantes críticas (Ej. Go To Statement Considered Harmful) a la forma de diseñar y programar software, de la época. Hace unos años tuve el gusto de abordar una revisión histórica de sus trabajos, con la que pude apreciar y valorar todavía más su figura, así como la de otros importantes nombres como: Charles Antony Richard Hoare, David Lorge Parnas, Niklaus Wirth, Barbara Liskov, Stephen Zilles, Ole-Johan Dahl, Kristen Nygaard, Alan Kay… entre otros. Si hoy en día, diseñar software y programar puede ser visto como un ingenioso arte preciso es en gran medida gracias a las bases que todo ellos sentaron.

En mi libro, abordo un resumen de esa revisión histórica en la sección: 2.4 - La abstracción como puerta hacia P = NP (58-63 pág.) y argumento como pude apreciar que abstracción no solo inunda cada rincón de nuestra ciencia, sino que está detrás de los más importantes avances que hemos ido dando.

En honor a Edsger Wybe Dijkstra y a todos ellos en general, pensé que podría ser interesante dedicarles un algoritmo, aplicando mi metodología. Así que me propuse dedicar una semana para diseñar un nuevo algoritmo para el conocido problema de las mil reinas (N-Queens). Personalmente conocí este problema gracias al video de Eduardo Sáenz de Cabezón - El problema de las 1000 reinas. ¡Un millón de dólares en juego! en el cual me baso y uso para explicar algunas de las partes de la implementación que hago.

Ahora bien, recordemos que en EWD316: A Short Introduction to the Art of Programming (see more), Dijkstra aborda el diseño de un algoritmo que genera todas las configuraciones de las reinas para un tablero de 8*8. Sin embargo, siguiendo nuestra metodología lo que vamos a pretender es construir un conjunto que de forma abstracta contenga todas las configuraciones que sean válidas para un tablero de NxN, sin caer en los costes exponenciales asociados. En otras palabras, vamos a buscar y mostrar paso a paso durante una serie de videos como diseñamos un algoritmo teóricamente polinómico, haciendo uso de la abstracción como un recurso computacional más.

Capítulos

I Diseño en Papel

En el primer capítulo “Diseño en papel” abordamos el diseño del algoritmo en papel.

De forma agnóstica a cualquier implementación concreta explicamos cuales serían los principales componentes de una máquina que construyera el conjunto de todas las configuraciones de reinas que sean válidas para un tablero de NxN. Es importante indicar que este algoritmo hará uso de abstracciones exponenciales para evitar una escalada exponencial de los costes espaciales y temporales.

II Cheesboard

En el segundo capítulo “Chessboard” comenzamos a implementar la lógica del tablero y sus reglas. Este tablero nos permitiera conocer que celdas son compatibles e incompatibles con cada una de las celdas. La idea detrás de esto es poder saber que celdas no serán válidas en caso de poner una reina en una celda determinada.

III Timeline

En el tercer capítulo “Timeline” implementamos la línea temporal de nuestra máquina. De la misma forma que vimos en HC y TSP, la ejecución de nuestro algoritmo será paso a paso, y hará uso de una tabla que le permitirá guiar la construcción del conjunto de todas las configuraciones válidas.

Abordamos la lógica necesaria para la propagación de conjuntos en el siguiente paso, enviando el ID de la acción únicamente a las celdas que sean compatibles con la anterior.

IV MockQueensSet

En el cuarto capítulo de esta serie abordamos la implementación de un Mock del conjunto de configuraciones. Cabe indicar que a pesar de que esta estructura de datos no sigue la metodología de las abstracciones exponenciales que proponemos, consideramos interesante crearla para ayudar a entender cuál es el funcionamiento general del algoritmo.

Por otra parte, el contraste nos permitirá entender mejor cual es nuestra propuesta y porque defendemos que no es correcto representar físicamente (una a una) cada una de las configuraciones válidas.

V DB Actions

En el quinto capítulo de esta serie abordamos la implementación de la base de datos de acciones, que nos servirá para dar seguimiento a las acciones UP (construcción, composición…) y JOIN (unión de conjuntos).

Será precisamente la base de datos de acciones la que controla que el número total de conjuntos con los que trabajaremos a lo largo de la ejecución sea polinómico. Por lo tanto, la responsabilidad de que el algoritmo caiga o no en costes exponenciales recaerá en como representamos físicamente el conjunto de configuraciones. El cual, a pesar de tender de forma natural a crecer exponencialmente, tal y como defendemos con nuestra metodología de abstracciones exponenciales podemos representar de forma abstracta usando grafos.

VI Graph QueensSet

En el sexto capítulo de esta serie siguiendo nuestra metodología implementaremos la estructura de datos exponencial (EDS, pág. 87) GraphQueensSet. Esta es una implementación concreta de un Exponential Abstract Data Type (EADT, pág. 87). Esto implica que GraphQueensSet deberá lograr, un poder de abstracción exponencial (para representar todas las posibles configuraciones de las reinas) haciendo uso de un espacio y tiempo polinómico.

Recordemos que MockQueensSet representaba físicamente cada una de las configuraciones, lo que implica que cualquier máquina de cómputo tiene que soportar el crecimiento exponencial de los requisitos espaciales de esa estructura. Sin embargo, si consideramos la abstracción como un recurso computacional más. Podemos diseñar una estructura de datos con la cual trabaje nuestra máquina que a pesar de estar acotada espacialmente, pueda representar para nosotros una información creciente en términos exponenciales.

En otras palabras, el truco está en que a pesar de que la máquina trabaje con un grafo o cualquier otra estructura de datos acotada espacialmente, lo que esa información acotada pueda significar para nosotros, no repercutirá en los costos del algoritmo, eludiendo de esa forma los límites físicos que tradicionalmente hemos estado percibiendo a la hora de diseñar algoritmos para problemas NP-Complete, NP-Hard…

Como hemos avanzado usaremos grafos para representar ese conjunto de forma abstracta (al igual que hicimos en HC, TSP y 3-SAT). Sin embargo, como podrá verse a lo largo de los cuatro videos de este capítulo, la implementación tiene muchas peculiaridades y requiere haber entendido el funcionamiento general del algoritmo.

Los procesos más importantes que veremos serán el filtrado, UP, JOIN, así como el proceso de revisión del grafo. Este proceso es más simple y por lo tanto más fácil de entender que el que abordamos en nuestro libro para HC y TSP.

VII Reader & ReaderExp

En el capítulo séptimo de esta serie estudiaremos como podemos leer una de las configuraciones contenidas de forma abstracta en nuestro GraphQueensSet y posteriormente veremos como podríamos leer todas las que contiene el conjunto solución que hemos construido paso a paso.

Es importante indicar que la lectura de una sola de las configuraciones implica un proceso de manipulación del grafo con el que representamos el conjunto. Sin embargo, y a pesar de que este proceso es polinomico, si necesitamos leer un número exponencial de configuraciones (Ej. Todas las que contine) entonces caeremos en costes exponenciales, puesto que estaríamos trasladando la información exponencial que tenemos en la dimensión de la abstracto a la dimensión espacial, lo que implicará necesariamente que nuestro algoritmo caiga en unos costes temporales exponenciales.

En resumidas cuentas, obtener un certificado será polinómico sin embargo obtener todos implicará un coste pseudopolimico respecto al número de certificados totales que tengamos.

VIII Testing

En el octavo capítulo de esta sería probamos el funcionamiento general del algoritmo y comprobamos que hayamos construido y representado de forma correcta todas las configuraciones válidas.

Durante esta prueba no solo comprobamos que cada una de las configuraciones individualmente sea correcta (secuencia de reinas que no se atacan entre si) sino que comprobaremos que el conjunto contiene exactamente todas las configuraciones validas existentes.

IX Machine

En el capítulo noveno de esta sería implementamos la máquina abstracta para N-Queens, y añadimos el concepto de instancia para poder indicarle al algoritmo que partimos de un tablero que ya tiene algunas reinas coladas. Esto nos permitirá obtener el conjunto de todas las configuraciones válidas en las cuales se encuentren ciertas reinas por defecto.