Graphillion and the exact cover problem

[co-ord]

Hi,

I would like to know if it is possible to use the Graphillion library to solve an exact cover problem.

For example, let's say I have a set of 4 tetrominos and I would like to find all the possible tilling combinations inside a 4x4 grid. At the moment I am using Donald Kuth's "Dancing Links" technique to find all the solutions but I have heard that using a ZDD data structure could drastically improve the searching process.

Could Graphillion be used to solve this type of problem ? If so, would you mind to provide a simple example or some guidance ?

[takemaru]

Thank you for your interest in Graphillion.

Last year, seanlaw developed a Python script about dancing link with ZDD based on the paper. I recommend you first to check dxz.py and ask seanlaw if you have questions.

Best regards,

[co-ord]

Thank you for hint, it is very much appreciated.

Thankfully.

[co-ord]

@takemaru Hi again!

Following a quick discussion with Sean it seems his implementation doesn't quite work yet in its current state. Before investigating any further could you please tell me if it is possible/appropriate to implement the DXZ algorithm using Graphillion ?

日本語でかいてみます: Graphillionを使ってDXZアルゴリズムを作ることができますか。もしくは、他にもっと適したものがありますか。

Respectfully

[takemaru]

The following are the message from Dr. Nishino, the author of DXZ. I hope that helps you.

Currently, Graphillion does not implement Algorithm DXZ, which can build a ZDD representing the solutions of an exact cover problem. You can find an implementation of the Algorithm DXZ at Donald Knuth's web page. The program DLX6 extends DXZ and it can be applied to the XCC (exact cover with colors) problems.

[co-ord]

My question was to know if Graphillion could be used to represent the ZDD inside of DXZ but thank you anyway. I will probably implement my own ZDD structure and not rely on Graphillion.

Thanks to both Dr. Nishino and you for your time.