Snake Polyominoes of Maximal Area in a Rectangle

Given a discrete rectangle R of dimensions h × w, let W snake h×w be the set of snake-like polyominoes contained in R represented as binary matrices, i.e. polyominoes whose underlying simple graph is a chain with respect to the 4-adjacency relation.We present an algorithm that generates W snake h×w for any h and w.Also, let a max (h,w) the maximal area that can be realized by an element of W snake h×w .We provide exact formulas of a max (h,w) for h ∈ {1,2,3,4,5} and w ∈ N * .