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
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
