PDA

View Full Version : Programming algorythm: domino tilings question


sirams
11-02-2005, 12:42 PM
I have found a problem, which can be solved if I solve the following:
I need a program, which calculates all possible variants how you can tile m*n fields large rectangle with domino pieces. I did google search but I have found only the Kasteleyn formula which counts how much variants are possible. But I need to store all these variants in arrays or something like that (to output them). If someone has an algorythm or source in Java/C++/Pascal/Delphi, I would really appreciate that. Also any link to useful info will be really good for me.
Thanks.

sirams
11-07-2005, 03:01 PM
ok, I figured it out anyway :) If someone else needs it
it can be done with recursive function, which tries to put a horizontal domino, than calls itself. Than removes horizontal domino and tries to put a vertical domino. Again calls itself and removes vertical domino. When the board is full, the variant is saved into a dynamically growable array. And so the function goes forth and back until it gets back to the first domino, puts it vertically and tries all subvariants and then just retuns. :) Thats all! Now I need the way to output the results but it will be very easy comparing with the task I have done already. Phew! :)