An approximate enumerative coding method (100, 200) and apparatus (300) employ a cardinality-approximating (C-A) lower bound in mapping a message M to a 2-dimensional (2-D) codeword array that satisfies a 2-D constraint. The method (100) includes encoding the message M as a codeword array X using an encoder apparatus. The encoding determines entries in a codeword array X using the C-A lower bound. The C-A lower bound is a function of several terms, namely a memory term k, a cardinality of a set of sequences satisfying a horizontal constraint, a columnar extension probability of the 2-D constraint, and a non-negative constant that is a function of the columnar extension probability. The apparatus (300) includes an encoder processor (310), memory (320) and a computer program (330) stored in the memory (320) and executed by the encoder processor (310).