Оценка:

Рассмотрим любой квадрат 2 на 2 клетки. Все его клетки покрашены в попарно различные цвета, так как иначе две клетки одного цвета стоят рядом. Значит, потребуется не менее четырёх цветов.

Пример:

Раскрасим таблицу вертикальными полосами в чёрный и белый цвета. Теперь пронумеруем все строки сверху вниз от 1 до 28. В каждой чётной строке перекрасим все белые клетки в светло-серые, а все чёрные - в тёмно-серые. Теперь для любой клетки две соседние с ней по строке клетки окрашены в другой цвет из-за изначальной раскраски полосами, а остальные - из-за замены цветов.

Ответ: в 4 цвета.