Свободная ячейка

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
«Свободная ячейка» в наборе пасьянсов Aisleriot

«Свободная ячейка»[1] (англ. FreeCell) — карточный пасьянс. Поскольку пасьянс относительно новый и известен исключительно по компьютерным реализациям, устоявшегося русского названия нет. В Windows XP игра некорректно названа «Солите́р» (этот пасьянс отличается от «Свободной ячейки» одним правилом)[2].

Пасьянс удачно сочетает высокую сложность (намного сложнее «Косынки»), совершенную информацию (полную + отсутствие дальнейшей случайности) и мизерный процент комбинаций, которые невозможно сложить.

  • Используется стандартная колода карт (52 карты).
  • Раскладывается вся колода в 8 колонок, лицом вверх. Таким образом, будет четыре колонки по 7 карт и ещё четыре — по 6.
  • Также есть 4 ячейки, именуемых «домом», и 4 «свободных» ячейки. В начале игры все они пусты.
  • Разрешено перекладывать одну карту из колонки или свободной ячейки:
    • в любую другую колонку — на следующую по старшинству карту другого цвета (например, чёрного валета — только на красную даму).
    • либо на свободную ячейку, если она пуста (таким образом, каждая из свободных ячеек может хранить только одну карту);
    • либо в пустую колонку — без ограничений;
    • либо в «дом» — карты одной масти, начиная с туза и заканчивая королём.
  • Пасьянс сходится, если удаётся переместить всю колоду в «дом».

Если нужно перенести стопку карт, это можно сделать только по одной, используя пустые колонки и свободные ячейки. Имея n свободных ячеек и m пустых колонок, можно перенести в другое место сложенных по порядку карт[3][4], такие комбинации называются «суперходы» (англ. supermoves). Компьютерные версии обычно показывают суперход во всех деталях; играющие с настоящей колодой просто переносят стопку, убедившись, что карты действительно сложены по порядку, а пустых ячеек достаточно. Иногда можно перенести ещё больше карт, придержав какую-то часть в занятой колонке, но это уже комбинация суперходов[4].

Варианты правил

[править | править код]

Используется одна колода в 52 карты, как и в стандартных правилах.

Карты раскладываются картинкой вверх в 7 столбцов по 7 карт. Оставшиеся три карты кладутся в низ любых столбцов (одного или нескольких) по выбору раскладывающего.

Свободных ячеек можно использовать только три (а не четыре, как в стандартных правилах).

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

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

Игра отличается от «Свободной ячейки» одним правилом: карты в колонках выкладываются по масти, по одной за ход. Например, В♡ — только на Д♡[2].

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

Но иногда Солитером называют классическую версию «Свободной ячейки».

Солитер 6×6

[править | править код]

Вариант пасьянса для колоды в 36 карт.[5]

Колода раскладывается в 6 столбцов по 6 карт. Используются три свободных ячейки. Правила аналогичны стандартным для «Солитера»: карты в столбцах можно перекладывать в нисходящем порядке по масти, по одной за ход (например, трефовую десятку можно положить на трефового валета). Цель пасьянса — собрать карты на базовые тузы в восходящем порядке (6, 7, 8, 9, 10, В, Д, К). Существует вариант со сбором карт на базовые в нисходящем порядке (К, Д, В, 10, 9, 8, 7, 6).

Солитер с одной и двумя мастями

[править | править код]

В этом варианте пасьянса используется половина стандартной колоды в 52 карты[6]. Из неё выбирают какие-нибудь две масти (26 карт). Их раскладывают в 6 столбцов: четыре столбца по 4 карты и два по 5 карт.

Используются две свободные ячейки. В базовом ряду, естественно, есть только два места для тузов.

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

Существует также вариант пасьянса с одной мастью (13 карт). Их раскладывают в 5 столбцов (три по 3 карты и два по 2 карты). Используется одна свободная ячейка и одно базовое место для единственного туза.

Этот вариант пасьянса при правильной игре сходится всегда. Один из наиболее трудных раскладов — упорядоченная в восходящем порядке колода (1-й горизонтальный ряд — Т, 2, 3, 4, 5; 2-й — 6, 7, 8, 9, 10; 3-й — В, Д, К). Эта задача решается за 23 хода[7].

«Свободная ячейка» на PLATO

Предтечами «Свободной ячейки» можно считать пасьянсы «Восьмёрка» и «Сорок разбойников» (он же «Наполеон на острове святой Елены»)[8]. В 1968 году М. Гарднер опубликовал пасьянс под авторством некоего Бейкера, однако в нём карты складывались по масти. Журнал «Наука и жизнь» мгновенно перепечатал пасьянс,[2] окрестив его «Солитером», периодически предлагал решить головоломные расклады.

Изобретатель «Свободной ячейки» Пол Олфилл (Paul Alfille), будучи ещё ребёнком, жаловался, что большинство пасьянсов оставляли колоду отсортированной по масти; чтобы начать новую игру, требовалось долгая и тщательная перетасовка. Установив правило «чёрный-красный», Олфилл улучшил состояние колоды: даже если пасьянс решён, позиция становится очевидной задолго до того, как будут сложены все карты, и часть колоды складывается по масти, а часть — поочерёдно[9]. Игра оказалась довольно сложной, но неразрешимые комбинации практически не выпадали.

Впоследствии, в 1978 году, Олфилл реализовал свою игру в рамках системы программированного обучения PLATO на языке программирования TUTOR. Благодаря высокому (по тем временам) разрешению PLATO — 512×512 — удалось нарисовать разборчивые изображения мастей, несмотря на монохромный монитор.

В дальнейшем Джим Хорн (Jim Horne) реализовал «Свободную ячейку» для DOS (в текстовом виде), в 1992 — для Windows.[8][10] Неизвестно, где Хорн узнал о «Свободной ячейке» — вероятно, будучи студентом, имел дело с PLATO. Компания Microsoft включила игру в пакет Microsoft Entertainment Pack, позднее — в Win32s. Впрочем, «Свободная ячейка» оставалась малоизвестной, пока не оказалась в стандартной поставке Windows 95. В дальнейшем игру включали во все версии Windows вплоть до Windows 7. Из Windows 8 игру выбросили; она (вместе с четырьмя другими пасьянсами) доступна из магазина программ.

Только после появления Microsoft FreeCell изобретение Олфилла стали включать в книги о карточных играх.[8]

Реализации

[править | править код]
компонент Windows
Солитер
Тип компонента Игра
Включён в Win32s, 957
Состояние Поддерживается
Логотип Викисклада Медиафайлы на Викискладе

Реализация Джима Хорна, опубликованная под именем Microsoft FreeCell, считается классической. Сторонние разработчики обычно делают в своих программах генератор раскладов, совместимый с нумерацией Microsoft[8][11].

Теоретическое количество раскладов в пасьянсе — 52! или 8,06·1067. Если расклады с переставленными колонками и переименованными мастями считать одинаковыми, то число раскладов будет равно 1,75·1064. В MS FreeCell представлено лишь 32000 раскладов, генерирующихся 15-битным генератором псевдослучайных чисел; встроенная справка заявляла:

Считается (хотя и не доказано), что данный пасьянс сходится при любом раскладе.

В общем случае это неверно: в качестве «пасхального яйца» в игре можно задать явно неразрешимые расклады −1 и −2. Чтобы проверить 32000 раскладов Microsoft, в интернете появился краудсорсинг-проект, проверяющий, действительно ли все расклады разрешимы. В проекте были задействованы более чем 100 заядлых картёжников; к 1995 году только расклад № 11982 не поддался ни одному участнику. Несмотря на то, что задача NP-полна по количеству карт[12], к середине 2000-х годов удалось реализовать достаточно быстрый полный перебор и показать, что для этого расклада решения действительно нет.

В Windows XP количество раскладов увеличено до 1 миллиона, первые 32000 раскладов были теми же. Помимо расклада 11982, решение не существует для раскладов 146692, 186216, 455889, 495505, 512118, 517776 и 781948.

В версии Microsoft суперходы реализованы, но не полностью: если колонок больше одной или нет свободных ячеек, программа может и не заметить суперход[8]. Например, имея одну пустую ячейку и две колонки, можно перенести восемь карт;[13] MS FreeCell перенесёт только четыре.

Существует способ быстрого выигрыша: нажимаем одновременно клавиши ⇧ Shift+Ctrl+F10, в полученном окне выбираем: «Прервать» — выиграть, «Повтор» — проиграть, «Пропустить» — отмена.

Другие виды

[править | править код]
  • Aisleriot — набор пасьянсов.
  • KPat — набор пасьянсов в составе KDE Games.

Вероятность победы

[править | править код]

По современным данным, вероятность выпадения разрешимой комбинации оценивается более чем в 99,99 % — одна неразрешимая комбинация на 78 000 разрешимых. Без свободных ячеек сходится всего 0,2 % раскладов. Чтобы любой расклад гарантированно сошёлся, нужно не менее семи свободных ячеек.[8]

Если упростить правила и разрешить перемещать упорядоченную стопку целиком, не используя свободных ячеек, разрешимы все 1 млн раскладов Microsoft — но потенциально неразрешимые также остались.[8] Поскольку шансы на плохой расклад и без этого крайне малы, такое упрощение считается сомнительным.

Примечания

[править | править код]
  1. Название в Windows 95
  2. 1 2 3 Мартин Гарднер. Комбинаторные задачи // Наука и жизнь : журнал / Перевод Б. Колтового. — 1968. — № 11. — С. 114. Архивировано 27 сентября 2013 года.
  3. Доказательство. База индукции: без колонок, на одних ячейках можно перенести n+1 карту. Шаг индукции: переносим (n+1)·2m карт на (m+1)-ю колонку, используя оставшиеся m колонок и ячейки; затем ещё (n+1)·2m в конечную позицию; наконец, содержимое (m+1)-й колонки в конечную позицию.
  4. 1 2 Freecell PowerMoves Explained. Дата обращения: 6 июля 2014. Архивировано 14 июля 2014 года.
  5. «Наука и жизнь», 1976, № 11, с. 101. Дата обращения: 6 июня 2013. Архивировано 13 июля 2013 года.
  6. «Наука и жизнь», 1978, № 2, с. 97. Дата обращения: 6 июня 2013. Архивировано 3 июня 2013 года.
  7. «Наука и жизнь», 1978, № 7, с. 143. Дата обращения: 6 июня 2013. Архивировано 3 июня 2013 года.
  8. 1 2 3 4 5 6 7 FreeCell FAQ Архивная копия от 19 июля 2013 на Wayback Machine (англ.)
  9. Interview with Paul Alfille Архивная копия от 23 июня 2009 на Wayback Machine (англ.)
  10. Microsoft FreeCell, «О программе»
  11. Джим Хорн. Алгоритм перетасовки карт Microsoft Архивная копия от 4 мая 2009 на Wayback Machine (англ.)
  12. Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003 Архивная копия от 31 октября 2008 на Wayback Machine; в файле с. 44—49 (англ.)
  13. Свободна 1 ячейка и 2 колонки, однако переместить цепочку из 8 карт не получается, см. видео: https://www.youtube.com/watch?v=ZfZN5RRW9aM Архивная копия от 8 декабря 2015 на Wayback Machine.