Свободная ячейка (FreeCell) — это карточный пасьянс, в который играют стандартной колодой из 52 карт. Он принципиально отличается от большинства пасьянсов тем, что очень немногие расклады являются неразрешимыми, а все карты с самого начала игры сдаются лицом вверх. Хотя программные реализации различаются, в большинстве версий руки обозначаются номером (полученным из начального значения, используемого генератором случайных чисел для перетасовки карт).
Компания Microsoft включала компьютерную игру FreeCell в каждый выпуск операционной системы Windows с 1995 года, что значительно способствовало популярности игры среди пользователей персональных компьютеров и даже привело к созданию нескольких веб-сайтов, посвященных FreeCell. Microsoft FreeCell является настолько определяющей для многих игроков в FreeCell, что многие другие программные реализации стремятся к совместимости с ее генератором случайных чисел, чтобы воспроизвести ее пронумерованные руки.
Одним из старейших предков FreeCell является игра Eight Off. В июньском выпуске журнала Scientific American за 1968 год Мартин Гарднер в своей колонке "Математические игры" описал игру К. Л. Бейкера, которая похожа на FreeCell, за исключением того, что карты на столе выстраиваются по масти, а не по чередованию цветов. Гарднер писал: "Этой игре Бейкера научил его отец, который, в свою очередь, научился ей у англичанина в 1920-х годах". Этот вариант сейчас называется "Игра Бейкера". Истоки FreeCell могут восходить к 1945 году и скандинавской игре под названием "Наполеон на острове Святой Елены" (не пасьянс "Наполеон на острове Святой Елены", также известный как "Сорок воров").
Пол Алфилл изменил игру Бейкера, заставив карты строиться в соответствии с чередованием цветов, создав таким образом FreeCell. Он реализовал первую компьютерную версию, будучи студентом-медиком Иллинойского университета, на языке программирования TUTOR для образовательной компьютерной системы PLATO в 1978 году. Альфилле смог вывести легко узнаваемые графические изображения игральных карт на монохромный дисплей 512 × 512 системы PLATO.
Эта оригинальная среда FreeCell допускала игры с 4-10 столбцами и 1-10 клетками в дополнение к стандартной игре 8 × 4. Для каждого варианта программа хранила ранжированный список игроков с самыми длинными выигрышными сериями. Также существовала система турниров, которая позволяла людям соревноваться за победу в сложных, отобранных вручную сделках. Пол Алфилл более подробно описал эту раннюю среду FreeCell в интервью 2000 года.
В 2012 году исследователи использовали методы эволюционных вычислений для создания выигрывающих игроков FreeCell.
Другие пасьянсы, связанные или вдохновленные FreeCell, включают Seahaven Towers, Penguin, Stalactites, ForeCell, Antares (скрещивание со Scorpion).
Цель
Цель игры заключается в том, чтобы переместить все карты в свои стопки.
Как играть?
- Используется одна стандартная колода из 52 карт.
- Есть четыре открытых клетки и четыре открытых основания. В некоторых альтернативных правилах используется от одной до десяти ячеек.
- Карты сдаются лицом вверх в восемь каскадов, четыре из которых состоят из семи карт каждый и четыре — из шести карт каждый. В некоторых альтернативных правилах используется от четырех до десяти каскадов.
- Игра выиграна после того, как все карты перемещены в свои стопки.
Стратегия
- Верхняя карта каждого каскада начинает последовательность.
- Каскады должны строиться вниз путем чередования цветов.
- Основания строятся по мастям. Основания обычно начинаются с туза и строятся до короля.
Опции
- Игра FreeCell имеет постоянное количество карт. Это означает, что за постоянное время человек или компьютер может перечислить все возможные ходы из заданной начальной конфигурации и обнаружить выигрышный набор ходов или, если предположить, что игра не может быть решена, отсутствие такового. Чтобы провести интересный анализ сложности, необходимо построить обобщенную версию игры FreeCell с 4 × n картами. Эта обобщенная версия игры NP-полна; маловероятно, что существует алгоритм, более эффективный, чем перебор, который может находить решения для произвольных обобщенных конфигураций FreeCell.
- Существует 52! (т.е. 52 факториала), или приблизительно 8×1067, различных сделок. Однако некоторые игры фактически идентичны другим, поскольку масти карт произвольны или столбцы могут быть поменяны местами. С учетом этих факторов существует примерно 1,75×1064 различных игр.