29. My grandson makes wall hangings by stitching together 16 square patches of fabric into a 4 x 4
grid. I asked him to use patches of red, blue,
green and yellow, but to ensure that no patch
touches another of the same colour, not even di-
agonally.
The picture shows an attempt which fails only
because two yellow patches touch diagonally.
In how many different ways can my grandson
choose to arrange the coloured patches correctly?

9514 1404 393

  168

Step-by-step explanation:

Below are shown the 7 different kinds of arrangements that can be made. Each of these can be permuted into 24 different arrangements by assigning colors in a different order than the one used here:

  {1, 2, 3, 4} ⇒ {green, blue, red, yellow}

Then the total number of possible correct colorings is 7·24 = 168.

__

These colorings were found using a computer program that identified all 168 viable colorings, then eliminated permutations. It started by identifying ways to color 2 rows, then adding rows based on that.

_____

You'll notice that the last on the attached list most closely matches the one in the problem statement.