How many ways can fill in HxW rooms with 2x1 tatami mats?

Question

Question

I want to check the ways of tiling a HxW grid with tatami mats (1x2 tiles)?
But tatami filling has a special rule, which it is prohibited to make a cross with the border of the tatami mats.
I have written a code for this problem, which is very slow.
If H=20 and W=20, it may get 1 seconds. I want to calculate for more big cases.
Are there any efficient algorithm?

Example

I have an example of H=3, W=4 and H=4, W=4.
If H=3 and W=4, there are 4 ways.
If H=4 and W=4, there are 2 ways.

My Current Code (C++)

#include <cstdio>
#include <vector>
 
using namespace std;
 
int H, W;
 
inline bool hantei(vector<vector<int> > tatami)
{
    bool ok = true;
 
    for (int k = 0; k < H - 1; k++)
    {
        for (int l = 0; l < W - 1; l++)
        {
            int c1 = tatami[k][l];
            int c2 = tatami[k][l + 1];
            int c3 = tatami[k + 1][l];
            int c4 = tatami[k + 1][l + 1];
 
            bool ok2 = !(c1 > 0 && c2 > 0 && c3 > 0 && c4 > 0 && c1 != c2 && c1 != c3 && c1 != c4 && c2 != c3 && c2 != c4 && c3 != c4);
 
            ok = ok && ok2;
        }
    }
 
    return ok;
}
 
inline int dfs(int count_, vector<vector<int> > tatami)
{
    if ((count_ - 1) * 2 == H * W)
    {
        return 1;
    }
 
    int sum = 0;
 
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (!tatami[i][j])
            {
                if (H - i - 1)
                {
                    if (!tatami[i + 1][j])
                    {
                        vector<vector<int> > tatami2(tatami.begin(), tatami.end());
 
                        tatami2[i][j] = count_; tatami2[i + 1][j] = count_;
 
                        if (!hantei(tatami2)) { return 0; }
 
                        sum += dfs(count_ + 1, tatami2);
                    }
                }
 
                if (W - j - 1)
                {
                    if (!tatami[i][j + 1])
                    {
                        vector<vector<int> > tatami2(tatami.begin(), tatami.end());
 
                        tatami2[i][j] = count_; tatami2[i][j + 1] = count_;
 
                        if (!hantei(tatami2)) { return 0; }
 
                        sum += dfs(count_ + 1, tatami2);
                    }
                }
 
                return sum;
            }
        }
    }
 
    return 0;
}
 
int main()
{
    while (true)
    {
        scanf("%d", &H);
        scanf("%d", &W);
 
        if (H == 0 && W == 0) { break; }
 
        if (H % 2 == 1 && W % 2 == 1)
        {
            printf("0\n");
        }
        else if (H == 1 || W == 1)
        {
            printf("1\n");
        }
        else if (H == W)
        {
            printf("2\n");
        }
        else
        {
            vector<vector<int> > start(H, vector<int>(W, 0));
 
            printf("%d\n", dfs(1, start));
        }
    }
 
    return 0;
}

EDIT: This code is searching more nodes (the number of times of recursion) than necessary. The answer will not be exceed 1000 if H, W <= 20.

Thank you for reading.

Answer 1

This problem has been investigated by Dean Hickerson (see http://oeis.org/A068920/a068920.txt ). You can find proofs and recursive algorithms at the linked location.