algorithm - automaticamente - El algoritmo de Dancing Links: ¿una explicación que sea menos explicativa pero más sobre la implementación?

sudoku solver automaticamente (2)

He estado trabajando en un Sudoku Solver, mi solucionador actual utiliza el algoritmo de seguimiento, pero aún así toma demasiado tiempo.

Espero reducirlo a menos de un segundo para la mayoría de los casos. Como tal, he decidido volver a escribirlo con el algoritmo de enlaces de baile, entendiendo que es uno de los mejores métodos de fuerza bruta que funciona bien, especialmente con un problema de restricción como el Sudoku Puzzle.

He tratado de leer el artículo de Wiki y Knuth sobre él, sin embargo, ambos son un poco difíciles de comprender y extremadamente detallados.

También leí la versión de Sudopedia, y parece que una vez que llegó a la implementación del Sudoku, se volvió demasiado abstracta.

¿Alguien puede intentar explicar el algoritmo de Dancing Links no en términos de su derivación sino de su implementación? (Sería genial usar el Sudoku como ejemplo)

¡Gracias!

Usted podría estar interesado en mi implementación en javascript .

En primer lugar tienes que entender Exact Cover. Un problema de cobertura exacto es un problema en el que se le da un montón de opciones, y un conjunto de restricciones y su desafío es seleccionar un grupo de las opciones que llenarán cada restricción exactamente una vez.

Por ejemplo, considere el caso de alguien que está creando su rutina de baile en el hielo. Tienen una serie de trucos que necesitan para mostrar a los jueces, y no quieren realizar ningún truco más de una vez. Tienen una serie de secuencias que son grupos de trucos que se pueden juntar y quieren elegir la selección ideal de secuencias para cubrir todos los trucos una vez. En este ejemplo, las restricciones son que deben realizar todos los trucos. Las opciones son las posibles secuencias que podrían incorporar en su rutina.

Una buena manera de representar problemas de este tipo es dibujar una tabla donde las restricciones son columnas y las elecciones son filas, y tiene una gran X en las celdas donde una opción particular cumple con esa restricción.

Como resultado, dadas las restricciones y opciones correctas, el sudoku se puede describir como un problema de cobertura exacta.

Ok, asumiendo que lo tienes, ahora necesitas entender el Algoritmo X. Knuth dijo al respecto: "El Algoritmo X es simplemente una declaración del obvio enfoque de prueba y error. (De hecho, no puedo pensar en ningún otro método razonable. forma de hacer el trabajo, en general.) ". Así que aquí está mi descripción del algoritmo X:

Si tu tabla no tiene columnas, detente: la has resuelto. Si tienes una solución parcial almacenada, entonces en realidad es una solución real, devuélvela.
Seleccione una columna (que representa una restricción).
Encuentre una fila con una cruz en esa columna (que representa una opción que cumple con esa restricción). Agréguelo a algún tipo de estructura donde esté almacenando soluciones potenciales. Si no puedes encontrar una fila, abandona, no hay soluciones.
Suponga que la fila que encontró en 3 está en la solución, así que elimine todas las columnas que tengan una X en esa fila. Al eliminar todas esas columnas, también elimine todas las filas que tengan una X en las columnas que está eliminando (porque ya cumplió con la restricción, por lo que tiene prohibido elegir algo que la satisfaga nuevamente).
Ahora recursivamente intenta resolver la tabla reducida. Si no puede, elimine la fila que intentó de la estructura de solución potencial, restaure todas las filas y columnas que eliminó en los pasos 3 y 4 e intente una fila diferente. Si te quedas sin filas, abandona, no hay soluciones.

Ahora que entiendes eso, puedes entender los enlaces de baile. Dancing Links es una forma de implementar ese algoritmo de manera eficiente. El punto clave de los enlaces de baile es que en una lista enlazada, cuando elimina un nodo (lo que se puede hacer de manera eficiente modificando los punteros de sus vecinos), el nodo que ha eliminado tiene toda la información que necesita para volver a agregarla. a la lista vinculada (en el caso de que resulte que te equivocaste al adivinar que era parte de la solución). Eso, más el hecho de que si haces que todas tus listas vinculadas sean circulares, de repente pierdes muchos casos especiales, es prácticamente todo lo que es bailar.

Aunque esta pregunta es muy antigua, pensé en añadir:

Esta página hace que el algoritmo sea muy fácil de entender: la redacción de Zendoku . Hasta que lo leí en ese enlace, pensé que debía ser un algoritmo súper avanzado, pero realmente una vez que puedes visualizarlo, es solo una solución realmente ingeniosa pero simple.

Además, mi implementación en C # debería ser bastante fácil de leer ... sería útil para dividir las distintas clases en diferentes archivos, estoy seguro.
Es en gran parte una implementación directa del pdf de Knuth, pero con algunas optimizaciones orientadas a objetos (en realidad, desde que hice esto hace unos meses, no recuerdo bien cuánto me aparté del pdf)