[fjfaase]

I have made an implementation of the original Dancing Links algorithm, but for some large problem, more than a million rows and 104 columns with an average of about sixteen positions per row, it is killed because it takes too much memory.

I wonder if the updated algorithm is using less memory.

My guess is that this large problem has about a hundred million solutions. So, even if it finds a hundred solutions per second, it still would require about ten days to finish.

The problem, I am working on, is the number of solutions to the 'Fancy Tetris Houten Puzzel' where all pieces of the same color touch are connected by at least one side touching another side of a piece with the same color.

I have been thinking about other algorithms for solving this Exact Cover problem that are less memory sensitive.

[OskarS]

It does improve memory usage! In the version in the paper, each item has four links, in the book version they only have two. So memory usage is roughly cut in half.

[mafuy]

From a rough estimation, it should not run out of memory with these constraints. The matrix should be about 1m rows * 16 cells/row * (4 pointers/cell + overhead?) * 8 bytes/pointer = approx 1 GB. That's quite little.

The dynamic memory is negligible with 104 cols, avg search depth should only be around 104/16.