If counting polyominoes is hard, what else can we do?

Ideally⁹ we would like to be able to write in this introduction something along the lines of:

``In chapter $k$ we give our polynomial time algorithm for the computation of the number of polyominoes of area $n$.''

The history of polyomino enumeration on the square lattice would suggest that our attempts at finding a solution are likely to be frustrated¹⁰, and indeed a quick look at the table of contents will tell you that we cannot make any such claim (without lying).

Question 8   If we cannot solve the problem then what can we do?

Three possible options are:

• analyse the problem numerically,
• determine properties of the solution without actually obtaining the solution, and
• solve similar problems.

Roughly speaking, this thesis is divided into three different areas, each exploring one of these possibilities.