Квадрат Мерлина

Да будут благословенны твои дни, мой читатель! Да не покинет тебя терпение при чтении моих записок. А терпение тебе, ох, как понадобится…

. . .

Есть такая головоломка «Квадрат Мерлина». Поле, как в детских «Крестиках-ноликах» — три на три. Но клетки могут иметь всего два состояния: вкл. и выкл. То есть, в отличии от «крестиков-ноликов», клетка не может быть нейтральной (пустой): либо «крестик», либо «нолик» — другого не дано.

Условно можно представить все клетки, как монетки, у которых есть лицевая сторона (аверс) и обратная сторона (реверс).

И каждый ход производит над полем Квадрата Мерлина инверсию клеток, в зависимости от точки приложения воздействия. Если нажать на любой угол, то инвертируются четыре клетки: клетка данного угла и три примыкающие к ней.

Например, было так:

0 0 0
0 0 0
0 0 0

а после нажатия в левый верхний угол станет так:

х х 0
х х 0
0 0 0

(Понятно, что ещё одно такое нажатие вернёт поле в исходное состояние.) Для любого угла инверсии клеток симметричны. Т.е., при нажатии на любой угол, переворачивается сама угловая клетка и три примыкающие к ней. Ну, вот… С углами вроде понятно. Разобрались. Поехали дальше.

Теперь. Если же нажать на середину стороны Квадрата, то переворачивается клетка, в которую совершён ход, и две соседние рядом, т.е. инвертируются за раз — три клетки. Вот так:

(было)
0 0 0
0 0 0
0 0 0

нажали в середину средней грани:

(получили)
х х х
0 0 0
0 0 0

Очевидно, что и тут все стороны Квадрата будут вести себя одинаково симметрично.

Ну и, на конец, клетка в центре. Если нажать на неё, то перевернётся не только она, но и ещё четыре клетки, примыкающие к ней в прямых направлениях. Вот так:

(было)
0 0 0
0 0 0
0 0 0

нажали на центральную клетку, и получили:

(стало)
0 х 0
х х х
0 х 0


Вот такие преобразования. Понятно?

А уж условия задачи могут быть разными.

В простейшем случае — это перевести все Аверсы в Реверсы, все «крестики» в «нолики» (или наоборот), все тёмные клетки в светлые. Можно искать решение за минимальное число ходов. А можно произвольно заполнять поле для начального состояния и требовать приведения к одному цвету. А можно вообще искать переход от одного произвольного (начального) расклада, к другому произвольному. И при этом подсчитывать ходы и начислять очки.

Вот на этом принципе я и смастерил несколько очень простых программок, и спешу выложить их в общее пользование. Крутите, ребята, и развивайте свои мозги.

Ссылку на ресурс для скачивания приведу ниже. А пока поговорим за теорию Квадрата Мерлина. Наверное, вам будет удивительно (я тоже сильно удивился, когда это обнаружил), что путая и петляя по полю в разные стороны произвольными ходами, мы бы легко вернули его из любого «запутанного» состояния в «гладкое» первоначальное, если бы записывали свои ходы на бумажку. А потом, вместо того, чтобы повторять все ходы в обратном порядке, произвели бы над записью на бумажке преобразование: сгруппировали все разные нажатия на одну и туже клетку поля (в каком бы порядке они не следовали), и сократили все такие пары! А оставшиеся нажатия можно выполнять в любом порядке! Они гарантированно вернут Квадрат Мерлина в исходное состояние.

Вот так. Знай наших.

Отсюда получается, что в любом преобразовании никогда не будет два нажатия на одну и туже клетку! А Квадрат Мерлина из любого состояния в любое переводится не больше, чем за девять ходов (потому что клеток-то — девять!). А порядок этих ходов никакой роли не играет! Их можно выполнять в любой последовательности.

Круто? То-то.

А теперь разберём мой архив MERLIN.ZIP и чего я в него положил, и как этим баловаться…

Поехали.


Ссылка для закачки:


Архив будет храниться 3 месяца с момента последнего скачивания. Содержимое автоматически проверяется свежими антивирусами, так что не дрожи народ! Всё в ожуре.

Итак,

Merlin.zip        -- 241Кб (247 739 байт)

Внутри лежат:

Name                Size                CRC32
---------------------------------------------------
Merlin1.exe       -- 96,0 Кб (98 304 байт) EA64599C
MerlinSmart1.exe  -- 40,0 Кб (40 960 байт) 46CFD3E6
MerlinTest1.exe   -- 48,0 Кб (49 152 байт) DE2283EA
Mrl2.exe          -- 224 Кб (229 376 байт) DCE40AA4


Краткое назначение программ из архива.

Merlin1.exe – Из произвольного состояния собрать все клетки бирюзового цвета.
MerlinSmart1.exe — Сама решает задачу за наименьшее число ходов.
MerlinTest1.exe — Много сложных задачек.
Mrl2.exe — Вертит безо всяких условий. Графика. Внешний вид можно менять.


Описание программ.

Merlin1.exe – На поле произвольная комбинация клеток. Нужно перевести всё поле к бирюзовому цвету. При решении программа вас похвалит и сообщит, за сколько ходов вы пришли к цели. После чего откроется красивая картинка. Двойной щелчок по картинке вернёт вас к решению другой произвольной комбинации.


MerlinSmart1.exe — Перед вами на форме три поля по 9 клеток в каждом. В левом поле вы устанавливаете начальное положение. В правом — конечное. (При помощи мышки). А потом жмёте кнопку «Решить». Программа сама находит решение и отображает его в среднем поле. Все светлые клетки среднего поля — это ходы, которые нужно сделать по Квадрату Мерлина, когда он будет в набранном вами начальном состоянии, в результате он перейдёт к конечному, набранному тоже вами.

Как оказалось, решение лежит внутри диапазона чисел от 0 до 511. Если каждое число из этого диапазона рассматривать как девять клеток (битиков, которые могут быть либо «ноль», либо «единица»), то решение для всех возможных состояний (переходов из любого начального в любое конечное) укладывается в это множество. А битики в данном случае играют роль не положения клеток, а ходов! Вот так.

Программа ищет решения последовательно, проверяя воздействия на Квадрат Мерлина от 0 (нет ходов), до 511 (все девять ходов). Понятно, что для разных позиций число, которое приводит к решению, будет разным. Когда решение найдено, оно отображается в среднем поле, и программа сообщает: «Есть решение. Искать ещё?» И предлагает выбор: «OK» или «Cancel». А в заголовке окошка выводит текущее значение этого самого числа, при котором решение было получено. Можно сказать «OK», и тогда программа перепробует остальные значения. А можно отказаться. Тогда она остановится на этом. (Правда, мной замечено, что второго решения не выпало ни разу. Но исключать такую возможность нельзя, пока не проведён вычислительный эксперимент, для решения всех возможных комбинаций 511 * 511 = 261 121 шт. Если кто-то из вас сможет логически доказать единственность решения, то я с интересом вас послушаю.)

Ну, и наконец, кнопка «Сброс» — вернёт форму в исходное положение. Можно снова задавать условия и требовать решения. С этой программой всё. Поехали дальше.



MerlinTest1.exe — генерирует последовательность задач для Квадрата Мерлина, предлагая их по одной за раз. Опять перед вами на форме три поля. Только теперь уже программа устанавливает начальное положение (слева) и конечное положение (справа), и даёт вам десять бонусов (очков) «на прокорм». Каждый ход будет стоить вам одного очка. Если вы решите позицию за меньшее число ходов, то останетесь в прибыли. А если будете крутить бестолку и случайно сложите (например, на 27 ходу), то останетесь в убытке (-17 очков). Вот и крутитесь, как можете!

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

Поскольку теперь вы уже знаете, что в Теории любая комбинация решается максимум за 9 ходов, то при наихудших раскладах у вас должна оставаться единица в запасе от решения каждого задания.

Кнопка сброс — отменяет все ходы в решении одного текущего задания.

Новая миссия — новая последовательность заданий (кстати, уже других, ведь общее число всех комбинаций 511 * 511 = 261 121 шт.) будет сгенерирована только после выполнения всех заданий из предложенного ряда. Либо надо закрыть программу и запустить её заново.



Mrl2.exe — Самая простая программа из комплекта. В ней упор сделан на графику. Это «тренажёр», чтобы вы поняли, как крутить Квадрат Мерлина. Никаких условий нет. Зато вы можете сами поменять её внешний вид. Если вас не устраивает космический пейзаж звёздного неба в качестве фона и нефритовые плиточки в качестве клеток, то вы просто кладёте рядом файлы JPG-формата с заданными именами, и программа подкачивает их при запуске, и меняет свой антураж до неузнаваемости.

Имена должны быть такими:

AversBlock.jpg   — лицевая сторона клетки соответствует нулям
ReversBlock.jpg  — обратная сторона клетки соответствует единице
BackImage.jpg    — фон

Желательно конечно, чтобы лицевая сторона и обратная для клетки были одинакового размера — так красивше будет смотреться. И фон чтобы был под размер вашего экрана. Клетки внутри формы висят, как на резиночках. Когда вы растягиваете окошко, то клетки сами ползут к центру.

(Раз уж сегодня 1 июня, то предлагаю вам в качестве оформления Квадрата Мерлина такую идею: найдите фотку покрасивше Мирлин Монро и вырежьте из неё квадратик для аверса, а потом из какого-нибудь «человека-паука» сделайте такой же квадратик для реверса. А в качестве фона — ночной пейзаж Нью-Йорка… )

И наконец, если вы щёлкните мышью два раза по фону на форме, то не пугайтесь. Программа начинает генерировать последовательность всех возможных состояний Квадрата Мерлина, переворачивая клетки в заданное текущим числом положение, а вам выводит окошко для квитирования, в котором сообщает номер позиции и число, из которого получена позиция. Однако, она выводит не все возможные, а только уникальные! Которые не могут быть получены путём поворота предыдущих. Поэтому их число не 511, как вы наверное ожидали, а всего 101 шт.

(То есть, если второе число разложить на двоичные разряды, то единички как раз будут соответствовать реверсам).

Чтобы быстро прекратить генерацию (если вы случайно попали в эту череду окон, а жать «OK» устали, да и мышь жалко!) утопите на клавиатуре клавишу «Enter» и подержите в нажатом состоянии: весь перебор промелькнёт, и не заметите…



Ну, вот, вроде и всё! Счастливых упражнений с Квадратом Мерлина. Пока. Надеюсь, вы героически добрались до конца текста. … Я тоже!

. . .

;-)




16:47:31 01.06.2012          10C62A80