добрый вечер, я бы рассуждал так, естественно не претендую на истину:
1. Закрасим квадраты наибольшего пересечения квадратов (извините за тавтологию), 1 рисунок.
2. Квадраты будем рассматривать слева направо из верхнего левого угла. В 1 квадрате получается 1 лишняя закрашенная клетка, соответственно требуется удалить одну любую из закрашенных с краю, так как в них пересекаются меньше квадратов (дальнейшие рассуждения показывают что можно удалить любую клетку кроме центральной). Удаляем (Рис. 1).
3. Получаем Рис. 2. В 2 и 3 квадрате все хорошо, переходим к 4му квадрату, в нем 1 лишняя клетка, но удалить из всех закрашенных в нем клеток мы можем только одну, так как другие 3 являются частью уже проверенных квадратов, удаляем (Рис. 2).
4. Получаем Рис. 3. Проверяем 5, 6, 7, 8 и 9 квадраты, в каждом только 4 клетки.
5. Меньше клеток закрасить невозможно так как все закрашенные клетки расположены в точках максимального пересечения квадратов.