Свободная ячейка: различия между версиями

Солитер
	компонент Windows
Солитер
Тип компонента	Игра
Включён в	Win32s, 95—7
Состояние	Поддерживается
	Медиафайлы на Викискладе

Интерактивная навигация по истории

(Показать все непатрулированные изменения)

[непроверенная версия]

← Предыдущая правка

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Текущая версия от 05:59, 27 сентября 2024

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

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

Правила

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

Если нужно перенести стопку карт, это можно сделать только по одной, используя пустые колонки и свободные ячейки. Имея n свободных ячеек и m пустых колонок, можно перенести в другое место $(n+1)\cdot 2^{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

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

Теоретическое количество раскладов в пасьянсе — 52! или 8,06·10⁶⁷. Если расклады с переставленными колонками и переименованными мастями считать одинаковыми, то число раскладов будет равно 1,75·10⁶⁴. В 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] Поскольку шансы на плохой расклад и без этого крайне малы, такое упрощение считается сомнительным.

См. также

Примечания

↑ Название в Windows 95
↑ ¹ ² ³ Мартин Гарднер. Комбинаторные задачи // Наука и жизнь : журнал / Перевод Б. Колтового. — 1968. — № 11. — С. 114. Архивировано 27 сентября 2013 года.
↑ Доказательство. База индукции: без колонок, на одних ячейках можно перенести n+1 карту. Шаг индукции: переносим (n+1)·2^m карт на (m+1)-ю колонку, используя оставшиеся m колонок и ячейки; затем ещё (n+1)·2^m в конечную позицию; наконец, содержимое (m+1)-й колонки в конечную позицию.
↑ ¹ ² 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 года.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ 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.

[1] Название в Windows 95

[gardner-2] ¹ ² ³ Мартин Гарднер. Комбинаторные задачи // Наука и жизнь : журнал / Перевод Б. Колтового. — 1968. — № 11. — С. 114. Архивировано 27 сентября 2013 года.

[3] Доказательство. База индукции: без колонок, на одних ячейках можно перенести n+1 карту. Шаг индукции: переносим (n+1)·2^m карт на (m+1)-ю колонку, используя оставшиеся m колонок и ячейки; затем ещё (n+1)·2^m в конечную позицию; наконец, содержимое (m+1)-й колонки в конечную позицию.

[powermoves-4] ¹ ² 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 года.

[fcfaq-8] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Строка 2: / Строка 2: @@
 [[Файл:FreeCell (Aisleriot 2.31.2) ru.png|thumb|300px|«Свободная ячейка» в наборе пасьянсов [[Aisleriot]]]]
-«'''Свободная ячейка'''»<ref>Название в [[Windows 95]]</ref> ({{lang-en|FreeCell}}) — карточный [[пасьянс]]. Поскольку пасьянс относительно новый и известен исключительно по компьютерным реализациям, устоявшегося русского названия нет. В [[Windows XP ]] игра некорректно названа «'''Солите́р'''» (этот пасьянс отличается от «Свободной ячейки» одним правилом).{{-1|<ref name="gardner" />}}
+«'''Свободная ячейка'''»<ref>Название в [[Windows 95]]</ref> ({{lang-en|FreeCell}}) — карточный [[пасьянс]]. Поскольку пасьянс относительно новый и известен исключительно по компьютерным реализациям, устоявшегося русского названия нет. В [[Windows XP]] игра некорректно названа «'''Солите́р'''» (этот пасьянс отличается от «Свободной ячейки» одним правилом)<ref name="gardner" />.
-Пасьянс удачно сочетает высокую сложность (намного сложнее «[[Косынка (пасьянс)|Косынки]]»), [[игра с полной информацией|полную информацию]] и мизерный процент комбинаций, которые невозможно сложить.
+Пасьянс удачно сочетает высокую сложность (намного сложнее «[[Косынка (пасьянс)|Косынки]]»), [[игра с совершенной информацией|совершенную информацию]] ([[игра с полной информацией|полную]] + отсутствие дальнейшей случайности) и мизерный процент комбинаций, которые невозможно сложить.
 == Правила ==
 * Используется стандартная [[колода карт]] (52 карты).
 * Раскладывается вся колода в 8 колонок, лицом вверх. Таким образом, будет четыре колонки по 7 карт и ещё четыре — по 6.
-* Также есть 4 ячейки, именуемых «домом», и 4 «свободных» ячейки. На момент начала игры все они пусты.
+* Также есть 4 ячейки, именуемых «домом», и 4 «свободных» ячейки. В начале игры все они пусты.
 * Разрешено перекладывать '''одну''' карту из колонки или свободной ячейки:
 ** в любую другую колонку — на следующую по старшинству карту другого цвета (например, чёрного валета — только на красную даму).
@@ Строка 17: / Строка 17: @@
 * Пасьянс сходится, если удаётся переместить всю колоду в «дом».
-Если нужно перенести стопку карт, это можно сделать только по одной, используя пустые колонки и свободные ячейки. Имея ''n'' свободных ячеек и ''m'' пустых колонок, можно перенести в другое место <math>(n+1) \cdot 2^m</math> сложенных по порядку карт, такие комбинации называются «суперходы» ({{lang-en|supermoves}}). Компьютерные версии обычно показывают суперход во всех деталях; играющие с настоящей колодой просто переносят стопку, убедившись, что карты действительно сложены по порядку, а пустых ячеек достаточно.
+Если нужно перенести стопку карт, это можно сделать только по одной, используя пустые колонки и свободные ячейки. Имея ''n'' свободных ячеек и ''m'' пустых колонок, можно перенести в другое место <math>(n+1) \cdot 2^m</math> сложенных по порядку карт<ref>Доказательство. База [[Математическая индукция|индукции]]: без колонок, на одних ячейках можно перенести ''n''+1 карту. Шаг индукции: переносим {{nobr|(''n''+1)·2<sup>''m''</sup>}} карт на (''m''+1)-ю колонку, используя оставшиеся ''m'' колонок и ячейки; затем ещё {{nobr|1=(''n''+1)·2<sup>''m''</sup>}} в конечную позицию; наконец, содержимое (''m''+1)-й колонки в конечную позицию.</ref><ref name="powermoves">{{Cite web |url=http://www.solitairecentral.com/articles/FreecellPowerMovesExplained.html |title=Freecell PowerMoves Explained<!-- Заголовок добавлен ботом --> |access-date=2014-07-06 |archive-date=2014-07-14 |archive-url=https://web.archive.org/web/20140714125841/http://www.solitairecentral.com/articles/FreecellPowerMovesExplained.html |deadlink=no }}</ref>, такие комбинации называются «суперходы» ({{lang-en|supermoves}}). Компьютерные версии обычно показывают суперход во всех деталях; играющие с настоящей колодой просто переносят стопку, убедившись, что карты действительно сложены по порядку, а пустых ячеек достаточно. Иногда можно перенести ещё больше карт, придержав какую-то часть в занятой колонке, но это уже комбинация суперходов<ref name="powermoves" />.
 == Варианты правил ==
@@ Строка 23: / Строка 23: @@
 === Марсель ===
 Используется одна колода в 52 карты, как и в стандартных правилах.
 Карты раскладываются картинкой вверх в 7 столбцов по 7 карт.
 Оставшиеся три карты кладутся в низ любых столбцов (одного или нескольких) по выбору раскладывающего.
@@ Строка 36: / Строка 36: @@
 === Солитер ===
-Игра отличается от «Свободной ячейки» одним правилом: карты в колонках выкладываются по масти, по одной за ход. Например, В♡ — только на Д♡.{{-1|<ref name="gardner" />}}
+Игра отличается от «Свободной ячейки» одним правилом: карты в колонках выкладываются по масти, по одной за ход. Например, В♡ — только на Д♡<ref name="gardner" />.
 Солитер намного сложнее «Свободной ячейки», высок процент неразрешимых комбинаций, поэтому есть и упрощённые варианты.
+Но иногда Солитером называют классическую версию «Свободной ячейки».
 ==== Солитер 6×6 ====
-Вариант пасьянса для колоды в 36 карт.<ref>[http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1976_.html#7611 «Наука и жизнь», 1976, № 11, с. 101.]</ref>
+Вариант пасьянса для колоды в 36 карт.<ref>{{Cite web |url=http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1976_.html#7611 |title=«Наука и жизнь», 1976, № 11, с. 101. |access-date=2013-06-06 |archive-date=2013-07-13 |archive-url=https://web.archive.org/web/20130713051540/http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1976_.html#7611 |deadlink=no }}</ref>
-Колода раскладывается в 6 столбцов по 6 карт. Используются три свободных ячейки.
-Карты в столбцах можно перекладывать в нисходящем порядке по масти (а не с чередованием цветов, как в стандартных правилах), по одной за ход. Например, трефовую десятку можно положить только на трефового валета (а не бубнового или червонного).
-В остальном правила аналогичны стандартным. Цель пасьянса — собрать карты на базовые тузы в восходящем порядке (6, 7, 8, 9, 10, В, Д, К). Существует вариант со сбором карт на базовые в нисходящем порядке  (К, Д, В, 10, 9, 8, 7, 6).
+Колода раскладывается в 6 столбцов по 6 карт. Используются три свободных ячейки. Правила аналогичны стандартным для «Солитера»: карты в столбцах можно перекладывать в нисходящем порядке по масти, по одной за ход (например, трефовую десятку можно положить на трефового валета). Цель пасьянса — собрать карты на базовые тузы в восходящем порядке (6, 7, 8, 9, 10, В, Д, К). Существует вариант со сбором карт на базовые в нисходящем порядке  (К, Д, В, 10, 9, 8, 7, 6).
 ==== Солитер с одной и двумя мастями ====
-В этом варианте пасьянса используется половина стандартной колоды в 52 карты<ref>[http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1978_.html#7802 «Наука и жизнь», 1978, № 2, с. 97.]</ref>. Из неё выбирают какие-нибудь две масти (26 карт). Их раскладывают в 6 столбцов: четыре столбца по 4 карты и два по 5 карт.
+В этом варианте пасьянса используется половина стандартной колоды в 52 карты<ref>{{Cite web |url=http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1978_.html#7802 |title=«Наука и жизнь», 1978, № 2, с. 97. |access-date=2013-06-06 |archive-date=2013-06-03 |archive-url=https://web.archive.org/web/20130603223215/http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1978_.html#7802 |deadlink=no }}</ref>. Из неё выбирают какие-нибудь две масти (26 карт). Их раскладывают в 6 столбцов: четыре столбца по 4 карты и два по 5 карт.
 Используются две свободные ячейки. В базовом ряду, естественно, есть только два места для тузов.
 Перекладывать карты между столбцами можно по масти в нисходящем порядке, по одной.
 В базовый ряд собираются карты по масти в восходящем порядке.
 Существует также вариант пасьянса с одной мастью (13 карт). Их раскладывают в 5 столбцов (три по 3 карты и два по 2 карты). Используется одна свободная ячейка и одно базовое место для единственного туза.
-Этот вариант пасьянса при правильной игре сходится всегда. Один из наиболее трудных раскладов — упорядоченная в восходящем порядке колода (1-й горизонтальный ряд — Т, 2, 3, 4, 5; 2-й — 6, 7, 8, 9, 10; 3-й — В, Д, К). Эта задача решается за 23 хода<ref>[http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1978_.html#7807 «Наука и жизнь», 1978, № 7, с. 143.]</ref>.
+Этот вариант пасьянса при правильной игре сходится всегда. Один из наиболее трудных раскладов — упорядоченная в восходящем порядке колода (1-й горизонтальный ряд — Т, 2, 3, 4, 5; 2-й — 6, 7, 8, 9, 10; 3-й — В, Д, К). Эта задача решается за 23 хода<ref>{{Cite web |url=http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1978_.html#7807 |title=«Наука и жизнь», 1978, № 7, с. 143. |access-date=2013-06-06 |archive-date=2013-06-03 |archive-url=https://web.archive.org/web/20130603223215/http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1978_.html#7807 |deadlink=no }}</ref>.
 == История ==
 [[Файл:PlatoFreeCell.png|thumb|«Свободная ячейка» на PLATO]]
-Предтечами «Свободной ячейки» можно считать пасьянсы «Восьмёрка» и «Сорок разбойников» (он же «Наполеон на острове святой Елены»).{{-1|<ref name="fcfaq">[http://www.solitairelaboratory.com/fcfaq.html FreeCell FAQ]{{ref-en}}</ref>}} В 1968 году [[Гарднер, Мартин|М.&nbsp;Гарднер]] опубликовал пасьянс под авторством некоего Бейкера, однако в нём карты складывались по масти. Журнал «[[Наука и жизнь]]» мгновенно перепечатал пасьянс,{{-1|<ref name="gardner">{{статья
+Предтечами «Свободной ячейки» можно считать пасьянсы «Восьмёрка» и «Сорок разбойников» (он же «Наполеон на острове святой Елены»)<ref name="fcfaq">[http://www.solitairelaboratory.com/fcfaq.html FreeCell FAQ] {{Wayback|url=http://www.solitairelaboratory.com/fcfaq.html |date=20130719194533 }}{{ref-en}}</ref>. В 1968 году [[Гарднер, Мартин|М.&nbsp;Гарднер]] опубликовал пасьянс под авторством некоего Бейкера, однако в нём карты складывались по масти. Журнал «[[Наука и жизнь]]» мгновенно перепечатал пасьянс,<ref name="gardner">{{статья
  |автор         = [[Гарднер, Мартин|Мартин Гарднер]]
  |заглавие      = Комбинаторные задачи
@@ Строка 86: / Строка 84: @@
  |issn          =
  |doi           =
  |bibcode       =
  |arxiv         =
  |pmid          =
  |ref           =
+ |archiveurl    = https://web.archive.org/web/20130927102658/http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_%27%27Nauka_i_jizn%27%27%27_1968_.html#6811
- |archiveurl    =
- |archivedate   =
+ |archivedate   = 2013-09-27
-}}</ref>}} окрестив его «Солитером», периодически предлагал решить головоломные расклады.
+}}</ref> окрестив его «Солитером», периодически предлагал решить головоломные расклады.
-Изобретатель «Свободной ячейки» Пол Олфилл (''Paul Alfille''), будучи ещё ребёнком, жаловался, что большинство пасьянсов оставляли колоду отсортированной по масти; чтобы начать новую игру, требовалось долгая и тщательная [[тасование|перетасовка]]. Установив правило «чёрный-красный», Олфилл улучшил состояние колоды (даже если пасьянс решён, позиция становится очевидной задолго до того, как будут сложены все карты, и часть колоды складывается по масти, а часть — поочерёдно).<ref>[http://www.freecell.net/f/c/alfille.html Interview with Paul Alfille]{{ref-en}}</ref> Игра оказалась довольно сложной, но неразрешимые комбинации практически не выпадали.
+Изобретатель «Свободной ячейки» Пол Олфилл (''Paul Alfille''), будучи ещё ребёнком, жаловался, что большинство пасьянсов оставляли колоду отсортированной по масти; чтобы начать новую игру, требовалось долгая и тщательная [[тасование|перетасовка]]. Установив правило «чёрный-красный», Олфилл улучшил состояние колоды: даже если пасьянс решён, позиция становится очевидной задолго до того, как будут сложены все карты, и часть колоды складывается по масти, а часть — поочерёдно<ref>[http://www.freecell.net/f/c/alfille.html Interview with Paul Alfille] {{Wayback|url=http://www.freecell.net/f/c/alfille.html |date=20090623223549 }}{{ref-en}}</ref>. Игра оказалась довольно сложной, но неразрешимые комбинации практически не выпадали.
 Впоследствии, в [[1978 год]]у, Олфилл реализовал свою игру в рамках системы [[программированное обучение|программированного обучения]] [[PLATO (компьютерная система)|PLATO]] на языке программирования [[TUTOR]]. Благодаря высокому (по тем временам) [[Разрешение (компьютерная графика)|разрешению]] PLATO — 512×512 — удалось нарисовать разборчивые изображения мастей, несмотря на монохромный монитор.
-В дальнейшем Джим Хорн (''Jim Horne'') реализовал «Свободную ячейку» для [[DOS]] (в текстовом виде), в [[1992]] — для [[Windows]].<ref name="fcfaq" /><ref>Microsoft FreeCell, «О программе»</ref> Неизвестно, где Хорн узнал о «Свободной ячейке» — вероятно, будучи студентом, имел дело с PLATO. Компания [[Microsoft]] включила игру в пакет [[Microsoft Entertainment Pack]], позднее — в [[Win32s]]. Впрочем, «Свободная ячейка» оставалась малоизвестной, пока не оказалась в стандартной поставке [[Windows 95]]. В дальнейшем игру включали во все версии Windows вплоть до [[Windows 7|Seven]]. Из [[Windows 8]] игру выбросили; она (вместе с четырьмя другими пасьянсами) доступна из магазина программ.
+В дальнейшем Джим Хорн (''Jim Horne'') реализовал «Свободную ячейку» для [[DOS]] (в текстовом виде), в [[1992]] — для [[Windows]].<ref name="fcfaq" /><ref>Microsoft FreeCell, «О программе»</ref> Неизвестно, где Хорн узнал о «Свободной ячейке» — вероятно, будучи студентом, имел дело с PLATO. Компания [[Microsoft]] включила игру в пакет [[Microsoft Entertainment Pack]], позднее — в [[Win32s]]. Впрочем, «Свободная ячейка» оставалась малоизвестной, пока не оказалась в стандартной поставке [[Windows 95]]. В дальнейшем игру включали во все версии Windows вплоть до [[Windows 7]]. Из [[Windows 8]] игру выбросили; она (вместе с четырьмя другими пасьянсами) доступна из магазина программ.
 Только после появления ''Microsoft FreeCell'' изобретение Олфилла стали включать в книги о карточных играх.<ref name="fcfaq" />
@@ Строка 106: / Строка 104: @@
 === Microsoft ===
+{{Компонент операционной системы
-{{Карточка компонента Windows
-| name               = Солитер
+| название             = Солитер
+| операционная система = [[Windows]]
-| other_names        = Свободная ячейка
-| type               = Игра
+| логотип              =
-| logo               =
+| изображение          =
-| logo_size          =
+| подпись              =
-| screenshot         =
+| тип                  = Игра
+| версии ОС            = [[Win32s]], [[Windows 95|95]]—[[Windows 7|7]]
-| screenshot_size    =
-| caption            =
+| заменил              =
+| был заменён          =
-| support_status     = Поддерживается
+| сервис               =
-| included_with      = [[Windows 95|95]]—[[Windows 7|7]]
+| описание сервиса     =
-| also_available_for =
-| replaces           =
+| состояние            = Поддерживается
-| replaced_by        =
+| сайт                 =
-| related_components = [[Косынка (пасьянс)|Косынка]], [[Паук (пасьянс)|Паук]]
 }}
-Реализация Джима Хорна, опубликованная под именем ''Microsoft FreeCell'', считается классической. Сторонние разработчики обычно делают в своих программах генератор раскладов, совместимый с нумерацией Microsoft.<ref>[http://www.solitairelaboratory.com/mshuffle.txt Джим Хорн. Алгоритм перетасовки карт Microsoft]{{ref-en}}</ref>
+Реализация Джима Хорна, опубликованная под именем ''Microsoft FreeCell'', считается классической. Сторонние разработчики обычно делают в своих программах генератор раскладов, совместимый с нумерацией Microsoft<ref name="fcfaq" /><ref>[http://www.solitairelaboratory.com/mshuffle.txt Джим Хорн. Алгоритм перетасовки карт Microsoft] {{Wayback|url=http://www.solitairelaboratory.com/mshuffle.txt |date=20090504011122 }}{{ref-en}}</ref>.
-Теоретическое количество раскладов в пасьянсе – [[факториал|52!]] или 8,06·10<sup>67</sup>. Если расклады с переставленными колонками и переименованными мастями считать одинаковыми, то число раскладов будет равно 1,75·10<sup>64</sup>. В ''MS FreeCell'' представлено лишь 32000 раскладов, генерирующихся 15-битным [[генератор псевдослучайных чисел|датчиком псевдослучайных чисел]]; встроенная справка заявляла:
+Теоретическое количество раскладов в пасьянсе — [[факториал|52!]] или 8,06·10<sup>67</sup>. Если расклады с переставленными колонками и переименованными мастями считать одинаковыми, то число раскладов будет равно 1,75·10<sup>64</sup>. В ''MS FreeCell'' представлено лишь 32000 раскладов, генерирующихся 15-битным [[генератор псевдослучайных чисел|генератором псевдослучайных чисел]]; встроенная справка заявляла:
 {{cquote|Считается (хотя и не доказано), что данный пасьянс сходится при любом раскладе.}}
-В общем случае это неверно: в качестве «[[пасхальное яйцо (виртуальное)|пасхального яйца]]», в игре можно задать явно неразрешимые расклады −1 и −2. Чтобы проверить 32000 раскладов Microsoft, в [[интернет]]е появился [[краудсорсинг]]-проект, проверяющий, действительно ли все расклады разрешимы. В проекте были задействованы более чем 100 заядлых картёжников; к [[1995 год]]у только расклад № 11982 не поддался ни одному участнику. Несмотря на то, что задача [[NP-полная задача|NP-полна]] по количеству карт<ref>[http://www.informatik.uni-freiburg.de/~ki/papers/helmert-aij03.ps.gz Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003]; в файле с.&nbsp;44—49{{ref-en}}</ref>, к середине 2000-х годов удалось реализовать достаточно быстрый [[полный перебор]] и показать, что для этого расклада решения действительно нет.<!--<ref>[http://fc-solve.berlios.de/ FreeCell Solver]</ref><ref>[http://www.rrhistorical.com/rrdata/Fcpro65/ FreeCell Pro Evaluation Edition]</ref> куда приткнуть? -->
+В общем случае это неверно: в качестве «[[пасхальное яйцо (виртуальное)|пасхального яйца]]» в игре можно задать явно неразрешимые расклады −1 и −2. Чтобы проверить 32000 раскладов Microsoft, в [[интернет]]е появился [[краудсорсинг]]-проект, проверяющий, действительно ли все расклады разрешимы. В проекте были задействованы более чем 100 заядлых картёжников; к [[1995 год]]у только расклад № 11982 не поддался ни одному участнику. Несмотря на то, что задача [[NP-полная задача|NP-полна]] по количеству карт<ref>[http://www.informatik.uni-freiburg.de/~ki/papers/helmert-aij03.ps.gz Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003] {{Wayback|url=http://www.informatik.uni-freiburg.de/~ki/papers/helmert-aij03.ps.gz |date=20081031144712 }}; в файле с. 44—49{{ref-en}}</ref>, к середине 2000-х годов удалось реализовать достаточно быстрый [[полный перебор]] и показать, что для этого расклада решения действительно нет.<!--<ref>[http://fc-solve.berlios.de/ FreeCell Solver]</ref><ref>[http://www.rrhistorical.com/rrdata/Fcpro65/ FreeCell Pro Evaluation Edition]</ref> куда приткнуть? -->
-В [[Windows XP]] количество раскладов увеличено до 1 миллиона, первые 32000 раскладов были теми же. Помимо расклада 11982, решение не существует для раскладов 146692, 186216, 455889, 495505, 512118, 517776 и 781948.
+В [[Windows XP]] количество раскладов увеличено до 1 миллиона, первые 32000 раскладов были теми же. Помимо расклада 11982, решение не существует для раскладов 146692, 186216, 455889, 495505, 512118, 517776 и 781948.
-В версии Microsoft (до Windows XP) суперходы реализованы, но не полностью: с пустыми колонками программа работает как со свободными ячейками. Другими словами, имея три пустых колонки, даже без свободных ячеек можно перенести 8 карт; ''MS FreeCell'' перенесёт только четыре. В Windows XP, Windows Vista и Windows 7 суперходы реализованы в полном объёме, однако есть недоработки<ref>Свободна 1 ячейка и 2 колонки, однако переместить цепочку из 8 карт не получается, см. видео: https://www.youtube.com/watch?v=ZfZN5RRW9aM.</ref>.
+В версии Microsoft суперходы реализованы, но не полностью: если колонок больше одной или нет свободных ячеек, программа может и не заметить суперход<ref name="fcfaq" />. Например, имея одну пустую ячейку и две колонки, можно перенести восемь карт;<ref>Свободна 1 ячейка и 2 колонки, однако переместить цепочку из 8 карт не получается, см. видео: https://www.youtube.com/watch?v=ZfZN5RRW9aM {{Wayback|url=https://www.youtube.com/watch?v=ZfZN5RRW9aM |date=20151208013858 }}.</ref> ''MS FreeCell'' перенесёт только четыре.
 Существует способ быстрого выигрыша: нажимаем одновременно клавиши {{Клавиша|Shift|Ctrl|F10}}, в полученном окне выбираем: «Прервать» — выиграть, «Повтор» — проиграть, «Пропустить» — отмена.
@@ Строка 147: / Строка 144: @@
 == См. также ==
+* [[Microsoft Solitaire]]
-* [[Пасьянс «Косынка»]] (в Windows)
 * [[Косынка (пасьянс)|Косынка]]
 * [[Паук (пасьянс)|Паук]]
@@ Строка 154: / Строка 151: @@
 {{примечания}}
+{{Пасьянсы}}
 {{Компоненты Microsoft Windows}}
@@ Строка 159: / Строка 157: @@
 [[Категория:Пасьянсы]]
 [[Категория:Стандартные приложения Windows]]
-[[Категория:Компьютерные игры с бесплатными клонами]]
+[[Категория:Карточные компьютерные игры]]
+[[Категория:NP-полные задачи]]

Пасьянсы
Пасьянсы	Гусиные лапки Дом в лесу Косынка Крепость Маджонг Мария Стюарт Маскарад Осаждённый замок Паганини Паук Покерный пасьянс Прекрасная Лючия Свободная ячейка Солнце Султан Шедевр
Пасьянсы в Microsoft Windows	Косынка Паук Солитер Пирамида Microsoft Mahjong Microsoft Solitaire Collection
Другие компьютерные пасьянсы	Aisleriot PySol BVS Solitaire Collection
Прочее	Словарь пасьянсных терминов

Свободная ячейка: различия между версиями

Текущая версия от 05:59, 27 сентября 2024

Содержание

Правила