Enlaces de baile

La idea de DLX se basa en la observación de que en una lista circular doblemente enlazada de nodos,

x.izquierda.derecha ← x.derecha; x.derecha.izquierda ← x.izquierda;

eliminará el nodo x de la lista, mientras

x.izquierda.derecha ← x; x.derecha.izquierda ← x;

Esto restaurará la posición de x en la lista, siempre que x.right y x.left no se hayan modificado. Funciona independientemente del número de elementos en la lista, incluso si ese número es 1.

Knuth observó que una implementación ingenua de su algoritmo X consumiría una cantidad excesiva de tiempo buscando unos. Al seleccionar una columna, era necesario buscar unos en toda la matriz. Al seleccionar una fila, era necesario buscar unos en toda la columna. Después de seleccionar una fila, era necesario buscar unos en esa fila y en varias columnas. Para mejorar este tiempo de búsqueda, reduciendo su complejidad de O(n) a O(1), Knuth implementó una matriz dispersa donde solo se almacenan unos.

En todo momento, cada nodo de la matriz apuntará a los nodos adyacentes a la izquierda y a la derecha (unos en la misma fila), arriba y abajo (unos en la misma columna), y al encabezado de su columna (que se describe más adelante). Cada fila y columna de la matriz constará de una lista circular doblemente enlazada de nodos.

Cada columna tendrá un nodo especial conocido como "encabezado de columna", que se incluirá en la lista de columnas y formará una fila especial ("fila de control") compuesta por todas las columnas que aún existen en la matriz.

Finalmente, cada encabezado de columna puede indicar opcionalmente el número de nodos en su columna, de modo que encontrar la columna con el menor número de nodos tiene una complejidad de O( n ) en lugar de O( n × m ), donde n es el número de columnas y m es el número de filas. Seleccionar una columna con un bajo número de nodos es una heurística que mejora el rendimiento en algunos casos, pero no es esencial para el algoritmo.

En el Algoritmo X, las filas y columnas se eliminan y se reincorporan a la matriz periódicamente. Las eliminaciones se determinan seleccionando una columna y una fila dentro de ella. Si una columna seleccionada no tiene filas, la matriz actual es irresoluble y debe ser recalculada. Cuando se produce una eliminación, se eliminan todas las columnas cuya fila seleccionada contenga un 1, junto con todas las filas (incluida la seleccionada) que contengan un 1 en cualquiera de las columnas eliminadas. Las columnas se eliminan porque están llenas y las filas porque entran en conflicto con la fila seleccionada. Para eliminar una sola columna, primero se elimina el encabezado de la columna seleccionada. A continuación, para cada fila donde la columna seleccionada contiene un 1, se recorre la fila y se elimina de las demás columnas (esto hace que esas filas sean inaccesibles y evita conflictos). Se repite este proceso de eliminación de columnas para cada columna cuya fila seleccionada contenga un 1. Este orden garantiza que cada nodo eliminado se elimine exactamente una vez y en un orden predecible, lo que permite recalcularlo correctamente. Si la matriz resultante no tiene columnas, significa que todas están rellenas y las filas seleccionadas forman la solución.

Para retroceder, el proceso anterior debe revertirse utilizando el segundo algoritmo mencionado. Un requisito para usar dicho algoritmo es que la reversión debe realizarse de forma exacta, invirtiendo las eliminaciones. El artículo de Knuth ofrece una visión clara de estas relaciones y del funcionamiento de la eliminación y reinserción de nodos, y proporciona una ligera flexibilización de esta limitación.

También es posible resolver problemas de cobertura única en los que una restricción particular es opcional, pero no puede cumplirse más de una vez. Dancing links se adapta a esto con columnas primarias que deben completarse y columnas secundarias que son opcionales. Esto modifica la prueba de solución del algoritmo de una matriz sin columnas a una matriz sin columnas primarias y, si se utiliza la heurística de mínimo de unos en una columna, entonces solo es necesario verificar dentro de las columnas primarias. Knuth analiza las restricciones opcionales aplicadas al problema de las n reinas . Las diagonales del tablero de ajedrez representan restricciones opcionales, ya que algunas diagonales pueden no estar ocupadas. Si una diagonal está ocupada, solo puede estarlo una vez.