Let $S(m)$ be the number of partitions of an $n \times n$ checkerboard into $m$ subsets such that all the squares in each subset are connected contiguously. So for each $n,$ $m$ goes from $1$ to $n^2.$ For a $2 \times 2$ board, for example, $S(1) = 1,$ $S(2) = 6,$ $S(3) = 4$ and $S(4) = 1.$ The $3 \times 3$ case is proving to be quite an effort in brute force.
How do I approach this problem so that the cases for $n > 2$ are more tractable? Thank you in advance for any guidance you can provide.
By "contiguously" I mean that any pair of squares in a subset must be connected by a sequence of squares in which successive squares share an edge.