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