Назад

ⓘ Игра в 15, пятнашки, такен - популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесённым ..




                                               

Финальная игра чемпионата НФЛ 1935

Финальная игра чемпионата НФЛ 1935 - решающий матч по американскому футболу в 1935. В матче играли Детройт Лайонс и Нью-Йорк Джайентс. Матч прошел 15 декабря 1935 года. На стадионе находились 15 тысяч человек. Детройт победил 26-7.

                                               

Уайтфилд, Беверли

Беверли Джой Уайтфилд, Вуллонгонг - 20 августа 1996, Шелхарбор) - австралийская пловчиха, чемпионка летних Олимпийских игр 1972 года и Игр Содружества.

                                               

Думбия, Сулейман

Сулейман Кели Думбия, Париж) - ивуарийский футболист, защитник французского "Ренна" и сборной Кот-д’Ивуара.

                                               

Финальная игра чемпионата НФЛ 1940

Финальная игра чемпионата НФЛ 1940 - это матч по американскому футболу, получивший прозвище 73-0. Матч, между командами Чикаго "Беарз" и Вашингтон Редскинз, прошел 8 декабря 1940 года. Чикаго набрали 28 очков за первую половину и ещё 45 за вторую, выиграв игру со счетом 73-0. По состоянию на 2020 год, больше не одна команда из четырёх главных лиг США не выиграла матч в 73 или более очков.

Игра в 15
                                     

ⓘ Игра в 15

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

                                     

1.1. История В США

6 января 1880 года в газете Boston Evening Transcript появилось объявление о головоломке под названием Boss Puzzle. 12 января Boston Transcript упомянула несколько версий других производителей, включая Gem Puzzle, Solitaire, Fifteen и Number Puzzle. 19 января в той же газете была анонсирована головоломка под названием The New Puzzle ; на следующий же день Worcester Gazette разместила объявление о головоломке The Boss Puzzle. Популярность головоломки стремительно росла, и предприниматели уже начали её производство и продажу.

В промежуток времени с 26 по 30 января Boston Evening Transcript опубликовала объявление Маттиаса Райса, раздосадованного появлением копий головоломки. В объявлении говорилось:

В феврале 1880 года в разных газетах начали появляться подробные статьи, посвящённые головоломке. Ряд журналов национального масштаба, включая The Youths Companion, Illustrated Newspaper, Harper’s Weekly, Scientific American, The Independent, в течение нескольких недель публиковали объявления о головоломке. Новости о головоломке распространялись в другие города. К началу марта многие производители выпускали версии головоломки под разными названиями.

12 февраля газета Boston Herald опубликовала поэму о головоломке, за которой последовал ряд произведений в стихотворной форме в других газетах. 17 февраля в газете Rochester Democrat and Chronicle была опубликована статья о влиянии головоломки на общество. 20 февраля в нью-йоркском журнале Ontario County Journal появилась заметка следующего содержания:

17 марта 1880 года газета Boston Daily Advertiser опубликовала статью, которая описывала "начало безумия" в Бостоне три месяца тому назад в декабре 1879.

На основании газетных объявлений и статей авторы книги The 15 Puzzle Слокум и Зонневельд делают вывод, что в большинстве городов "безумие" длилось один-два месяца; впрочем, во многих городах головоломка становилась популярной до появления публикаций в местных газетах и оставалась популярной даже тогда, когда публикации прекращались.

                                     

1.2. История За пределами США

В марте 1880 года головоломка начала распространяться за пределами США. До конца марта она достигла Канады и Франции. В течение апреля "безумие" достигло Англии, Германии, Латвии, Австрии, Эстонии, Норвегии, Швеции, России, Финляндии, в мае - Новой Зеландии, Нидерландов, Италии, Мексики, Дании, Австралии.

                                     

1.3. История В России

25 апреля 1880 года газета St. Petersburg Herold на немецком языке разместила объявление "Neues Spiel - Das Spiel der Funfzehn" "Новая игра - Игра в 15".

                                     

2.1. Задачи The Gem Puzzle

В головоломке The Gem Puzzle, которую в 1879 году производил и продавал Матиас Райс, игрок высыпал плитки из коробочки и случайным образом укладывал их обратно, после чего пытался восстановить упорядоченную конфигурацию:

В этой версии задача оказывалась неразрешимой ровно в половине случаев.

                                     

2.2. Задачи Головоломка 14-15

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

                                     

2.3. Задачи Современные модификации

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

                                     

2.4. Задачи Магический квадрат

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

                                     

3. Математическое описание

Можно показать, что ровно половину из всех возможных 20 922 789 888 000 =16! начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом i {\displaystyle i} расположен до если считать слева направо и сверху вниз k {\displaystyle k} квадратиков с числами меньшими i {\displaystyle i}. Будем считать n i = k {\displaystyle n_{i}=k}, то есть если после костяшки с i {\displaystyle i} -м числом нет чисел, меньших i {\displaystyle i}, то k = 0 {\displaystyle k=0}. Также введем число e {\displaystyle e} - номер ряда пустой клетки считая с 1. Если сумма

N = ∑ i = 1 15 n i + e {\displaystyle N=\sum _{i=1}^{15}n_{i}+e}

является нечётной, то решения головоломки не существует.

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



                                     

4. Оптимальное решение

Для обобщённых пятнашек задача поиска кратчайшего решения для заданной конфигурации является NP-полной.

Текущие результаты

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

                                     

4.1. Оптимальное решение 4 × 4

Любую из 10 461 394 944 000 разрешимых конфигураций "классической" головоломки 4 × 4 можно перевести в начальную не более чем за 80 ходов, если под ходом понимать перемещение одной плитки, или не более чем за 43 хода, если под ходом понимать одновременное перемещение сплошного ряда из не более чем трёх плиток. Только 17 из всех разрешимых конфигураций не могут быть решены менее чем за 80 ходов, то есть требуют 80 перемещений отдельных плиток для решения; только 16 разрешимых конфигураций требуют 43 перемещений сплошных рядов плиток.

                                     

4.2. Оптимальное решение 5 × 5

В 1995 году было показано, что любая конфигурация головоломки 5 × 5 может быть решена не более чем за 219 одиночных ходов, то есть была получена верхняя граница в 219 ходов для длины оптимального решения произвольной конфигурации. В 1996 году была найдена конфигурация, которая не может быть решена меньше чем за 112 перемещений плиток. В 2000 году верхняя граница была улучшена до 210 ходов; в 2011 году для "числа Бога" головоломки 5 × 5 были получены нижняя граница в 152 хода и верхняя граница в 208 ходов.

                                     

4.3. Оптимальное решение Текущие результаты

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

                                     

5. Использование пятнашек в информатике

"Пятнашки" разных размеров с 1960-х годов регулярно используются в исследованиях в области ИИ; в частности, на них испытываются и сравниваются алгоритмы поиска в пространстве состояний с разными эвристическими функциями и другими оптимизациями, влияющими на число посещённых в процессе поиска конфигураций головоломки вершин графа. В исследованиях так или иначе использовались головоломки размеров 3 × 3, 4 × 4, 5 × 5, 6 × 6, 2 × 7, 3 × 5.

Можно перечислить основные причины выбора пятнашек в качестве "испытательного стенда" для алгоритмов поиска:

  • задачи с пятнашками - удачные представители класса проблем, в которых требуется найти кратчайший путь между двумя заданными вершинами неориентированного конечного графа;
  • для моделирования головоломки не требуется передачи семантических тонкостей, присущих более сложным предметным областям;
  • не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек n × n за разумное время;
  • пространство состояний классических пятнашек является доступным для анализа, но всё же достаточно большим, чтобы представлять интерес и использовать и сравнивать разнообразные эвристики;
  • одна и та же эвристическая функция может применяться ко всем состояниям, так как все состояния описываются одинаково; в реальных применениях разные состояния могут иметь разные описания, что требует введения нескольких эвристик;
  • размер графа поиска зависит от размера головоломки n экспоненциально, хотя любое состояние можно описать с затратой O n 2 памяти;
  • использование в исследованиях игр и головоломок не порождает финансовых или этических проблем.
  • сама задача поиска кратчайшего решения для пятнашек проста для понимания и программного манипулирования; головоломка поддаётся описанию с помощью небольшого и чётко определённого набора простых правил;


                                     

5.1. Использование пятнашек в информатике Эвристический поиск

В качестве алгоритма поиска может использоваться алгоритм A*, IDA*, поиск в ширину.

Головоломка 3 × 3 легко решается любым алгоритмом поиска. Произвольные конфигурации пятнашек 4 × 4 решаются с помощью современных алгоритмов поиска за несколько миллисекунд. Для оптимального решения головоломки 5 × 5 требуются большие затраты ресурсов даже с применением современных компьютеров и алгоритмов; процесс поиска может длиться несколько недель и генерировать триллионы узлов. Оптимальное решение произвольных конфигураций головоломки 6 × 6 до сих пор находится за пределами возможностей, в связи с чем в исследованиях делаются лишь попытки предсказать относительную производительность алгоритма IDA* с разными эвристическими функциями.

Одна из самых простых эвристик для пятнашек может быть выражена следующим образом:

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

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

Более "умная" эвристика сопоставляет каждому расположению плиток сумму расстояний от текущей позиции каждой плитки до её целевой позиции. В литературе эта эвристика встречается под именем "манхэттенское расстояние" Manhattan distance. Допустимость функции следует из того, что за один ход перемещается только одна фишка, и расстояние между этой фишкой и её конечной позицией изменяется на 1. Тем не менее, эта эвристика также не использует всю имеющуюся информацию, из-за того, что в одной позиции не могут находиться одновременно две плитки. Существуют более информированные варианты "манхэттенского расстояния", такие, как Linear Conflict.

Для быстрого поиска оптимального решения головоломки 4 × 4, а также для возможности находить оптимальное решение головоломки 5 × 5 в разумные сроки, разработаны эвристики, основанные на базах данных образцов pattern databases. Подобные эвристики являются по сути заранее вычисленными и хранящимися в оперативной памяти таблицами, в которых закодированы оптимальные решения для подзадач; каждая из подзадач сводится к перемещению в целевые позиции определённой группы плиток. Эти эвристики также могут быть применены к кубику Рубика и другим головоломкам.

Энциклопедический словарь

Перевод
Бесплатно и без рекламы
не нужно скачивать или устанавливать

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

интеллектуальная игра онлайн →