Thursday, 19 September 2013

Implementing the Algorithm X with Dancing links to solve pentomino tiling

Implementing the Algorithm X with Dancing links to solve pentomino tiling

http://en.wikipedia.org/wiki/Exact_cover#Pentomino_tiling
How are we constructing the matrix for algorithm X. The columns have to be
the constraint imposed on the problem i.e. 12 pentomino to be used exactly
once + each of the 60 square have to be filled exactly once. This gives
(12+60=72) constraints hence the 72 columns. The question is how are the
rows generated?

No comments:

Post a Comment