On Wed, Nov 26, 2008 at 4:03 PM, Geoffrey Summerhayes <[EMAIL PROTECTED]>wrote:
> > > > On Nov 25, 6:34 pm, "[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? > > I think I have a way. > > given z pieces and a x-by-y grid > n=x*y/5 > S=(1,1,1,...1) (n times) > solutions=0 > repeat > G.clear() > solutions+=cover(G,S) > while generate_next(S) > return solutions > > where generate_next produces the next combination > of pieces and returns true if it succeeded. > > e.g. for 3 pieces and n=3 > (1,1,1),(1,1,2),(1,1,3),(1,2,2),(1,2,3),(1,3,3),(2,2,2), > (2,2,3),(2,3,3),(3,3,3),then returns false > > then modify cover > > cover(S, G) > if G covered: return 1 [1] > solutions = 0 > > p=first(S) > for (x,y) in (Z_n)x(Z_m) > > # I assume you had a loop here > # to account for rotation/reflection of non- > # symmetrical pieces before placement? > > if ((previous piece placed was different from > the current piece) OR (the position of the > current piece is after the position of > the last place piece)) AND > (it is possible to put p on (x,y) in G): > solutions += COVER(rest(S), G+p(x,y)) > return solutions > > Can be improved, of course. I think that will > eliminate duplicates while finding all solutions, > assuming the loop rotation/reflection of non-symmetrical > pieces does its job correctly. (there are a couple of > gotchas here) > > Anyone see a flaw? > > --- > Geoff > > It is too slow, i replied with better solution , bu i dont know how this > forum works. > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
