Гра в конфігурації: читайте про нову головоломку

Пропонуємо вам варіант ще однієї нової і захоплюючої гри, яка підійде як дітям, так і дорослим. На перший погляд, вона являє собою типову головоломку зі змінними початковими умовами типу кубика Рубіка, судоку або пасьянса. Однак її можливості значно ширші.


Гра в конфігурації може використовуватися як конструктор для різноманітних красивих конфігурацій - аналогічно грі (точніше, клітинному автомату) «Життя», - а також для створення цікавих математичних завдань.


Правила гри дуже прості. На «нескінченному» аркуші паперу в клітку задається довільна початкова конфігурація з кінцевого числа хрестиків, яку назвемо затравкою. Приклад затравки представлений на рис. 1.

Малюнок 1

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

До затравки послідовно додаються нові хрестики відповідно до наступних двох правил.

  1. Кожен хрестик повинен утворювати з уже виставленими хоча б один ряд з трьох хрестиків, що стоять поруч, по вертикалі, горизонталі або діагоналі. З цього правила випливає, що не можна виставляти ізольований хрестик, а також вибудовувати ряд, що складається лише з двох хрестиків, що стоять поруч.
  2. Забороняється ставити хрестик, якщо він при цьому утворює з вже виставленими хоча б один ряд більш ніж з трьох поруч стоять хрестиків. Ці правила ілюструються на рис. 2.

Малюнок 2

У клітини 1, 2, 3 ставити хрестики можна. Після цього в клітку 4 хрестик не можна ставити, оскільки утворюється кілька із чотирьох хрестиків [1, 2, 3, 4], які стоять по вертикалі, (порушено правило 2). У клітку 5 хрестик теж не можна ставити, оскільки утворюється діагональний ряд лише з двох хрестиків [1, 5] (порушено правило 1).


Виявляється, до будь-якої затравки можна додати лише кінцеве число нових хрестиків (нескінченні затравки ми поки не зачіпаємо). Спробуйте це довести!

Конфігурації, до яких неможливо, не порушуючи правил, додати нові хрестики, назвемо повними. В іншому випадку вони вважаються неповними. Деякі повні конфігурації, породжені зошитом, мають витончену симетричну структуру (рис. 3 - 6).

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

1. Для заданої затравки знайти повну конфігурацію з максимальним числом хрестиків. У загальному випадку це завдання складне (поки не знайдено розумного алгоритму, що не зводиться до простого перебору можливостей). Автор припускає, що до зошита можна додати, найбільше, 19 нових хрестиків. Відповідна повна конфігурація з 23 хрестиків зображена на рис. 8.

Малюнок 8

Відновіть последова "

COM_SPPAGEBUILDER_NO_ITEMS_FOUND