Ключевая инвариантность: диагональный сдвиг сохраняет цвет клетки (шахматная раскраска), то есть фишки из клеток одного цвета попадают только в клетки того же цвета.
Разбиваем клетки каждого цвета на два подмножества по чётности номеров строк (или столбцов): при диагональном ходе фишка переходит из одного такого подмножества в другое. Поэтому для любого цветового класса с частями размеров $a$ и $b$ число занятых клеток в этом классе не превосходит $2\min (a,b)$.
Для доски $9\times 9$:
- для «чёрных» клеток (сумма индексов чётна) размеры частей равны $5^2=25$ и $4^2=16$, поэтому максимум для чёрных не больше $2\cdot 16=32$;
- для «белых» клеток размеры частей равны $5\cdot 4=20$ и $4\cdot 5=20$, поэтому максимум для белых равен $2\cdot 20=40$.
Суммарно максимум равен $32+40=72$. Этот показатель достижим (выполним попарные перестановки по диагонали внутри подходящей разбиения доски, для белых делая взаимные пары для всех $40$ клеток, для чёрных — для $32$ клеток), значит ответ:
72