Gray codes for column-convex polyominoes and a new class of distributive lattices

We introduce the problem of polyomino Gray codes, which is the listing of all members of certain classes of polyominoes such that successive polyominoes differ by some well-defined closeness condition (e.g., the movement of one cell). We discuss various closeness conditions and provide several Gray codes for the class of column-convex polyominoes with a fixed number of cells in each column. For one of our closeness conditions, a natural new class of distributive lattice arises: the partial order is defined on the set of m -tuples [ S 1 ] × [ S 2 ] × ⋯ × [ S m ] , where each S i > 1 and [ S i ] = { 0 , 1 , … , S i − 1 } , and the cover relations are ( p 1 , p 2 , … , p m ) ≺ ( p 1 + 1 , p 2 , … , p m ) and ( p 1 , p 2 , … , p j , p j + 1 , … , p m ) ≺ ( p 1 , p 2 , … , p j − 1 , p j + 1 + 1 , … , p m ) . We also discuss some properties of this lattice.