Решение головоломок Харриса

Научная статья Решение игровых комбинаторных задач «Головоломки Харриса»
с использованием математических и программных методов


Автор: Васильева Алёна Валерьевна.

г. Рязань

Содержание

Введение 3

Задачи с перекатывающимися кубиками 5

Первая задача. Классическая головоломка Харриса 16

Вторая задача. Модифицированная головоломка Харриса 17

Третья задача. Задача в четырёх красках 18

Четвёртая задача. 19

Порядки операторов 21

Приложения 24

Список литературы 26

Введение

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

Теоретические сведения, которые были необходимы мне для получения практических результатов, изложены в книге «Преобразования и перестановки» Калужнина Л.А. и Сущанского В.И.. Авторы этой книги указывают на имеющийся опыт изложения основ теории групп школьникам на кружках и факультативных занятиях в республиканской физико-математической школе при Киевском университете. В книге содержится материал, касающийся приложений групп перестановок, «Теорема Лагранжа», «Орбиты группы перестановок», «Лемма Бернсайда», «Комбинаторные задачи».

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

Оценим сложность этих комбинаторных задач. В кубике Рубика 27 граней; в головоломке Харриса 24 пары граней, причём достаточно обращать внимание только на одну из парных граней. В кубике Рубика 3·3 =9 образующих операторов над гранями, каждый имеет порядок 4; в головоломке Харриса 4 образующих оператора, каждый имеет порядок 9. Таким образом, и в той и в другой головоломке можно рассматривать 36 образующих операторов, и составлять из них слова, не содержащие подряд двух одинаковых букв. Таким образом, головоломки почти одинаковы по сложности.

Задачи с перекатывающимися кубиками – это практически не изученные головоломки. Рассматриваемые задачи связанны с головоломкой Харриса. Две первые из них сформулированы в книге М. Гарднера «Путешествие во времени.

Поставлены цели двух типов: практические и алгебраические.

Практические цели состоят в нахождении решений задач с перекаты-вающимися кубиками, в том числе и минимальных решений. Задачи в связи с этими целями ставятся следующие. Множество перекатов всех кубиков свести к фиксированной группе операторов над перестановками, которые изучены в алгебре. Найти с помощью перебора композиций операторов решения некоторых задач, связанных с головоломкой Харриса. Найти минимальные решения задач. Привести статистику, то есть, сколько новых состояний можно получить при данном числе ходов. Исследовать, сколько ходов (в рассматриваемых операторах) достаточно, чтобы получить любое состояние из данного состояния.

Алгебраические цели. Исследовать группу операторов. Определить, возможные длины циклов, на которые можно разложить перестановки, и определить возможные типы перестановок. Указать все возможные порядки операторов.

Задачи с перекатывающимися кубиками

1 b l u r f d	2 b l u r f d	3 b l u r f d
4 b l u r f d		5 b l u r f d
6 b l u r f d	7 b l u r f d	8 b l u r f d

Введём обозначения. Шесть граней каждого кубика пометим буквами u, d, l, r, f, b следующим образом: верхняя грань u (up), левая грань l (left), передняя f (front), нижняя d (down), правая r (right), задняя b (back). Нам потребуются только состояния головоломки, в которых свободна именно центральная клетка, поэтому сопоставим матрице 3х3 вектор (строку) длины 8.

Построим математическую модель головоломки. Упорядочим грани всех восьми кубиков, начиная с граней первого кубика в порядке u, d, l, r, f, b, и переходя к граням других кубиков и беря их в том же порядке. Каждой грани присвоим свой номер по порядку, начиная с номера 1..

Например, все верхние грани имеют номера 1, 7, 13, 19, 25, 31, 37, 43, а левые грани имеют номера 2, 8, 14, 20, 26, 32, 38, 44.

Для каждого кубика в пространстве достаточно указать расположение двух смежных граней (расположение остальных граней тогда однозначно определяется). Тогда в математической модели головоломки Харриса будем указывать номер кубика, грань сверху и грань слева. Таким образом, модель головоломки – это вектор из 16 элементов (2 грани, 8 кубиков). Координатами вектора могут быть все 48 граней. За исходное состояние головоломки примем множество (1, 2, 7, 8, 13, 14, 19, 20, 25, 26, 31, 32, 37, 38, 43, 44). Эта модель головоломки хорошая, но помимо всех состояний головоломки она описывает множество других, мне не нужных объектов.

Удобнее, нагляднее и правильнее использовать другую математическую модель. Оставляем вектор (строку) длины 8, элементами которого будут тройки, на первом месте которых номер кубика, на втором – грань сверху, на третьем – грань слева. Так, например, головоломка в начальном состоянии запишется в виде вектора (1ul; 2ul; 3ul; 4ul; 5ul; 6ul; 7ul; 8ul), или строки
1ul 2ul 3ul 4ul 5ul 6ul 7ul 8ul. Обозначим построенную математическую модель головоломки через M. M можно рассматривать как 8-ми элементное множество 6-ти элементных множеств. Согласно введённым здесь обозначениям M записывается в виде строки.

Мощность множества различных состояний головоломки (с различением пложений матрицы в пространстве) равна 4 438 236 667 576 320 = 8!^. (24)⁸ – это точное число. Действительно, всего головоломка имеет 8 кубиков, каждый из которых независим от других. Следовательно имеем 8! Различных перестановок. Переставляемые множества сами являются перестановками, и при этом независимыми. Эти множества состоят из
6-ти граней, и перестановка на них однозначно определяться расположением двух непротивоположных из них. Для выбора первой грани имеем 6 возможностей, для выбора второй – четыре возможности. Поэтому количество перестановок ганей одного кубика равно 6^. 4=24. Ввиду независимости перестановок имеем множителем 24⁸. Итак, число различных состояний равно 8!^. (4!)⁸.

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

Как было сказано ранее, ход состоит в перекатывании кубика через одно из четырёх нижних рёбер на пустую клетку. Обозначим эти перекаты: U- вверх, L- налево, D- вниз, R-направо. На множестве M определим восемь подстановок:

a = URDL = 1ul 2ul 3ul 4rf 5ul 6bl 7ld 8ul.

b = RULD = 1ul 2ul 3ul 4fl 5ul 6ru 7bd 8ul.

c = DLUR = 1ul 3rul 5fl 4ul 2lf 6ul 7ul 8ul.

d = LDRU = 1ul 5fu 2ld 4ul 3bl 6ul 7ul 8ul.

e = RDLU = 2ru 4fd 3ul 1bl 5ul 6ul 7ul 8ul.

f = DRUL = 4fl 1ld 3ul 2rb 5ul 6ul 7ul 8ul.

g = LURD = 1ul 2ul 3ul 4ul 8fl 6ul 5bu 7ld.

h = ULDR = 1ul 2ul 3ul 4ul 7lb 6ul 8ru 5bl.

Обозначим через E тождественную подстановку. Перечисленные восемь подстановок вместе с тождественной образуют некоторую группу подстановок G по операции композиции. Элементы этой группы представляют собой различные композиции из перечисленных выше подстановок. Будем записывать их также в виде строк, состоящих из символов a, b, c, d, e, f, g, h.

Рассматриваемая группа преобразований является подгруппой группы всех перестановок на множестве M, значит, её мощность является делителем числа 8!^. (4!)⁸.

Группа подстановок G, действуя на некоторое исходное состояние головоломки, порождает (генерирует) некоторое множество состояний головоломки Харриса, являющееся подмножеством множества всех состояний головоломки. Таким образом, было бы хорошо указать несколько состояний, действуя с которыми рассматриваемая группа подстановок может сгенерировать группу всех состояний головоломки. То есть интересно найти разбиение множества состояний головоломки на классы эквивалентности относительно отношения «переводятся друг в друга с помощью группы преобразований G». Займёмся построением дерева состояний головоломки из некоторого состояния с помощью группы преобразований G и попутным изучением свойств G.

Тождественной перестановкой головоломки назовём любую перестановку, приводящую его в исходное состояние, обозначим E.

Перечислим свойства подстановок, которые понадобятся далее для исключения повторов состояний головоломки, получающихся с помощью перестановок из G.

1. a и b, c и d, e и f, g и h – взаимно обратные.

Поэтому в строке перестановки недопустимо, чтобы после буквы a шла буква b, после b шла буква a, аналогично, запрещается, чтобы после буквы c шла буква d, после d шла буква c, после буквы e шла буква f, после f шла буква e и после буквы g шла буква h, после h шла буква g.

2. Будем использовать обозначения степени, например a³ = aaa. Порядок каждой перечисленных восьми подстановок равен 9, тогда a⁹=E, b⁹=E, c⁹=E, d⁹=E, e⁹=E, f ⁹=E, g⁹=E, h⁹=E. Поэтому подряд одна и та же подстановка может быть записана такое число раз, которое не превышает её порядок.

3. a⁵ = b⁴, b⁵ = a⁴, c⁵ = d ⁴, d ⁵ = c⁴, e⁵ = f ⁴, f ⁵ = e⁴, g⁵ = h⁴, h⁵ = g⁴. Поэтому в строке будем допускать не более четырёх одинаковых символов подряд.

4. Восемь подстановок можно мыслить как два класса подстановок: прямые и обратные для них, либо a, b, c, d и e, f, g, h. Последнее разбиение на классы хорошо тем, что внутри каждого класса композиция операторов коммутативна: ac = сa, ad = da, bс = сb, bd = db, eg = ge, eh = he, fg = gf,
fh = hf.

Оценка сверху на число различных состояний после того, как сделано не более чем N ходов, то есть вычисление числа вариантов на фиксированном шаге дерева при данном способе его построения.

Предположим, имеем строку (последовательность) ходов S=(s₁ s₂ ... s_n-1 s_n). Элементы s_k и s_l лежат в одном классе, если s_k s_l оба лежат водном из множеств
{a, b, c, d} и {e, f, g, h}. Разделим строку S на подстроки используя следующее правило (правило 1). Поставим разделитель между s_i и s_{i + 1}, если s_i и s_{i + 1} не принадлежат одному классу. Пример. Пусть S=aacgbcec, тогда получим деление S= aac|g|bc|e|c.
Длины последовательностей элементов одного класса.

Рассуждения для класса, содержащего a и класса, содержащего e, аналогичны. Рассмотрим класс, содержащий a.

Множество элементов длины 1:
(a, b, c, d).
Множество элементов длины 2:
(a², b², c², d², ac, ad, bc, bd).
Множество элементов длины 3:
(a²c, ac², a²d, ad ², ad ³, b²c, bc², b²d, bd ², a³, b³, c³, d³).
Множество элементов длины 4:
(a³c, a²c², ac³, a³d, a²d ², ad ³, b³c, b²c², bc³, b³d, b²d ², bd ³, a⁴, b⁴,c⁴, d ⁴).
Множество элементов длины 5:
(a⁴c, a³c², a²c³, ac⁴, a⁴d, a³d ², a²d ³, ad ⁴, b⁴c, b³c², b²c³, bc⁴, b⁴d, b³d ², b²d ³, bd ⁴).

Множество элементов длины 6:
(a⁴c², a³c³, a²c⁴, a⁴ d ², a³d³, a²d⁴, b⁴c², b³c³, b²c⁴, b⁴ d², b³d³, b²d⁴).
Множество элементов длины 7:
(a⁴c³, a³c⁴, a⁴d ³, a³d ⁴, b⁴c³, b³c⁴, b⁴d ³ b³d ⁴).
Множество элементов длины 8:
(a⁴c⁴, b⁴c⁴, a⁴d⁴, b⁴d⁴).

Обозначим число элементов во множестве q_i за q_i, i=1, 8, т.е.

q₁= 4 =q₈, q₂= 8 =q₇, q₃=12=q₆, q₄=16=q₅.

Рассчитаем число элементов второго слоя дерева, то есть когда строка S имеет только два символа. С точки зрения разделения ее по правилу 1 имеем две возможности: нет разделителей и один разделитель.
1. Нет разделителей. Тогда число элементов равно 2q₂=2·8=16 (2 класса)
2. Один разделитель. Тогда число элементов равно 2q₁·1q₁=2· 4· 4=32 (первый элемент может быть из любого класса, следовательно, имеем две возможности, второй элемент должен быть из другого класса, следовательно, имеем одну возможность).
Итак, имеем на втором слое 16 + 32 = 48 элементов.

Обобщим эту идею на большее число ходов.

Число различных состояний кубика, после того как сделано N (N=0) ходов меньше или равно чем 2∑(q₁ⁿ¹…q₈ⁿ⁸)(n₁ + … + n₈)! / (n₁!...n₈!),

^n1..n8

где 2- число выборов класса, который будет первым,
q₁ⁿ¹…q₈ⁿ⁸ – число вариантов для разделённой конкретным образом строки
(n₁ + … + n₈)! / (n₁!...n₈!) – число вариантов деления строки при фиксированных
n₁, ..., n_8.

Доказательство. Зафиксируем длину последовательности n≤N.
Если n=0, то очевидно имеем только один вариант - это начальная позиция. Далее будем считать, что n0. Пусть имеем строку S=(s₁, ... , s_n). Разделим ее по вышеуказанному правилу. После этого получатся последовательности длины 1, .., 8. Обозначим число последовательностей длины 1 за n₁, число последовательностей длины 2 за n₂,
…, длины 8 за n₈. Заметим, что 1n_{1 +} 2n_{2 +} … + 8n₈ = n. Число различных вариантов деления строки S при фиксированных n₁, … + n₈ равно
(n₁ + … + n₈)! / (n₁!...n₈!). Вычислим число различных вариантов при фиксированных n₁, …, n₈ и фиксированных разделителях. Для фиксированных n₁, …, n₈, фиксированных разделителях, но различных разбиений, например, S=[s₁][s₂][s₃s₄][s₅s₆][s₇s₈s₉s₁₀], S=[s₁s₂][s₃][s₄][s₅s₆][s₇s₈s₉s₁₀], ... , S=[s₁s₂s₃s₄][s₅s₆][s₇s₈][s₉][s₁₀], будем иметь равное число элементов. При фиксированных разделителей: для подстрок длины 1 число вариантов надо умножить на q₁, для подстрок длины 2 на q₂ и так далее. Итак, надо домножить на коэффициент q₁ⁿ¹…q₈ⁿ⁸. Но еще осталась свобода в выборе классов. Для первой подстроки имеем 2 варианта, для второй и последующих строк имеем только один вариант. Итак число вариантов надо домножить на два. Так получим конечную формулу 2∑(q₁ⁿ¹…q₈ⁿ⁸)(n₁ + … + n₈)! / (n₁!...n₈!) .
^n1..n8

Проведём вычисления по полученной формуле:

N₁=2q₁=8,

N₂=2(q₂ + q₁²)=2(8 + 16)=48,

N₃=2(q₃ + q₁³ + 2q₁q₂)=2(12 + 64 + 64)=280,

N₄=2(q₄ + q₁⁴ + 2q₁q₃ + q₂² + 3q₁²q₂)=1632,

N₅=2(q₅ + q₁⁵ + 2q₁q₄ + 2q₂q₃ + 3q₁²q₃ + 3q₁q₂² + 4q₁³q₂)=9504,

N₆=2(q₆ + q₁⁶ + 2q₁q₅ + 2q₂q₄ + 6q₁²q₂² + 5q₁⁴q₂ + q₄q₁² + 4q₃q₁³ + q₂³ + q₃² +
+ 3q₁q₂q₃)=53 048.

…

Количество новых вариантов на фиксированном шаге дерева:

№	Практические данные			Теорети-ческие результаты
	компьютер-ные данные	обработка 1	обработка 2
0	1 0	1 = 1 0	1 + 0 = 1	1
1	7 0	7 + 1 = 8 0	8 + 0 = 8	8
2	41 0	41 + 7 = 48 0	48 + 0 = 48	48
3	239 0	239 + 41 = 280 0	280 + 0 = 280	280
4	1368 24	1368 + 239 = 1607 24	1607 + 24 = 1631	1632
5	7672 304	7672 + 1368 = 9040 304	9040 + 304 = 9344	9504
6	42201 2531	42201 + 7672 = 49873 2531	49873 + 2531 = 52404	53048

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

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

С помощью программы, осуществляющей построение операторов перебором и запрещающей строить операторы по правилам, приводящим к повторам, было получено дерево состояний головоломки. Если не сделаем ходов, то получим только 1 позицию, если сделаем один ход, то получим 8 различных позиций, ...

Как было написано ранее, всего состояний очень много. Поэтому приводится статистику сложности позиции, то есть число позиций, чтобы распутать которые достаточно ровно 1, 2, ... хода:

слой	новые состояния	неучтённые повторы
0	[1]	0
1	[7]	0
2	[41]	0
3	[239]	0
4	[1 368]	24
5	[7 672]	304
6	[42 201]	2 531
7	[228 121]	17 463
8	…

В первой колонке таблицы указан номер слоя N, то есть сколько ходов было сделано, вторая колонка показывает, сколько различных позиций было получено, если было сделано не более чем N ходов, третья колонка показывает число неучтённых повторов N-ном слое.

Заметим, что каждый неучтённый повтор - тоже результат. Два оператора, дающие одно и то же состояние, приводят к нахождению новой нетривиальной тождественной перестановки.

Начиная с седьмого хода число повторов становится значительным. Это объясняется тем, что количество состояний головоломки конечно. Теперь повторы не представляют уже интереса, а замечательны получаемые новые состояния. Число их становится всё меньше с каждым шагом. Эти состояния получаются у разгадывателей головоломки очень редко. Теперь можно приблизиться к созданию новых интересных задач головоломки или найти решение уже существующих. Если заметить какую-нибудь закономерность в расположении кубиков и сформулировать её кратко, то получится новая задача головоломки.

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

Можно рассматривать группy преобразований головоломки с системой образующих из двух операторов: F и T. Она включает в себя предыдущую группу преобразований как подгруппу, так как даёт те же перестановки плюс их композиции с поворотами матрицы.

Для тех, кто хочет решить одну или несколько задач головоломки, не обязательно строить дерево состояний головоломки. Достаточно провести следующие рассуждения и воспользоваться следующим алгоритмом.

Алгоритм нахождения минимального решения некоторой задачи головоломки Харриса. Составим компьютерную программу, для этого заметим, что группа всех преобразований головоломки является образованной подстановками F и T. Тогда, чтобы найти комбинацию операций F и T, переводящую головоломку из начального положения в удовлетворяющее требованию задачи, надо найти произведение всех возможных комбинаций подстановок из F и T, результатом которых будет подстановка, описывающая конечное положение.

T задает элементарную операцию вращения трёх кубиков по часовой стрелке, но с равной вероятностью должен в комбинацию решения входить оператор S=T ⁸ элементарного вращения по часовой стрелке. Оказывается выгодней составить комбинации из трёх подстановок S, F, T. Чтобы получить оператор, дающий интересующее нас состояние головоломки, организуем перебор операторов по порядку. Сначала упорядочим всевозможные операторы. Введём соответствие между числом, записанным в позиционной троичной системе счисления, и оператором. Цифрами числа будут 0, 1, 2, операторы, представляющие собой композиции из F, T и S, будут записываться через F, T, S, начиная с того оператора, который должен выполняться первым. 0 соответствует F, 1 соответствует T, 2 соответствует S. Первым, минимальным, числом берётся 1 – это соответствует оператору T. Перебор осуществляется прибавлением единицы к числу в троичной системе счисления. И так до тех пор, пока оператор не будет строить из начальной ситуации искомую. Пример соответствия числа и оператора:
1 0 2 2 0 0 1 0 2
T F S S F F T F S.

Целесообразно несколько дописать этот алгоритм, используя свойства операторов так, чтобы существенно сократить сам процесс перебора перестановок.

Свойства операторов.

1. T и S – взаимно обратные, поэтому в строке перестановки недопустимо, чтобы после буквы T шла буква S, после S шла буква T.

2. Порядок подстановки T равен 9, тогда T ⁹=E, порядок подстановки S равен 9, тогда S ⁹=E, порядок подстановки F равен 4, тогда F ⁴=E. Поэтому подряд одна и та же подстановка может быть записана такое число раз, которое меньше её порядка.

3. T ⁵ = S ⁴, S ⁵ = T ⁴, поэтому в строке будем допускать не более четырёх одинаковых символов T или S подряд.

Упрощения: Перебираем все цифры. Если встречаем 12, то заменим на 22; если *21 - на 002. При этом все предыдущие цифры обнуляем.

Если встречаем 22222, то их и все предыдущие обнуляем, а следующий разряд увеличиваем на 1. Если встречаем 11111, то их заменяем на 00002 и все предыдущие заменяем на 0. Если встречаем 0000, то все предыдущие цифры обнуляем, а затем все рассмотренные цифры, стоящие на местах, кратным 4, заменяем на 1.

Далее рассмотрим формулировки задач, обозначения, алгоритмы решений.

Первая задача. Классическая головоломка Харриса

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

При записи решения будем пользоваться сокращёнными обозначениями:

F – поворот кубика на 90^о по часовой стрелке.

U – вперёд, от себя

D – назад, на себя

L – влево

R – вправо.

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

1). Рассмотрим операторы (TFTF ³)⁵ и (TF)¹⁴F ².

Решение (TFTF ³)⁵ F ² (TFTF ³)⁵ (TF)¹⁴F ² F (TF)¹⁴ состоит из 180 ходов.

Другой способ. Если использовать оператор (TFTF ²SF ³SF ²)⁴, то получим решение (TFTF ²SF ³SF²)⁴ F((TF)¹⁴F²)², состоящее из 108 ходов.

Минимальное решение, полученное на компьютере, состоит из 36 ходов и имеет вид: URDL LDR RUL DLUR DRUL DLU URD RULD RDLU LDRU.
T F ² S F ³ S F T ³ S F T F T F T F T F S

Вторая задача. Модифицированная головоломка Харриса

Кубики раскрашены так, что, когда они расставлены на матрице и центральная клетка свободна, все видимые грани окрашены в красный цвет, а все невидимые грани в чёрный. Требуется перекатить кубики так, чтобы все красные грани стали невидимыми, а все чёрные грани – видимыми, и центральная клетка снова была пустой.

Рассмотрим оператор T ³F T ³F² S ²F T ²F S ³F ² T ²F T- с помощью четырёхкратного его применения можно перевернуть все угловые кубики. Рассмотрим далее оператор (TF)¹⁴F ². С помощью четырёхкратного его применения можно перевернуть все срединные кубики.

Другой способ. Рассмотрим оператор (TFTF ³TFT ²)³T ³((TFTF ³)⁵F)⁴ – переворачивает все угловые кубики. Оператор S ⁴ F ²T FT FS ² F ³S ² F ³S FT FS ³ переворачивает все срединные кубики, оставляя угловые в прежнем положении.

Минимальное решение, полученное на компьютере, состоит из 70 ходов и имеет вид:
RUL LDR DRUL ULDR DRUL DLUR ULDR RDLU LDRU RDLU RDLU
S F ³ S F S F ³ S F ² S F T F S F T F S F ³ T T

RDLU LURD RULD RULD LURD RULD LDR RUL.
T F ² T F S S F ³ T F S F ² S F ³ S

Третья задача. Задача в четырёх красках

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

Решение (SF)⁴S ²(FS)⁴(F (TF)⁷F)³(SF)⁴SF ³S(FS)⁴F ²(SF)⁴SF ³S(FS)⁴(TF)¹⁴F ³(TF)¹⁴ - 342 хода.

Другой способ. Рассмотрим (T ³ FS FT (FS ²)⁴ FT FS FT ³ F)² - переворачивает угловые кубики разом, не нарушая картины со срединными кубиками. Рассмотрим далее оператор S ⁴ F ²T FT FS ² F ³S² F ³S FT FS ³ – он переворачивает все срединные кубики, оставляя угловые в прежнем положении. Комбинация этих операторов является решением. Около 200 ходов.

Четвёртая задача.

Имеется восемь кубиков, раскрашенных как в классической головоломке Харриса (то есть с раскрашенными двумя противоположными гранями в красный и синий цвета, все боковые грани – в голубой цвет). Произвольным образом расставляем их на матрице 3х3, оставляя пустой центральную клетку. Требуется перевернуть кубики так, чтобы все они встали либо красными, либо синими гранями вверх.

1) Устанавливаем все угловые кубики цветными гранями вверх (всё равно, синими или красными). Для этого используем операторы T ³ и S ³, которые действуют следующим образом:

T S

Требуемое расположение углового кубика может быть получено и раньше (после применения T ², S ², T, S), однако с помощью T ³ и S ³ получение его гарантировано).

2) На этом этапе устанавливаем все серединные кубики цветными гранями вверх.

Когда цветные грани серединного кубика скрыты гранями соседних угловых кубиков, применяем оператор T (F T F ³ S) , который действует следующим образом:

Когда цветные грани серединного кубика открыты, применяем оператор
T ² (F T ² F ³ S ²):

3)Устанавливаем все угловые кубики так, что бы все верхние грани угловых кубиков были одного цвета. Для этого используем оператор Y = T FT (F ³S)² F ²S (FT)²

F ²T, который действует следующим образом:

или, например, оператор
Y₁ = T ² (FS ² FS FS)² S ², который действует также.

4) Устанавливаем серединные кубики так, чтобы все верхние грани были одного цвета. Для этого используем оператор C=(TF)¹⁰F ².

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

Порядки операторов

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

Определим, какие порядки могут иметь операторы рассматриваемой группы. Примеры:

оператор	порядок
agchbgdh	1		acehdd	8		acg	21
agagagagag	2		a	9		aacfaf	24
aaa	3		ag	10		agaafg	36
aagbce	4		aahcec	12		aaacfg	42
agag	5		ach	14		aagcec	45
afae	6		ah	15		aahceh	90
agcg	7		aaeafg	18

Все порядки операторов являются делителями порядка рассматриваемой группы операторов, а следовательно, являются делителями мощности множества состояний головоломки. (Рассматриваемая группа преобразований является подгруппой группы всех перестановок на множестве M, значит, её мощность является делителем числа
8!· (4!)⁸.) Рассмотрим произвольную перестановку α группы G. Она раскладывается в произведение циклов. Её порядок, следовательно, не превышает НОК(чисел до 48), где 48 – число граней. Но это очень грубая оценка. Заметим, что порядок k перестановки α является делителем порядка группы G, который в свою очередь является делителем числа 24⁸·8!, как было указано ранее. Тогда k – делитель числа 24⁸8! = 3⁴·2³¹·7·5.

Таким образом, в каноническом разложении k может быть не более одной 7, одной 5, нескольких 3 и 2 и только. Троек может быть не более двух согласно следующим рассуждениям. В разложении перестановки на циклы может быть не более 24 пар граней или граней, входящих в один цикл, при этом, если пары граней не входят в цикл, то они образуют аналогичный цикл той же длины. Поэтому 27 не может быть длиной никакого цикла в разложении перестановки. Таким образом, порядок произвольной перестановки не превышает 7·5·3²·2^m и является делителем этого числа
(m– натуральное число, не превышающее 24). Будем доказывать, что никаких других порядков операторов нет.

Итак, имеем в распоряжении множители произведения 7·5·3²·2^m. Имеем в наличии
48 граней, 8 кубиков. Используем теорему: порядок перестановки, которая раскладывается в произведение циклов длиною k₁, k₂, ... , k_m есть НОК (k₁, k₂,... , k_m).

Используем то, что если парные грани не входят в один цикл, то они входят в аналогичные друг другу циклы. Используем то, что в одном кубике могут переставляться 0, 2, 3 пары граней, но не 1 пара.

Предположим, в разложении перестановки на циклы имеется цикл длины 9. Тогда имеется ещё один цикл длины 9 из противоположных граней. Аналогично со всеми циклами нечётной длины. Как на кубиках мог получиться цикл длины 9? Кубиков всего восемь. Количество граней нечётно. Цикл длины 9 мог получиться только в результате циклической перестановки трёх кубиков, когда в каждом кубике изменилось положение всех трёх пар граней. Например, перестановка (1ul 8lu 2ld 3rd 6db 7ru 4bd 5bl).

Оставшиеся пять кубиков могут давать только множители 5, 10 (это рассмотрено далее). Три кубика также могли вместо двух 9–циклов давать один цикл длины 18, когда в обе грани в паре входят в один цикл. Других вариантов получения множителя 9 получается, что нет.

Пусть в разложении перестановки имеется 7–цикл. Он мог получиться, когда семь кубиков образуют циклическую перестановку. Однако, вместо шести циклов длины
7 могло быть три цикла длины 14, либо два цикла длины 21. Других вариантов получения множителя 7 нет. Заметим, что остаётся один кубик, и он не может сам собой менять положения, то есть не может давать другие множители.

Как может получиться множитель 5? Пять кубиков могут образовывать шесть циклов длины 5, либо три цикла длины 10, либо два цикла длины 15. Оставшиеся три кубика могут давать множители: 1, 9.

Перестановки порядков 3 и 2 существуют, их можно получить как третью/ вторую степень перестановок порядков 9/ 4. Множители 3, 2 легко могут возникать в циклах, дающих другие множители.

Максимальный порядок, следовательно, 90, и соответствует перестановке типа
, заметим, что сумма 9 + 9 + 10 + 10 + 10 = 48 – равна числу граней.

Эти результаты справедливы для группы всех перестановок на множестве головоломки. Заметим, в рассматриваемой группе операторов можно указать операторы любого из возможных порядков.

У всех операторов порядки конечны и легко вычисляются вручную путём разложения на циклы. Но вспомним, что при повторении одного и того же оператора несколько раз для получения новых состояний делать это надо столько раз, на сколько указывает порядок оператора. Чтобы проделать все это на компьютере, язык подстановок в чистом виде не подходит, так как там сложен. Но полученные результаты о порядках подстановок дают хороший способ: нужно повторять оператор до тех пор, пока не получится повтор, и известно, что число повторений не превысит максимального порядка, то есть число 90, которое для компьютера достаточно мало.

Приложения

Компьютерная программа.

unit UMyThread;

interface

uses

Classes, sysutils, windows;

type

TMyThread = class(TThread)

private

{ Private declarations }

protected

TmpNUm:int64;

procedure inicia_a;

procedure svob;

procedure rrr;

procedure lll;

procedure ddd;

procedure uuu;

procedure ffff;

procedure elt(r:char);

procedure Gen;

procedure Sw;

procedure Zapek;

function fnum(r:char):integer;

procedure GenerMas(r:char);

procedure Execute;override;

procedure WywEk;

procedure WywMem;

end;

var

a1, a2:array[1..250000, 1..3, 1..3, 1..7] of char;

L1, L2:array[0..250000] of char;

N1:integer;

M1, M2:array[0..250000] of integer;

Op_r1, Op_r2:array[0..250000] of string;

u2, w2, u, v, w, x, z:integer;

q0, q1, q2, q3: array[0..50]of integer;

qqq, pov, i1, j1:integer;

s: string;

q:integer;

implementation

uses Umain;

procedure TMyThread.inicia_a;

var

z, i, j, k:integer;

begin

z:=0;

for i:=1 to 3 do

for j:=1 to 3 do

begin

a2[z, i, j, 1]:='u';

a2[z, i, j, 2]:='d';

a2[z, i, j, 3]:='l';

a2[z, i, j, 4]:='r';

a2[z, i, j, 5]:='f';

a2[z, i, j, 6]:='b';

end;

a2[z, 1, 1, 7]:='1';

a2[z, 1, 3, 7]:='3';

a2[z, 3, 1, 7]:='6';

a2[z, 3, 3, 7]:='8';

a2[z, 1, 2, 7]:='2';

a2[z, 2, 1, 7]:='4';

a2[z, 2, 3, 7]:='5';

a2[z, 3, 2, 7]:='7';

for k:=1 to 7 do

a2[z, 2, 2, k]:='o';

for i:=1 to 3 do

for j:=1 to 3 do

for k:=1 to 7 do

a1[z, i, j, k]:=a2[z, i, j, k];

end;

procedure TMyThread.svob;

var

i, j, k:integer;

begin

for i:= 1 to 3 do

for j:= 1 to 3 do

if a2[v, i, j, 1]='o'

then

begin

i1:=i;

j1:=j;

end;

end;

procedure TMyThread.rrr;

var

k:integer;

begin

svob;

a2[v, i1, j1, 1]:=a2[v, i1, j1-1, 3];

a2[v, i1, j1, 2]:=a2[v, i1, j1-1, 4];

a2[v, i1, j1, 3]:=a2[v, i1, j1-1, 2];

a2[v, i1, j1, 4]:=a2[v, i1, j1-1, 1];

a2[v, i1, j1, 5]:=a2[v, i1, j1-1, 5];

a2[v, i1, j1, 6]:=a2[v, i1, j1-1, 6];

a2[v, i1, j1, 7]:=a2[v, i1, j1-1, 7];

for k:=1 to 7 do

begin

a2[v, i1, j1-1, k]:='o';

end;

end;

procedure TMyThread.lll;

var

k:integer;

begin

svob;

a2[v, i1, j1, 1]:=a2[v, i1, j1 + 1, 4];

a2[v, i1, j1, 2]:=a2[v, i1, j1 + 1, 3];

a2[v, i1, j1, 3]:=a2[v, i1, j1 + 1, 1];

a2[v, i1, j1, 4]:=a2[v, i1, j1 + 1, 2];

a2[v, i1, j1, 5]:=a2[v, i1, j1 + 1, 5];

a2[v, i1, j1, 6]:=a2[v, i1, j1 + 1, 6];

a2[v, i1, j1, 7]:=a2[v, i1, j1 + 1, 7];

for k:=1 to 7 do

begin

a2[v, i1, j1 + 1, k]:='o';

end;

end;

procedure TMyThread.uuu;

var

k:integer;

begin

svob;

a2[v, i1, j1, 1]:=a2[v, i1 + 1, j1, 5];

a2[v, i1, j1, 2]:=a2[v, i1 + 1, j1, 6];

a2[v, i1, j1, 3]:=a2[v, i1 + 1, j1, 3];

a2[v, i1, j1, 4]:=a2[v, i1 + 1, j1, 4];

a2[v, i1, j1, 5]:=a2[v, i1 + 1, j1, 2];

a2[v, i1, j1, 6]:=a2[v, i1 + 1, j1, 1];

a2[v, i1, j1, 7]:=a2[v, i1 + 1, j1, 7];

for k:=1 to 7 do

begin

a2[v, i1 + 1, j1, k]:='o';

end;

end;

procedure TMyThread.ddd;

var

k:integer;

begin

svob;

a2[v, i1, j1, 1]:=a2[v, i1-1, j1, 6];

a2[v, i1, j1, 2]:=a2[v, i1-1, j1, 5];

a2[v, i1, j1, 3]:=a2[v, i1-1, j1, 3];

a2[v, i1, j1, 4]:=a2[v, i1-1, j1, 4];

a2[v, i1, j1, 5]:=a2[v, i1-1, j1, 1];

a2[v, i1, j1, 6]:=a2[v, i1-1, j1, 2];

a2[v, i1, j1, 7]:=a2[v, i1-1, j1, 7];

for k:=1 to 7 do

begin

a2[v, i1-1, j1, k]:='o';

end;

end;

procedure TMyThread.ffff;

var

i, j, k:integer;

gg:array[1..3, 1..3, 1..7] of char;

begin

z:=0;

for i:=1 to 3 do

for j:=1 to 3 do

for k:=1 to 7 do

gg[i, j, k]:=a2[z, i, j, k];

for i:=1 to 3 do

for j:=1 to 3 do

begin

a2[z, i, j, 1]:=gg[j, 4-i, 1];

a2[z, i, j, 2]:=gg[j, 4-i, 2];

a2[z, i, j, 3]:=gg[j, 4-i, 6];

a2[z, i, j, 4]:=gg[j, 4-i, 5];

a2[z, i, j, 5]:=gg[j, 4-i, 3];

a2[z, i, j, 6]:=gg[j, 4-i, 4];

a2[z, i, j, 7]:=gg[j, 4-i, 7];

end;

end;

procedure TMyThread.elt(r:char);

begin

case r of

'a':begin uuu; rrr; ddd; lll; end;

'b':begin rrr; uuu; lll; ddd; end;

'c':begin ddd; lll; uuu; rrr; end;

'd':begin lll; ddd; rrr; uuu; end;

'e':begin rrr; ddd; lll; uuu; end;

'f':begin ddd; rrr; uuu; lll; end;

'g':begin lll; uuu; rrr; ddd; end;

'h':begin uuu; lll; ddd; rrr; end;

end;

end;

procedure TMyThread.Sw;

begin

s:=a2[v, 1, 1, 7] + a2[v, 1, 1, 1] + a2[v, 1, 1, 3] + ' ' + a2[v, 1, 2, 7] + a2[v, 1, 2, 1] + a2[v, 1, 2, 3] + ' ' + a2[v, 1, 3, 7] + a2[v, 1, 3, 1] + a2[v, 1, 3, 3] + ' ' + a2[v, 2, 1, 7] + a2[v, 2, 1, 1] + a2[v, 2, 1, 3] + ' ' + a2[v, 2, 3, 7] + a2[v, 2, 3, 1] + a2[v, 2, 3, 3] + ' ' + a2[v, 3, 1, 7] + a2[v, 3, 1, 1] + a2[v, 3, 1, 3] + ' ' + a2[v, 3, 2, 7] + a2[v, 3, 2, 1] + a2[v, 3, 2, 3] + ' ' + 2[v, 3, 3, 7] + a2[v, 3, 3, 1] + a2[v, 3, 3, 3];

end;

procedure TMyThread.GenerMas(r:char);

begin

case r of

'a': begin if M1[w]4 then begin L2[v]:='a';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='c'; Gen; L2[v]:='d'; Gen;

L2[v]:='e'; Gen; L2[v]:='f'; Gen;

L2[v]:='g'; Gen; L2[v]:='h'; Gen; end;

'b': begin if M1[w]4 then begin L2[v]:='b';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='c'; Gen; L2[v]:='d'; Gen;

L2[v]:='e'; Gen; L2[v]:='f'; Gen;

L2[v]:='g'; Gen; L2[v]:='h'; Gen; end;

'e': begin if M1[w]4 then begin L2[v]:='e';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='a'; Gen; L2[v]:='b'; Gen;

L2[v]:='c'; Gen; L2[v]:='d'; Gen;

L2[v]:='g'; Gen; L2[v]:='h'; Gen; end;

'f': begin if M1[w]4 then begin L2[v]:='f';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='a'; Gen; L2[v]:='b'; Gen;

L2[v]:='c'; Gen; L2[v]:='d'; Gen;

L2[v]:='g'; Gen; L2[v]:='h'; Gen; end;

'c': begin if M1[w]4 then begin L2[v]:='c';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='e'; Gen; L2[v]:='f'; Gen;

L2[v]:='g'; Gen; L2[v]:='h'; Gen; end;

'd': begin if M1[w]4 then begin L2[v]:='d';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='e'; Gen; L2[v]:='f'; Gen;

L2[v]:='g'; Gen; L2[v]:='h'; Gen; end;

'g': begin if M1[w]4 then begin L2[v]:='g';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='a'; Gen; L2[v]:='b'; Gen;

L2[v]:='c'; Gen; L2[v]:='d'; Gen; end;

'h': begin if M1[w]4 then begin L2[v]:='h';

Gen; M2[v-1]:=M2[v-1] + 1; end;

L2[v]:='a'; Gen; L2[v]:='b'; Gen;

L2[v]:='c'; Gen; L2[v]:='d'; Gen; end;

end;

end;

function TMyThread.fnum(r:char):integer;

begin

case r of

'u': fnum:=1;

'd': fnum:=2;

'l': fnum:=3;

'r': fnum:=4;

'f': fnum:=5;

'b': fnum:=6;

end;

end;

procedure TMyThread.WywEk;

var

num: integer;

begin

num:=(StrToInt(a2[v, 1, 1, 7])-1)*6 + fnum(a2[v, 1, 1, 1]);

Form1.Ek[num].Lines.Add(s);

q1[num]:=q1[num] + 1;

end;

procedure TMyThread.WywMem;

var

num: integer;

begin

Op_r2[v]:=Op_r1[w] + L2[v];

num:=(StrToInt(a2[v, 1, 1, 7])-1)*6 + fnum(a2[v, 1, 1, 1]);

Form1.Memo[num].Lines.Add(s);

Form1.Cifo[num].Lines.Add(Op_r2[v]);

Form1.Edit1.Text:=IntToStr(v);

q0[num]:=q0[num] + 1;

q:=q + 1;

Zapek;

M2[v]:=M1[w]; v:=v + 1;

end;

procedure TMyThread.Zapek;

var

v1, i, j, k:integer;

begin

z:=0;

for i:=1 to 3 do

for j:=1 to 3 do

for k:=1 to 7 do

a2[z, i, j, k]:=a2[v, i, j, k];

v1:=v; v:=0; ffff; Sw;

Synchronize(WywEk); v:=v1;

v1:=v; v:=0; ffff; Sw;

Synchronize(WywEk); v:=v1;

v1:=v; v:=0; ffff; Sw;

Synchronize(WywEk); v:=v1;

end;

procedure TMyThread.Gen;

var

qi, num, p, i, j, k:integer;

begin

Form1.komb.Lines[u2]:= Form1.komb.Lines[u2] + L2[v]; w2:=w2 + 1;

if w2=248 then begin Form1.komb.Lines.Add(''); u2:=u2 + 1; w2:=0; end;

// u2- номер строчки в Мемо

for i:=1 to 3 do

for j:=1 to 3 do

for k:=1 to 7 do

a2[v, i, j, k]:=a1[w, i, j, k];

elt(L2[v]); Sw;

num:=(StrToInt(a2[v, 1, 1, 7])-1)*6 + fnum(a2[v, 1, 1, 1]);

p:=1;

for i:=1 to q0[num]-1 do if s=Form1.Memo[num].Lines[i] then begin qi:=i; p:=0; end;

for i:=1 to q1[num]-1 do if s=Form1.ek[num].Lines[i] then begin qi:=i; p:=0; end;

if p=1 then Synchronize(WywMem) else begin Form1.Repe.Lines.Add

(s + ' ' + IntToStr(u) + ' ' + Op_r1[w] + L2[v] + ' ' + Form1.Cifo[num].Lines[qi]); pov:=pov + 1;

Form1.Cif.Text:=IntToStr(pov); end;

end;

procedure TMyThread.Execute;

var

i, j, k, z:integer;

begin

FreeOnTerminate:=true;

inicia_a;

pov:=0;

q:=1;

u:=0;

v:=0;

u2:=1;

w2:=1;

N1:=1;

Form1.komb.Lines.Add('');

Form1.tabl0.Lines.Add('1 1 0');

Form1.Cifo[1].Lines.Add('');

Sw; Form1.Memo[1].Lines.Add(s); q0[1]:=1; ffff;

Sw; Form1.Ek[31].Lines.Add(s); q1[31]:=1; ffff;

Sw; Form1.Ek[43].Lines.Add(s); q1[43]:=1; ffff;

Sw; Form1.Ek[13].Lines.Add(s); q1[13]:=1; ffff;

v:=1;

for i:=1 to 3 do

for j:=1 to 3 do

for k:=1 to 7 do

a2[v, i, j, k]:=a1[v-1, i, j, k];

elt('a'); Sw; Form1.Memo[1].Lines.Add(s); q0[1]:=q0[1] + 1; q:=q + 1;

Op_r2[v]:='a'; Form1.Cifo[1].Lines.Add(Op_r2[v]);

for i:=1 to 3 do

for j:=1 to 3 do

for k:=1 to 7 do

a1[v, i, j, k]:=a2[v, i, j, k];

L1[1]:='a';

M1[1]:=1;

Op_r1[1]:=Op_r2[1];

repeat begin

EnterCriticalSection(form1.cs);

v:=1;

for w:=1 to N1 do

begin GenerMas(L1[w]); end;

N1:=v-1;

for w:=1 to N1 do

begin

L1[w]:=L2[w];

M1[w]:=M2[w];

Op_r1[w]:=Op_r2[w];

for i:=1 to 3 do

for j:=1 to 3 do

for k:=1 to 7 do

a1[w, i, j, k]:=a2[w, i, j, k];

end;

for i:=1 to 48 do begin

Form1.Memo[i].Lines.Add(IntToStr(u));

Form1.Cifo[i].Lines.Add(IntToStr(u));

q0[i]:=q0[i] + 1; end;

Form1.tabl0.Lines.Add(IntToStr(u + 2) + ' ' + IntToStr(N1) + ' ' + IntToStr(pov));

u:=u + 1;

u2:=u2 + 3;

Form1.komb.Lines.Add(IntToStr(u));

Form1.komb.Lines.Add(''); Form1.komb.Lines.Add('');

LeaveCriticalSection(form1.cs);

end until q=483860; end;

end.

Список литературы

1. Гарднер М. Путешествие во времени, М.: Мир, 1989г.

2. Гроссман И., Магнус В. Группы и их графы: пер. с англ. – М.: Мир, 1971г.

3. Калужнин Л.А., Сущанский В.И. Преобразования и перестановки: пер. с укр. – М.: Наука, 1979г.

4. Кофман А. Введение в прикладную комбинаторику: пер. с фр. – М.: Наука, 1975г.

5. Курош А.Г. Курс высшей алгебры. М., 1962г.

6. Романовский И.В. Дискретный анализ. – СПб.: Невский Диалект, 2003г.

28