Hello,
I'm trying to write an algorithm counting all possible ways (symmetry
included) a grid of dimensions NxM can be covered with a prescribed
subset of pentominoes. (http://en.wikipedia.org/wiki/Pentomino). The
algorithm looks like this
let S be the set of pentominoes
let G be the grid of dimensions NxM
================================
COVER(S, G) :
if G covered: return 1 [1]
solutions = 0
for every p in S :
for (x,y) in (Z_n)x(Z_m) :
if is is possible to put p on (x,y) in G :
solutions += COVER(S, G+p(x,y)) # G+p(x,y) places pentomino
p on grid G on coordinates (x,y)
return solutions
================================
It is easy to see, that the above pseudocode generates/counts
duplicated solutions. For example, consider the grid 5x2 and pentomino
"I". The algorithm would count two ways of obtaining the solution
"II".)
One way I could fix this is to simply add another in [1] and see if
this solution was already generated but I'm sure there is a way to
avoid generating duplicate solutions altogether. Can somebody explain
me how?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
