В двух словах, идея доказательства такая.

Пусть через N шагов закрашены N клеток. Доска разбивается на две односвязные области: закрашенную и незакрашенную. Более того, пусть N - наименьшее, когда закрашенная область касается двух противоположных сторон доски. Такое N существует.

Граница между закрашенной и незакрашенной областями (по границам клеток) проходит между этими противоположными сторонами доски, деля каждую из этих противоположных сторон на закрашенную и незакрашенную непустые части.

Пусть M < N - номер шага, на котором была закрашена клетка, примыкающая к этой границе на первой из противоположных сторон (на второй, как мы знаем, её номер - N). В рассматриваемой конфигурации границы минимальный путь от клетки M до соседней с ней пустой клетки за границей раздела должен сначала проходить до клетки N вдоль границы, потом перешагнуть через границу вдоль второй стороны, и потом пройти вдоль границы обратно по пустым клеткам до пустого соседа M на первой стороне. А так как эта граница соединяет две противоположные стороны доски - минимальный путь от M до его соседа при условии произвольности границы раздела равен 2L-1, где L - расстояние между этими сторонами. Минимум достигается если граница раздела прямая. Порядовая заливка как раз обеспечивает такое решение.