Abstract: | 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 S1]×S2]× ×Sm], where each Si>1 and Si]={0,1,…,Si−1}, and the cover relations are (p1,p2,…,pm) (p1+1,p2,…,pm) and (p1,p2,…,pj,pj+1,…,pm) (p1,p2,…,pj−1,pj+1+1,…,pm). We also discuss some properties of this lattice. |