Usted podría estar interesado en my implementation in javascript.
En primer lugar, debe comprender Exact Cover. Un problema de cobertura exacto es un problema en el que se le dan varias opciones, y un conjunto de limitaciones y su desafío es seleccionar una serie de opciones que llenen cada restricción exactamente una vez.
Por ejemplo, considere el caso de alguien que está creando su rutina de baile sobre hielo. Tienen una serie de trucos que deben 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 que quieren elegir la selección ideal de secuencias para cubrir todos los trucos una vez. En este ejemplo, las restricciones son que deben realizar cada truco. Las elecciones son las posibles secuencias que podrían incorporar a su rutina.
Una buena manera de representar problemas de este tipo es dibujar una tabla donde las restricciones son columnas y las opciones son filas, y tiene una gran X en celdas donde una opción en particular cumple esa restricción.
Como resultado, dadas las limitaciones y opciones correctas, sudoku se puede describir como un problema de cobertura exacta.
Ok, suponiendo que tienes que, ahora que hay que entender Algoritmo X. Knuth dijo de ella "Algoritmo X es simplemente una declaración del método de ensayo y error evidente. (De hecho, no puedo No piense en ninguna otra manera razonable de hacer el trabajo, en general.) ". Así que aquí está mi descripción del algoritmo X:
- Si su tabla no tiene columnas, deténte - lo ha resuelto. Si tiene una solución parcial almacenada, entonces en realidad es una solución real, devuélvala.
- Seleccione una columna (que represente una restricción).
- Encuentra una fila con una cruz en esa columna (que representa una opción que cumple esa restricción). Agréguelo a algún tipo de estructura en la que almacene soluciones potenciales. Si no puede encontrar una fila, renuncie, no hay soluciones.
- Suponga que la fila que encontró en 3 está en la solución, por lo tanto, elimine todas las columnas que tengan una X en esa fila.Al eliminar todas esas columnas, también elimine todas las filas que tienen una X en las columnas que está eliminando (porque ya ha cumplido la restricción, por lo que no puede elegir algo que la satisfaga nuevamente).
- Ahora, recursivamente, intente resolver la tabla reducida. Si no puede, elimine la fila que intentó de la posible estructura de solución, restaure todas las filas y columnas que retiró en los pasos 3 y 4 y pruebe con una fila diferente. Si te quedas sin filas, entonces date por vencido, no hay soluciones.
Ahora que entienden que, se puede entender enlaces 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 vinculada, cuando elimina un nodo (lo que se puede hacer de manera eficiente modificando los indicadores de sus vecinos), el nodo que ha eliminado tiene toda la información que necesita para volver a agregarlo. a la lista vinculada (en el caso de que resulte erróneo cuando supusiste que era parte de la solución). Eso más el hecho de que si haces que todas tus listas enlazadas sean circulares, de repente pierdes muchos casos especiales, es más o menos todo lo que baila.
Ver también: http : //stackoverflow.com/questions/1518346/ –
Bueno, entonces supongo que esto debería ayudarlo: [Un Sudoku Solver en Java implementando Knuth's Dancing Links Algorithm] (http://www.ocf.berkeley.edu/~jchu /publicportal/sudoku/sudoku.paper.html) –
El código fuente completo para este enlace ya no está disponible. Y los fragmentos de código tienen algunos errores. Específicamente, el método de destapar (ColumnNode c). En ese artículo, ese código es una copia del método de cobertura con algunas cosas en el bucle for cambiado. El iterador del ciclo interno debe ir a la izquierda, no a la derecha, y los enlaces deben restaurarse al original, no repetir la operación de cobertura. Ejemplo: leftNode.getUp(). SetDown (leftNode); en lugar de leftNode.getUp(). setDown (leftNode.getDown()); –