Помогите с задачей по информатике

У мастера есть много одинаковых плиток паркета трёх различных цветов. Каждая плитка имеет форму уголка из трёх клеток (см. рис. справа). Мастер должен замостить ими комнату размером 2N×2N.

По требованию заказчика никакие одноцветные плитки не должны соприкасаться друг с другом по стороне клетки. Разрешается оставить непокрытой ровно одну клетку. Предложите алгоритм решения этой задачи для всех N, для которых возможно.