Dancing Links X!
« il: Luglio 14, 2014, 11:31 »
Ciao a tutti, oggi vi propongo una mia implementazione dell'algoritmo X di Donald Knuth usando i Dancing Links: https://github.com/DavideCanton/DancingLinksX. In pratica si tratta di esprimere un problema di Exact Cover (https://en.wikipedia.org/wiki/Exact_cover) tramite una matrice binaria sparsa, e di enumerarne tutte le soluzioni (o solo una, possibilmente).

Insieme al codice ci sono un esempio di solutore per Sudoku e per il problema delle N-regine. (Dare un'occhiata a come è stata implementata la Sudoku Board potrebbe essere anche utile, uso un trucchetto con as_strided che è utile da sapere per tutti i "numpyisti").

Hope you enjoy it! ;)