Навеяно проблемой четырёх красок
Как известно, Проблема четырёх красок решена в результате перебора вариантов на компьютере. Но не все математики согласны с таким решением, поскольку возникают сложности с проверкой отсутствия ошибок.
Для непосвящённых… Проблема четырёх красок формулируется очень просто: «Для раскраски любой карты на плоскости достаточно четырёх красок».
При этом, если области (страны) «касаются» только в одной точке, то считается, что они не граничат и их можно раскрасить в один и тот же цвет. Так, например, для раскраски клеток шахматной доски достаточно двух цветов.
Более того, Мартин Гарднер в книге «Математические головоломки и развлечения» упоминает, что доказана теорема «о двухцветных картах», которая утверждает, что «любую карту на плоскости можно раскрасить в два цвета тогда и только тогда, когда все её вершины чётны» (здесь, «вершиной» называется точка, в которой сходятся границы более двух стран).
* * *
Создал очень НЕинтересную игру, навеянную этой Проблемой.
Поле для игры
Области образованы из квадратиков (клеток) первоначальной сетки (56×55), из которой убраны некоторые звенья, т.е. границами областей являются замкнутые ломаные линии, каждое звено которой повёрнуто относительно соседней на угол кратный 90°.
Если области имеют единственную общую точку (узел сетки), то они считаются не граничащими между собой и могут быть окрашены в один и тот же цвет. Поскольку, изначально сетка квадратная, то в одной точке могут сходиться четыре области и тогда (если другие границы с другими областями позволят) эти четыре области могут быть раскрашены в два цвета как клетки шахматной доски (см. Рис. 1а).
Также легко имитируется схождение трёх областей в одной точке, ввиду того что, в этом случае, каждая из этих областей обязательно граничит с двумя другими (см. Рис. 1 б). Следовательно, здесь обязательно потребуется три цвета для правильной раскраски.
а) б)
Рис. 1
а) б) Рис. 1
Правила игры
Нужно раскрасить в 4 цвета карту, в которой разбиение на области (страны) произведено случайным образом при помощи стандартного генератора случайных чисел.
Предлагается использовать цвета: красный, жёлтый, зелёный и кремовый (clCream, который на моём мониторе выглядит, практически, как чисто белый).
Есть условие, что, окаймляющая карту, область закрашена в кремовый цвет и, соответственно, все области, граничащие с краями карты (периметр карты), должны быть раскрашены строго в три других цвета.
Работает таймер, который останавливается при «нажатии» кнопки «Закончил». После этого производится проверка правильности раскраски и если есть ошибка, указываются её координаты. По подтверждению игроком прочтения этого сообщения, таймер включается для продолжения отсчёта затраченного времени.
Формируется и хранится список одиннадцати лучших результатов.
*
Нюансы реализации Программы
Для существования решения (способа раскраски карты) поле игры формируется следующим образом (в тайне от игрока).
Поле размечается сеткой с квадратными ячейками. Затем, случайным образом разыгрывается цвет каждой ячейки.
На следующем шаге, ячейки одного цвета, имеющие общую границу, объединяются путём удаления этой общей границы. В результате, получаются области, ограниченные замкнутыми ломаными линиями и раскрашенные в 4 цвета.
Для обеспечения пункта 3 Правил игры, вначале производится раскраска ячеек по периметру карты в три цвета и только потом раскрашиваются внутренние ячейки в четыре цвета.
И, наконец, все области перекрашиваются в цвет clCream и карта предъявляется игроку.
*
Программа имеет два режима: «Игра» и «НЕ Игра».
Про первый режим рассказано выше. Второй режим предоставляет некоторые возможности для экспериментирования. Так, можно выбрать количество цветов для исходной раскраски в пределах от 2 до 18. Тем не менее, задача остаётся той же самой — раскрасить в 4 цвета (или меньшее количество цветов, если выбрана двухцветная или трёхцветная карта).
Выдаётся отчёт по параметрам созданной карты.
Отсчёт времени не ведётся.
Исходная раскраска карты демонстрируется.
*
Мои наблюдения в режиме «НЕ Игра»
Увеличение количества цветов раскрашивания ведёт к упрощению формы областей, поскольку ячейки одинакового цвета реже оказываются рядом и, соответственно, уменьшается среднее количество ячеек в областях. Больше становится «шахматных досок», которые раскрашиваются в два цвета.
С раскраской «пятицветной» карты в четыре цвета проблем не было (тем более, если цветов ещё больше, то и карта проще для раскраски).
При ошибочной окраске какой-либо области обычно для исправления достаточно перекраски двух-трёх ближних областей.
Ошибочная раскраска, требующая исправлений, бывает редко, чаще бывают пропущенные «одноклеточные» области (из-за большой площади игрового поля).
Очень часто встречается возможность выбора из двух цветов для конкретной области. Т.е., вероятность того, что ваша раскраска совпадёт с исходной, практически, равна нулю (кроме, конечно, раскраски в два цвета, когда условие 3 Правил игры однозначно определяет цвета раскраски).
Ещё про двухцветную раскраску
Чтобы выполнялось условие чётности всех вершин в «теореме о двухцветной карте», необходимо, чтобы карта занимала всю плоскость. Иначе, надо оговаривать, что цвет, «окаймляющей» карту, области , не участвует в задаче (при её «участии» условие «чётности всех вершин» невыполнимо). То есть, получается мы рассматриваем не всю бесконечную плоскость, а только её некоторый конечный участок.
Не в этом ли кроется сложность доказательства Теоремы четырёх красок?
Например, для поверхности тора смогли доказать, что для раскраски любой карты достаточно семи красок. А поверхность тора конечна…
Кстати, достаточно ли обосновано утверждение о том, что «поверхность сферы с одной выколотой точкой топологически эквивалентна плоскости»? С одной стороны, «выкалывание» точки нарушает целостность поверхности сферы, что, вроде, недопустимо в топологии. С другой стороны, поверхность сферы конечна в отличие от плоскости…
Учёт, «окаймляющей» карту, области сразу накладывает ограничение. Если даже в карте все вершины чётные, то окаймляющая область может быть окрашена только в третий цвет. А для карты, все вершины которой нечётные, окаймляющая область может быть окрашена только в четвёртый цвет. Это видно и на наших рисунках (Рис. 1а и б).
*
Желающим могу выслать исходники на Delphi. Пишите в личку.
