Олимпиадные задачи из источника «7 класс» - сложность 1 с решениями

Художник-авангардист Змий Клеточкин покрасил несколько клеток доски размером 8×8, соблюдая правило: каждая следующая закрашиваемая клетка должна соседствовать по стороне с предыдущей закрашенной клеткой, но не должна — ни с одной другой ранее закрашенной клеткой. Ему удалось покрасить 36 клеток. Побейте его рекорд! (Жюри умеет закрашивать 42 клетки!)<img src="/storage/problem-media/103879/problem_103879_img_2.gif">

2002 год — год-палиндром, то есть одинаково читается справа налево и слева направо. Предыдущий год-палиндром был 11 лет назад (1991). Какое максимальное число годов-непалиндромов может идти подряд (между 1000 и 9999 годами)?