Словарик

17 февраля 2012

От автора

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

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

Классификация

См. также: Википедия (Головоломка); Wikipedia (Puzzle, Mechanical puzzle, Combination puzzle, Sliding puzzle)

Головоломка – это некоторая проблема, задача, смысл которой заключается в её решении. Примерами головоломок являются кроссворды, пазлы, чайнворды.

Механическая головоломка – головоломка, состоящая из определённого количества составных частей. В некоторых головоломках эти части соединены механически; в других цель заключается в соединении частей в определённом порядке (напр., полимино).

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

Одна из наиболее популярных комбинаторных головоломок – кубик Рубика.

Головоломка со скользящими элементами – особый вид комбинаторной головоломки. Обычно плоские элементы произвольной формы находятся в ограниченном пространстве (боксе, лотке, коробке, доске). Элементы переупорядочиваются путём перемещения в пределах коробка. Цель заключается в том, чтобы упорядочить элементы определённым образом. Пример – Sokoban.

Скользяшки

Головоломки со скользящими блоками, головоломки со скользящими плитками, "скользяшки" – подкласс головоломок со скользящими элементами. Все подвижные элементы (блоки, или плитки) могут перемещаться независимо друг от друга, но в большинстве случаев не могут вращаться. Извлечение плиток из коробка запрещено. Плитки перемещаются самостоятельно; головоломка "Сокобан" не является скользяшкой, так как в ней способностью перемещаться самостоятельно обладает только один элемент, который и толкает остальные. Вращение отдельных плиток (без извлечения их из коробка) допускается только в том случае, если это оговорено в описании головоломки. Плитки могут иметь любую геометрическую форму (квадраты, треугольники, круги, прямоугольники, полимино и др.) Коробок (пространство, вмещающее плитки) также может иметь произвольную форму. Обычно за один ход перемещается только одна плитка. Некоторые "скользяшки" содержат препятствия, или неподвижные плитки. Головоломка может быть трёхмерной.

"Скользяшки" могут быть классифицированы по форме плиток и коробка.

Плитка, коробок, клетка, пустая клетка

7

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

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

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

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

WHITE
BLACK
Black & White

В головоломке "Black & White" доска представляет собой многосвязное додекамино (12-мино) с одной пустотой. Имеется 10 плиток и 12 клеток, две из которых – пустые.

Однако доска этой головоломки может рассматриваться, например, как прямоугольник 5 × 3 с тремя препятствиями (неподвижными плитками) в клетках с координатами (2,1), (2,3), (2,5). Таким образом, можно полностью избавиться от препятствий, если допустить доски в форме произвольных многосвязных полимино.

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

В головоломке, основанной на произвольном графе, клетки являются вершинами. Пустая клетка также называется незанятой вершиной.

Целочисленная головоломка m × n с плитками 1 × 1

Имеется некоторое количество плиток в форме квадратов 1 × 1 и прямоугольная доска высоты m и ширины n, где m и n – целые числа. Доска разбита на клетки 1 × 1.

У каждой клетки есть две координаты – горизонтальная и вертикальная. Четыре угловых клетки имеют координаты (1,1), (1,n), (m,1), (m,n).

При необходимости доска может быть разделена на m строк или n столбцов.

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

Количество плиток меньше количества клеток на доске; имеется по меньшей мере одна пустая клетка.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
15-головоломка,
или 4 × 4

Головоломка m × n

Целочисленная головоломка m × n с плитками 1 × 1, имеющая только одну пустую клетку, обычно называется просто головоломкой m × n. Когда m = n, головоломка m × n также называется (n2–1)-головоломкой.

Целочисленная головоломка с плитками 1 × 1

Имеется некоторое количество плиток, имеющих форму квадрата 1 × 1, и доска в форме произвольного полимино. Доска разделена на клетки 1 × 1. Имеется хотя бы одна пустая клетка.

Головоломка на произвольном графе

См. также: Jaap's Puzzle Page (Rotational Puzzles on Graphs), Cut The Knot

Целочисленная головоломка с плитками 1 × 1 может быть обобщена до головоломки, основанной на произвольном графе. Здесь клетки являются вершинами графа, а плитки – фишками, размещёнными на изображении графа на плоскости.

Данная разновидность головоломок была рассмотрена Ричардом Вильсоном в [3].

Целочисленная головоломка с прямоугольными плитками

В данном варианте разрешены любые прямоугольные плитки с целочисленными длиной и шириной. Доска по-прежнему имеет форму полимино.

Целочисленная прямоугольная головоломка

Доска и плитки имеют форму произвольных полимино.

Вещественная головоломка

Доска и плитки являются произвольными геометрическими фигурами произвольного действительного размера.

Определение хода

Связанная страница: Метрики.

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

  1. Перемещение одной плитки в любом направлении или по ломаной линии (определение №1 из [1]).
  2. Перемещение одной плитки в одном направлении. Каждое изменение направления перемещения плитки считается началом нового хода (определение №2 из [1]).
  3. Перемещение любого количества плиток вместе в любом одном направлении (определение №3 из [1]).
  4. Перемещение одной плитки в любом ортогональном направлении на расстояние, равное 1 (определение №4 из [1]). В этом случае последовательное перемещение одной и той же плитки в одном направлении считается за несколько ходов.
  5. Перемещение любого количества плиток вместе в одном и том же направлении, так же как и в варианте 3; однако, за один ход разрешается касаться только одной плитки. Эта плитка используется для того, чтобы "толкать" другие плитки, участвующие в ходе.

На головоломках m × n, подобных классической головоломке "Пятнашки", существует два естественных определения хода. В одном варианте, допускается перемещать одну плитку за ход; в другом варианте, допускается перемещать любое количество плиток в одном и том же направлении.

Конфигурация. Пространство состояний

Конфигурация головоломки, или состояние головоломки – просто некоторое расположение плиток на доске (в коробке).

Все конфигурации, которые могут быть получены путём последовательного выполнения ходов, называются достижимыми конфигурациями. Наоборот, все конфигурации, которые не могут быть получены без нарушения правил головоломки, называются недостижимыми конфигурациями. Например, конечная конфигурация "Пятнашек" достижима, в то время как конфигурация, в которой плитки 14 и 15 переставлены, недостижима.

Две заданные конфигурации A and B называются связанными, если существует последовательность ходов, которая переводит A в B. Если такой последовательности не существует, конфигурации называются несвязанными.

Любые две достижимые конфигурации связаны.
С другой стороны, две недостижимые конфигурации не обязательно связаны.

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

Множество всех достижимых конфигураций называется пространством состояний головоломки. Количество достижимых конфигураций равно мощности пространства состояний.

Начальная конфигурация

Начальная конфигурация может выбираться каждый раз случайным образом (напр., "Пятнашки") или определяться правилами головоломки (напр., Black & White).

Целевая конфигурация

Целевая конфигурация, или конечная конфигурация – конфигурация, по достижении которой головоломка считается решённой. Существует несколько способов задать целевую конфигурацию.

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

Во-вторых, можно задать положения некоторых плиток. Например, "Красная плитка 2 × 2 должна оказаться в верхнем левом углу". Расположение остальных плиток в конечной конфигурации не имеет значения.

В-третьих, можно определить некоторые свойства конечной конфигурации. Например, во многих "скользяшках" на поверхности плиток нанесены части изображения. Цель заключается в том, чтобы совместить все части и восстановить цельное изображение. Выяснение того, где должна находиться каждая из плиток, не является тривиальной задачей.

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

Классическая или с нуля?

Данный раздел относится к головоломке m × n.

Конфигурации могут записываться в тексте как последовательности чисел или букв на плитках. Для обозначения пустой клетки можно использовать 0.

В "Пятнашках", классическая целевая конфигурация выглядит следующим образом:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0

В исследованиях часто используется другая конечная конфигурация:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Первая конфигурация может быть названа классической или нуль-терминированной, а вторая – с нуля. Впрочем, эти названия не являются общепринятыми.

2 × 5
С нуля
3 × 4
Классическая
1 2 3 4 1 2 3 4
5 6 7 8 9 5 6 7 8
9 10 11

Разумеется, в качестве целевой можно выбрать любую другую конфигурацию. Некоторые "узоры" приведены на этой странице.

В общем случае, любая конфигурация головоломки m × n принадлежит к одному из m × n классов, в зависимости от пустой клетки. В каждом из этих классов можно выбрать представителя – одну конфигурацию, в которой плитки 1,2,...,(m × n – 1) расположены в порядке возрастания. Тогда произвольно выбранная конфигурация может быть перемаркирована таким образом, что она совпадёт с одним из представителей.

Трансформация

Данный раздел относится к целочисленной головоломке с плитками 1 × 1.

Трансформация на головоломке – это некоторый способ переупорядочить плитки на клетках. С точки зрения математики, это перестановка плиток (включая пустую плитку).

Легальная трансформация – трансформация, которая может быть выполнена без нарушения правил головоломки (без извлечения плиток из коробка). Наоборот, нелегальная трансформация – трансформация, которая может быть осуществлена только путём извлечения плиток из коробка.

Трансформация, которая является легальной в одной конфигурации, может быть нелегальной в другой конфигурации из-за того, что пустая клетка перемещается. Эта проблема не возникает в комбинаторных головоломках, подобных кубику Рубика, так как эти головоломки не содержат пустых клеток, и любой ход применим в любой достижимой конфигурации.

Ход может быть определён как элементарная легальная трансформация. Множество всех ходов головоломки имеет следующее свойство: любая легальная трансформация может быть представлена в виде последовательности ходов из этого множества.

Число Бога

Связанная страница: Алгоритм Бога и число Бога.

Две конфигурации A и B связаны, если существует последовательность ходов, переводящая A в B. Если на головоломке задана метрика, то расстояние между конфигурациями – наименьшее количество ходов в такой последовательности.

Число Бога головоломки с заданной метрикой и конечной конфигурацией – максимальное расстояние от цели до любой другой достижимой конфигурации.

Представление пространства состояний в виде графа

В математике графом называется абстрактное представление множества объектов, в котором некоторые пары объектов соединены связями. Объекты представлены в виде вершин, а связи – в виде рёбер.

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

Расстояние между двумя конфигурациями может быть определено как расстояние между соответствующими вершинами графа, т.е. длина кратчайшего пути, соединяющего эти вершины.

Представление пространства состояний головоломки в виде графа позволяет использовать ту же терминологию, что используется при изучении графов.

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

  1. Hordern, Edward A. (1986), "Sliding Piece Puzzles", Oxford Univ. Press, Series: Recreations in Mathematics Vol. 4
  2. Gallery of the Sequential Movement Puzzles
  3. Wilson, Richard M. (1974), "Graph puzzles, homotopy, and the alternating group", Journal of Combinatorial Theory. Series B 16: 86–96.
  4. Wikipedia, the free encyclopedia
  5. Википедия, свободная энциклопедия