For cakes up to **3×3** we can try all possible combinations of
cutting/not cutting of each edge between two neigbouring unit squares. For each such combination
we can verify its validity as follows. We first compute the connected
components of the cake (using the depth first search, or the breadth first
search). Then we verify that there is no cut between two unit squares which
belong to the same connected component.

For cakes of the dimensions **1×N** (resp. **N×1**) all
possible combinations are valid. This gives simple formula,
**2 ^{(N-1)}**, for the number possible cuttings.

For cakes of the dimensions **2×N** (resp. **N×2**) we set up a recurrence as follows.
Let us think of a **2×N** cake as two rows of unit squares of length **N** each.
We denote by **a _{N}** the number of possible cuttings of a

The following picture demonstrates that **a _{N}=2a_{N-1} + 3b_{N-1}**:

The following picture demonstrates that **b _{N}=3a_{N-1} + 4b_{N-1}**:

From these recurrences we obtain **a _{2}=5** and

= 6s

= 6s

= 6s

The solution for arbitrary dimension **M×N** is a generalization of
the **2×N** case, that is, we set up system of (linear) recurrences. However, our solution will work only for small
values of **M**. In practice today's PC is able to handle **M ≤ 5**.

(An alternate view of the same situation: we will consider one dimension **M** to be fixed and use dynamic programming
to compute the number of cuttings for each **N**.)

In our solution, for every partition **p** of the last (i.e. **N**-th) column into connected components,
and every combination **q** which determines whether any pair of the components
occuring in the last column touch each other somewhere in the cake, we compute the number **a(N,p, q)** –
the number of different cuttings of the **M×N** cake obeying **p** and **q**.

This is best demonstrated on an example. We consider **M=3** and the partition **p=(1,2,3)** of the last column:

The partition **p** implies that components **1,2** touch and
likewise **2,3**. Moreover, let us assume that the components **1,3**
do **not** touch anywhere in the cake before the last column. This is formally captured by the
combination **q={{1,2}, {2,3}}**. (Formally **q** is a set of
unordered pairs). Suppose that we have computed the value **a(N-1,p,q)**.

We try all the possible valid combinations how to cut the last column. Several of them are shown are shown of the following picture.

Note that the last combination is valid, since we assume that the
components **1,3** do not touch anywhere before the last column.

Each of the
valid combinations contributes **a(N-1,p,q)** to some **a(N,p',q')** for some
**p', q'**. For example the first two combinations in the picture together
with the last one contribute **3a(N-1,p,q)** to **a(N, p', q')** where
**p'=(1,1,1)** and **q'={}**. (Note that the partitions **(4,4,4)** and **(1,1,1)** and **(1/3,1/3,1/3)** are equivalent.)
Likewise, the third option in the picture contributes **1a(N-1,p,q)** to **a(N, p'', q'')**,
where **p''=(2,2,3)** and **q={{2,3}}**. (Or equivalently, **p''=(1,1,2)** and **q''=(1,1,2)**.)

Thus, by trying all combinations of **p,q** and all ways how to cut the last,
yields the coefficients of the linear system of recurrences for the numbers **a(N,p,q)**.
Using these coefficients we can compute the values **a(N,p,q)** for any **N**.
For example for **M=3**, there are 4 options for **p**; (**(1,1,1)**, **(1,1,2)**, **(1,2,2)**, **(1,2,3)**), and 8 options for **q**; (**{}**, **{{1,2}}**, **{{2,3}}**, **{{1,3}}**, **{{1,2}, {2,3}}**, **{{1,2}, {1,3}}**, **{{1,3}, {2,3}}** and , **{{1,2}, {2,3}, {1,3}}**).
Thus the whole system of recurrences consists of 4*8=32 variables **a(N,p,q)** (for each **N**).

We omit couple of details, such as how to compute the initial values **a(1,p,q)**,
and how determine whether a particular cutting of the last column is valid for some **p,q**,
and how to represent partions **p** and sets **q**.