Для решения этой задачи можно воспользоваться методом динамического программирования.

Обозначим количество способов отметить первые k клеток доски так, чтобы никакие две отмеченные клетки не граничили по стороне, как f(k).

Для решения этой задачи можно использовать следующее рекуррентное соотношение:

f(1) = 4; f(2) = 6; f(3) = 6

f(k) = f(k-1) + f(k-2) + f(k-3), для k > 3

Таким образом, чтобы решить задачу для 31 клетки, нужно последовательно вычислить значения функции f(k) для k = 1, 2, ..., 31.

f(31) = f(30) + f(29) + f(28) = 45636

Итак, количество способов отметить на шахматной доске 31 клетку так, чтобы никакие две отмеченные клетки не граничили по стороне равно 45636.