We present a general method for obtaining lower bounds on the capacities of two-dimensional (2-D) constraints. We apply our method to the 2-D (d=2, infin) run-length limited (RLL) constraint and obtain the best known lower bound, .4423, on the capacity of this constraint. Our lower bounds are shown to be achievable by a fixed-rate, polynomial-complexity encoding-decoding algorithm based on enumerative coding with approximate counts.