Раскраски

Заметим, что в каждом квадрате 22 так же ровно разных цвета, более того ровно по клетки каждого. То есть раскрасив верхнюю строчку (если только не все её клетки одноцветные) и самую левую клетку из второй строчки, мы однозначно раскрашиваем весь оставшийся квадрат или приходим в тупик и понимаем, что его раскрасить нельзя. Несложно заметить, что мы не приходим в тупик, только если каждый столбец получается одноцветным. То есть количество способов раскрасить квадрат равно количеству способов раскрасить первую строчку (но это ещё нужно умножить на т.к. если первая строка одноцветная, то мы рассмотрим первый столбец так же, как первую строку и получим аналогичный случай). Каждая клетка первой строки покрашена в один из цветов - это вариантов, так как соседние строки в один цвет покрашены быть не могут. Минус варианты, когда в ней нет всех трёх цветов, а это (первые два цвета выбираются, дальше чередование).