Multicolored 4x4

For any colouring of the top-left $2\times2$ square, there are four possible colourings of the remainder of the top two rows.

For each of the first three possibilities, there is exactly one way of completing the full square. For the final possibility, there are two choices each for possible third and fourth rows.

Thus there are $7$ ways of colouring the square, once the top-left square has been filled in. This means there are $7\times4! = \boxed{168}$ total colourings.

My apologies in advance, as this solution isn't elegant, and is a lot of bean counting... I would love to see if someone can come up with a simpler approach.

Consider the four in the middle. These can be chosen in $4! = 24$ ways.

For the remaining $12$ boxes there are $3$ ways to choose the top left corner. You can pick any of the three colors that aren't in the top left corner of the center $2\times2$ grid. For the one you pick that is the same color as the bottom right one in the center $2\times2$ grid, there are $3$ solutions, and for each of the other two colors there are $2$ solutions.

Let the middle four be numbered: 1 - top left, 2 - top right, 3 - bottom left, 4 bottom right

For the sake of this description, we will use numbers instead of colors...

The three solutions for picking 4 for the top left color are:

• 1 in top right
• 3 in top right, 1 in bottom right
• 3 in top right, 2 in bottom right
• (2 and 4 in the top right won't lead to any solutions)

For each case, the rest of the numbers can be filled in trivially showing that these are the only solutions.

And the two solutions for picking 3 for the top left color are:

• 2 in bottom right
• 1 in bottom right
• (3 and 4 in the bottom right won't lead to any solution)

Again, for each case, the rest of the numbers can be filled in trivially showing that these are the only solutions.

Finally, by symmetry, there are also two choices if you chose 2 for the top left box.

This leads then to a total of $7$ solutions for each of the $24$ ways to paint the central $2\times2$ grid.

Make sense?

So, the total number of ways to paint the $4\times4$ grid is given by,

$24\times7 = \boxed{168}$