Simplest Tiling of the Floor
C - 208 bytes

w,q,n,m,r,g,u;t(char*f){for(w=0;f[w++]-10;);for(q=1;;q++)for(n=1;m=q/n,n&lt;=q;++n)if(n*m==q){char t[q];bzero(t,q);r=q;for(g=0;f[g];++g){u=g/w%m*n+g%w%n;r=t[u]+f[g]-195?r:0;if(f[g]&amp;64)t[u]=f[g];}if(r)return r;}}


Equivalent code before golfing:

#include &lt;stdio.h&gt;
#include &lt;strings.h&gt;

int t(char* f) {
    int w = 0;
    for ( ; f[w++] - 10; );

    for (int q = 1; ; q++) {
        char t[q];
        for (int n = 1; n &lt;= q; ++n) {
            int m = q / n;
            if (n * m == q) {
                bzero(t, q);
                int r = q;
                for (int g = 0; f[g]; ++g) {
                    int u = g / w % m * n + g % w % n;
                    if (t[u] + f[g] == 195) {
                        r = 0;
                    }
                    if (f[g] &amp; 64) {
                        t[u] = f[g];
                    }
                }
                if (r) {
                    return r;
                }
            }
        }
    }
}


The algorithm is fairly brute force, so it should be reasonably obvious how it works based on the code. Here are a few comments anyway:


Input is expected to have the form with trailing spaces so that all lines have the same length.
First loop finds the width by looking for first newline character.
Outer loop is over candidate meta-tile sizes q. Exits with a return when a meta-tile can cover the floor. Note that the loop does not need another exit condition since there is always a solution (worst case is size of input).
First nested loop and following if enumerates valid meta-tile width/height combinations for size q.
A character array matching the candidate meta-tile size is zero-initialized.
Inner loop iterates over all tiles in the floor.
u is the index in the meta-tile that corresponds to the floor tile.
If both floor tile and meta-tile tile are a or b and different (sum of a = 97 and b = 98 is 195), there is a mismatch, and the meta-tile size with the attempted dimensions will not work.
Otherwise, if the floor tile is a or b, the tile color is copied to the candidate meta-tile.
Returns size of meta-tile when successful match was made, i.e. if the attempted match was not marked as failed.


Test code used:

#include &lt;stdio.h&gt;

extern int t(char* s);

int main()
{
    printf("%d\n", t(
        "a\n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "aaa  \n"
        "a    \n"
    ));
    printf("%d\n", t(
        "aabaab\n"
        "abaa  \n"
        "aaba  \n"
    ));
    printf("%d\n", t(
        "aabaab\n"
        "a  a a\n"
        "aabab \n"
    ));
    printf("%d\n", t(
        "ba  \n"
        "aaab\n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "ababb\n"
        "aaaa \n"
    ));
    printf("%d\n", t(
        " a aa\n"
        "ab ba\n"
        " aba \n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "abab \n"
        "aaaa \n"
    ));
    printf("%d\n", t(
        "ba \n"
        " ba\n"
        "  b\n"
    ));
    printf("%d\n", t(
        "baa\n"
        "aba\n"
        "aab\n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "aabaa\n"
        "aaaa \n"
    ));
    return 0;
}


Output:

1
1
6
18
8
10
6
4
4
9
6