it is possible to avoid duplicate solution, but i dont know if it is the same effective, and i am not sure if it is correct;
you consider first coordinates in row mayor order, and first uncovered cell must be covered by some top left corener of remaining pentomino. from here i am not sure if you have infinite of pentonimos, or what you must be careful if you have the same pentonimo more thane one time, so you dont try putting he same pentonimo on the same place but thats easy. On Wed, Nov 26, 2008 at 12:34 AM, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
