Chessboard Colouring

If 3 of the 4 squares in a 2 by 2 square have been 'filled' (when generating a colouring), then there is only one option for the other square.

This means that in the grid below, there is only one option for each square, once all squares with a number lower than it have been filled:

So once all the squares with 0 have been filled, there is only 1 colouring possible.

This means that the number of colourings is the number of ways to fill the squares with 0s.

Each of these initial colourings will result in a valid final colouring, as every 2 by 2 square which has been generated meets the conditions, and every 2 by 2 square in the grid is generated by this process.

As there are 2 ways to fill each of the 19 squares, this is clearly $2^{19} = 524288$ .

Start from the up-left 2 by 2 square, there are only 8 possible combinations (0 = white, 1 = black):

If you consider the next 2 by 2 square in the same row (made by 2 elements of the starting square + 2 new ones) you can see that there are only 2 allowed configuration compatible with the conditions. If you repeat the same concept until the end of the first row there are $2^8 = 256$ total combinations possible excluding the first square 8 configurations.

In the same way you can calculate the combinations for the first column.

It's easy to observe that if you set all the elements in the first row and the first column 2 by 2 squares, the rest of the 10 by 10 square has a given combination.

In total there are $8*2^8*2^8 = 524288$ possible combinations.

the key is you can fill the fouth element only in one possible way if the rest three are already filled in 2x2 square

1st row doesnt form any 2x2 square and doesnt pose any restriction which makes the no. of possible ways $2^{10}$ to fill

only the 1st element of 2nd row has 2 choices, rest of the elements dont have any choice once the square to its left is filled

likewise every row other than first has only 2 ways to fill. Therefore total no. of ways $= 2^{10} \times 2^9 = 2^{19} = 524288$

If you fill in the cells in a raster scan starting at the top left all cells with 3 known neighbours have to be computed. The 19 cells with fewer known neighbours on the top row and left column can be either colour. So there are just 2^19 possibilities.

• The first cell at the top left of the grid (1,1) can be either 1 or 0.
• The next cell to its right (2,1) can also be either 1 or 0 and doesn't depend on (1,1). The same holds true for all cells across the top row (x,1). So you can fill in row one with any combination of 1 or 0. That's 2^10 possibilities. (There are 8 possible 2x2 patterns and these can be assembled to make any sequence possible for the top row.)
• When you come to start the next row at (1,2) you can again choose either 1 or 0 and neither would result in an impossible move.
• Now you have set three of four cells chosen in the corner the last cell (2,2) has to make that 2x2 block uneven so it only has one possibility and can be computed.
• The same is true for the rest of the row.
• Each subsequent row follows the same patten

So cells in the top row (x,1) and the left column (1,y) have two equally probable options but all other cells have to be computed based on the cells above and to the left.

if x=1 or y=1 then cell is equally likely to be a 1 or a 0

otherwise, when x>1 and y>1

$cell_{x,y} = (cell_{x-1,y-1}+cell_{x,y-1}+cell_{x-1,y} + 1) \mod 2$

The result is 2^19 (2^10 for the top row and 2^9 for the other rows)

I solved this problem by using dynamic programming . (https://en.wikipedia.org/wiki/Dynamic_programming)

We use an array to store the solutions.First,we need an array.Next,we need to define states.

Let i be the ith of the row.

Next,we need to express the state of the row (i.e. which square is black or white).

Since the square is relatively small and C++ is good at bit operations,we can do a little trick called state compression .

We can store the state of the row into a single binary number,and 0 for white and 1 for black.

Let's just call it k.

For example,if k = 853 =(1101010101)2,the state of the row is:

And now let's define dp[i][k],where i is ith of the row,k represents for thee state of the ith row,just like discussed before.

And the value of dp[i][k] is the total ways to color the square,where the ith row has the state k.

To find out the total answer,just find the sum of dp[10][0~1023],since we have 10 columns.

dp[1][k] is always equal to 1 for purpose.

But how can we derive from previous values?

Assume we are going to derive dp[i][k1] from dp[i-1][k2].

Well,using bit calculations,you will figure out if and only if k1 xor k2 is equal to (0101010101)2 or (1010101010)2 ,then dp[i][k1] is a valid way,by the addition rule,we need to change dp[i][k1] to dp[i][k1]+dp[i-1][k2] ,if the condition satisfies.

Since we have 10 rows and 10 columns,we need to iterate i from 2 to 10,k1 from 0 to 1023,k2 form 0 to 1023,to find all the possible solutions.

Then we need to find the sum of dp[10][0~1023],and that's the answer.

And here's my C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int dp[12][65600];
int makedigit1(int m)
{
    int a=0,x=1;
    for(int i=1;i<=m;i++)
    {
        if(i%2==1){a=a|x;}
        x=x<<1;
    }
    return a;
};

int makedigit2(int m)
{
    int a=0,x=1;
    for(int i=1;i<=m;i++)
    {
        if(i%2==0){a=a|x;}
        x=x<<1;
    }
    return a;
};

int main()
{
    int n=0,m=0,ans=0;
    cin>>n>>m;
    int a1=makedigit1(m);
    int a2=makedigit2(m);
    int Kmax=(1<<m)-1;
    for(int k=0;k<=Kmax;k++)
    {
        dp[1][k]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int k1=0;k1<=Kmax;k1++)
        {
            for(int k2=0;k2<=Kmax;k2++)
            {
                if((k1^k2)==a1 || (k1^k2)==a2)
                {
                    dp[i][k1]+=dp[i-1][k2];
                }
            }
        }
    }
    for(int k=0;k<=Kmax;k++)
    {
        ans+=dp[n][k];
    }
    cout<<ans;
    return 0;
}

Input: 10 10

Output: 524288

good this problem cannot be brute-forced having $2^{n^2}$ dumb possibilities to consider, to many for a computer. So some thought is required as other people mentioned leading to $2^{2n-1}$ valid options

The tiles in the $1^{st}$ row can be coloured independent of each other. There are $2^{10}$ combinations of this.

A tile can then freely be coloured in the $2^{nd}$ row, but this forces the colours of the tiles next to it, and thus forces the entire row. (2 possible combinations for the row).

Similarly for the other 8 rows.

Hence there are $2^{10}*2^9=2^{19}=524288$ possible combinations.

This is by no means the best solution, but it's the way I did it.

Suppose an $n\times n$ grid is colored as desired. How many ways are there to add squares to the top and right to make an $(n+1)\times (n+1)$ grid?

We have two choices for the two leftmost squares of the top grid (e.g. for the pictured grid, we can color them both black or both white), and after that, the squares on the top of the grid (except for the top right corner) are uniquely determined.

Similarly, we have two choices for the two bottommost squares of the right column, and after that, the new squares on the right of the grid (except for the top right corner) are uniquely determined.

Finally, the top right corner is uniquely determined once we have colored the other squares.

So each $n\times n$ grid gives rise to exactly four $(n+1) \times (n+1)$ grids containing it in the bottom left corner.

Let $a_n$ be the number of ways to color an $n\times n$ grid as desired. Then $a_n = 4a_{n-1}$ for $n \ge 3,$ so $a_n = a_2 \cdot 4^{n-2}.$ Finally, it's easy to see directly that $a_2=8,$ so $a_n = 8 \cdot 4^{n-2} = 2^{2n-1}.$

So $a_{10} = 2^{19} = \fbox{524288}.$

[1] If you think about just one 2x2 square, then imagine two of the cells are predetermined. Then, in any possible ease, you will only have 2 options to select the remaining two. (to see this, draw all the possible scenarios on a piece of paper). [2] In the same line of thought, if 3 cells are predetermined, you only have 1 single choice for the remaining fourth cell.

Let's start by adding two cells to our solution, in the beginning of the first row. That gives us 2^2 different colourings.

If we extend the solution with an additional row, then [1] gives us two options to choose from. We can keep adding rows this way, and count the combinations by multiplying by 2 each step. This ends up being 2^9 combinations.

Now, to extend the solution horizontally, we can see that we only get to select the color of the new cell in the first row. After that, we use [2] to select the colors of all remaining cells in the column, inductively. We need to add 8 columns to get to the total of 10 columns

This amounts to 2^2 * 2^8 * 2^9 = 2^19 = 524288 possible layouts