О том как пятнашки представить в виде группы перестановок
(а точнее S(n²-1) × Cₙ × Cₙ)
Допустим вам захотелось представить пятнашки в виде группы перестановок. Но проблема: что и куда переставлять зависит от положения 0 (пустой клетки). И вообще, для классических пятнашек это сделать не получится. Но если допустить периодические гран условия (да, мы теперь живём на торе), то всё можно.
Для этого рассмотрим следующую конструкцию: для квадрата n×n заполним его n² элементами, 0 в левом верхнем углу (на рисунке это синий квадрат); дальше повторим как на рисунке строки и столбцы этого квадрата до (2n-1)×(2n-1); установим рамку в положение (0,0). Внутренности синего квадрата это как раз будет группа S(n²-1), а положение рамки по x и y это Cₙ × Cₙ.
Теперь если мы хотим поменять местами с 0 (пустышкой) соседний элемент, то: (i) двигаем в эту сторону рамку, (ii) внутри синего квадрата делаем циклические перестановки (внутри столбцов|строк), не трогая 0. Собственно, внутренности рамки это и будет состояние пятнашек, а мы только что описали их набором перестановок!
Давайте для наглядности выпишем генераторы для n=3. Всего будет (n²-1)+(n)+(n) элементов.
state: [1, 2, 3, 4, 5, 6, 7, 8,
0, 2, 1, 0, 2, 1]
right: [2, 1, 4, 5, 3, 7, 8, 6,
8+2, 8+0, 8+1, 11+0, 11+1, 11+2]
down: [4, 5, 6, 7, 8, 3, 1, 2,
8+0, 8+1, 8+2, 11+2, 11+0, 11+1]
и left, up получаются аналогично как обратные к right, down. Теперь чтобы сделать ход, нам достаточно применить заданную перестановку к набору элементов, независимо от положения пустышки.
// кстати, card(S_{n²}) = card(S_{n²-1} × C_n × C_n)