La estructura de datos del algoritmo de enlaces de baile de Knuth

Question

Lamento si mi pregunta suena estúpida porque la comprensión de mi estructura de datos no es muy buena.

He estado leyendo el algoritmo Knuth's Dancing Links y entiendo cómo funciona básicamente. Se menciona que la visualización de la estructura de datos del enlace de baile se ve como una tabla con columnas y filas, con cada celda conectada a sus celdas arriba, abajo, izquierda y derecha. También he leído que circularly double linked-list se usa en este algoritmo.

Lo que quiero saber es cómo se puede hacer exactamente una doble lista de enlaces en dicha tabla con columnas y filas?

Como sé, la mayoría de las listas doble-vinculadas solo tiene 2 punteros (arriba y abajo), ¿significa que tengo que crear mi propia lista enlazada personalizada que tenga 4 punteros (arriba, abajo, izquierda y derecha?)? O hay otras formas?

Gracias de antemano.

Answer 1

El algoritmo usa una lista doblemente vinculada para cada fila y columna, no solo una lista.

Esta article on using dancing links to solve sudoku tiene una bonita imagen.

Al menos en el código de este artículo, las filas están representadas como punteros izquierdo y derecho y las columnas como punteros hacia arriba y hacia abajo en los mismos nodos, más o menos como usted describe, por lo que las listas están interconectadas.