Каждую клетку доски

нужно покрасить либо в белый, либо в чёрный цвет.
Сколькими способами это можно сделать так, чтобы не нашлось двух соседних по стороне белых клеток?
Кроме длинного бестолкового перебора, дающего ответ
63, не вижу никакой идеи.
Наведите, пожалуйста, на мысль.