Солитер (пасьянс)

Эту страницу предлагается переименовать в Свободная ячейка. Пояснение причин и обсуждение — на странице Википедия:К переименованию/5 апреля 2012. Возможно, её текущее название не соответствует нормам современного русского языка и/или правилам именования статей Википедии. Не снимайте пометку о выставлении на переименование до окончания обсуждения. Дата постановки — 5 апреля 2012. Переименовать в предложенное название, снять этот шаблон

У этого термина существуют и другие значения, см. Солитер.

«Свободная ячейка» в наборе пасьянсов Aisleriot

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

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

Правила

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

Если нужно перенести стопку карт, это можно сделать только по одной, используя пустые колонки и свободные ячейки. Имея n свободных ячеек и m пустых колонок, можно перенести в другое место $(n+1) \cdot 2^m$ сложенных по порядку карт, такие комбинации называются «суперходы» (англ. supermoves). Компьютерные версии обычно показывают суперход во всех деталях; играющие с настоящей колодой просто переносят стопку, убедившись, что карты действительно сложены по порядку, а пустых ячеек достаточно.

История

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

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

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

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

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

Реализации

Microsoft

Солитер Компонент Microsoft Windows
Детали
Другие названия	Свободная ячейка
Тип	Игра
Поставляется с	Win32s, 95—7
Состояние поддержки
Поддерживается
Связанные компоненты
Косынка, Паук

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

Если расклады с переставленными колонками и переименованными мастями считать одинаковыми, в пасьянсе существует 1,75·10⁶⁴ разных раскладов. В MS FreeCell представлено 32000 раскладов, генерирующихся 15-битным датчиком псевдослучайных чисел; встроенная справка заявляла:

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

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

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

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

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

Другие виды

• Aisleriot — набор пасьянсов.
• KPat — набор пасьянсов в составе KDE Games.

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

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

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

См. также

• Пасьянс «Косынка» (в Windows)
• Косынка
• Паук

Примечания

1. ↑ Название в Windows XP
2. ↑ Название в Windows 95
3. ↑ ^{1 2 3 4 5} FreeCell FAQ (англ.)
4. ↑ Interview with Paul Alfille (англ.)
5. ↑ Microsoft FreeCell, «О программе»
6. ↑ http://windows8forums.com/windows-8-programs-applications/5337-what-annoying-windows-8-a.html#post6647
7. ↑ Джим Хорн. Алгоритм перетасовки карт Microsoft (англ.)
8. ↑ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003; в файле с. 44—49 (англ.)
9. ↑ FreeCell Solver
10. ↑ FreeCell Pro Evaluation Edition