В прошлый раз, в «Навеяно Проблемой четырёх красок» приводил описание своей небольшой Программы. При разработке Программы, в один момент поле для раскраски у меня получилось таким:

Рис.1. Поле для раскраски (уже раскрашенное).
Рис.1. Поле для раскраски (уже раскрашенное).

Не знаю, сколько из 1936 карт (исследованных в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета при компьютерном доказательстве Проблемы) может охватить такая структура, но простота его структуры, навела на мысль: «А может, есть алгоритм, позволяющий раскрасить любую подобную карту в 4 цвета?»

Структура карты

Карта состоит из клеток, которые случайным образом объединяются в области для раскраски. По горизонтали размещено 56 клеток, по вертикали – 54 (или 53).

Области формируются «одномерными», т.е. располагаются только в одной строке, но имеют случайную «длину» (количество клеток по горизонтали).

Сразу же отмечу, что области, расположенные по «периметру», не должны иметь цвет окружающего фона (Проблема сформулирована для плоскости, а она бесконечна и поэтому цвет фона приходится также учесть). В принципе, это требование «намекает», что для раскраски областей периметра достаточно трёх цветов, что является следствием достаточности четырёх цветов для раскраски всей карты.

Алгоритм раскраски карты

Раскраску будем проводить построчно слева направо и сверху вниз. Алгоритм предполагает несколько проходов по всем областям: первоначальная «черновая» раскраска и исправление несоответствий при следующих проходах.

Шаги алгоритма:

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

2) Вторую строку раскрашиваем тоже в два цвета, но уже в зелёный и белый (цвет фона). Но для этой строки не всё так гладко как для первой, потому что если левую крайнюю область мы можем всегда закрасить в зелёный цвет, то правую крайнюю область можем закрасить в зелёный только в том случае, когда областей в строке нечётное количество. Поскольку, количество областей разыгрывается случайным образом, то мы заранее не знаем «чётность» строки. Просто, на первом этапе (при первом проходе) мы будем игнорировать то, что правая крайняя область может оказаться раскрашенной неправильно.

3) Как установлено в пунктах 1) и 2) раскрашиваем нечётные и чётные строки всей карты и получаем раскраску, когда на границах между строками не будет областей с одинаковым цветом. Да и все внутренние области, области периметра сверху и слева будут раскрашены правильно. Остаётся определиться с раскрашиванием областей периметра справа и снизу (в случае чётного количества строк).

4) Проходим по чётным строкам с правыми крайними областями белого цвета. Тут уже нужен анализ раскраски трёх строк (самой чётной строки и нечётных над и под ней).

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

Рис.2. Над и под правой белой областью находились только жёлтые области.
Рис.2. Над и под правой белой областью находились только жёлтые области.

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

Рис.3. Во второй строке правая область перекрашена из белого в жёлтый, а в третьей строке поменяна последовательность цветов (самая левая область стала жёлтой).
Рис.3. Во второй строке правая область перекрашена из белого в жёлтый,
а в третьей строке поменяна последовательность цветов (самая левая область стала жёлтой).

4.3. Если белая область сверху или снизу граничит одновременно с двумя цветами, то перекрасим её в зелёный цвет, в результате, слева от неё окажется тоже зелёная область. Как в 4.1 и 4.2 анализируем соседей этой зелёной области: если соседи по 4.1 и 4.2 позволяют перекрасить эту область в красный или жёлтый, то – перекрашиваем и на этом исправление этой строки заканчивается.

Рис.4. В строке №40 правая область перекрашена из белого в зелёный цвет, а область слева от неё – в красный.
Рис.4. В строке №40 правая область перекрашена из белого в зелёный цвет,
а область слева от неё – в красный.

Если же не позволяют 4.1 и 4.2, то красим эту область в белый цвет и переходим к анализу следующей области слева и имеющей белый цвет.

В этом случае возникает вопрос: «В любой строке найдётся область, которую по 4.1 или 4.2 можно будет перекрасить в красный или жёлтый цвет?»

Отвечу так: «На моей практике «да», всегда находилась такая область». Этому способствуют две взаимосвязанные причины: 1) большая длина строки (56 клеток); 2) наличие в каждой строке области размером в одну клетку с вероятностью «единица» (одноклеточные области всегда можно перекрасить по 4.1 или 4.2).

Разумеется, иногда попадаются области, содержащие более одной клетки и перекрашиваемые по 4.1 или 4.2 (на рис.4 именно этот случай).

 Итак, в случае нечётного количества строк, алгоритм будет работать безупречно.

Если на какой-то карте вдруг алгоритм не сработает, то это, всего лишь, карта «не той системы», т.е. алгоритм на такую карту и не рассчитан.

В самом начале было отмечено, что мы не претендуем «объять необъятное» и большая часть из 1936 карт не может быть раскрашена по этому алгоритму. Но, допускаю, что для каких-то других карт тоже можно построить какие-то алгоритмы. Ведь, если существует алгоритм, то это и является доказательством некоторой части Проблемы четырёх красок, соответственно, более простым, чем представили Кеннет Аппель и Вольфганг Хакен (для всей Проблемы!).

 Моя попытка достроить алгоритм и для чётного количества строк была безуспешна. Хотя, «вручную» докрашивать всегда удаётся. При этом для перекраски какой-то части областей последней чётной строки можно использовать п.4.1 алгоритма.