Да, можно покрасить клетки доски 8 на 8 в 4 цвета таким образом, чтобы никакие две соседние клетки не имели одинакового цвета. Это называется задачей о четырех красках и является классическим примером вершинной раскраски графа.