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

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

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

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

Правила[править | править вики-текст]

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

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

Варианты правил[править | править вики-текст]

Марсель[править | править вики-текст]

Используется одна колода в 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 вплоть до Seven. Из Windows 8 игру выбросили; она (вместе с четырьмя другими пасьянсами) доступна из магазина программ.

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

Реализации[править | править вики-текст]

Microsoft[править | править вики-текст]

Солитер
Компонент Windows
Детали
Другие названия

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

Тип

Игра

Поставляется с

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.
  3. Доказательство. База индукции: без колонок, на одних ячейках можно перенести n+1 карту. Шаг индукции: переносим (n+1)·2m карт на (m+1)-ю колонку, использую оставшиеся m колонок и ячейки; затем ещё (n+1)·2m в конечную позицию; наконец, содержимое (m+1)-й колонки в конечную позицию.
  4. Freecell PowerMoves Explained
  5. «Наука и жизнь», 1976, № 11, с. 101.
  6. «Наука и жизнь», 1978, № 2, с. 97.
  7. «Наука и жизнь», 1978, № 7, с. 143.
  8. 1 2 3 4 5 6 7 FreeCell FAQ (англ.)
  9. Interview with Paul Alfille (англ.)
  10. Microsoft FreeCell, «О программе»
  11. Джим Хорн. Алгоритм перетасовки карт Microsoft (англ.)
  12. Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003; в файле с. 44—49 (англ.)
  13. Свободна 1 ячейка и 2 колонки, однако переместить цепочку из 8 карт не получается, см. видео: https://www.youtube.com/watch?v=ZfZN5RRW9aM.