Volná buňka

Tato varianta solitaire využívá polovinu standardního balíčku 52 karet [6] . Vyberou se z něj libovolné dvě barvy (26 karet). Jsou rozloženy do 6 sloupců: čtyři sloupce po 4 kartách a dva po 5 kartách.

Jsou použity dvě volné buňky. V základní řadě jsou samozřejmě jen dvě místa pro esa.

Karty můžete přesouvat mezi sloupci podle barvy v sestupném pořadí, jednu po druhé. V základní řadě se karty shromažďují podle barvy ve vzestupném pořadí.

Existuje i varianta solitaire s jednou barvou (13 karet). Jsou rozloženy do 5 sloupců (tři ze 3 karet a dvě ze 2 karet). Použije se jedna volná buňka a jedno základní místo pro jedno eso.

Tato varianta solitaire vždy konverguje se správnou hrou. Jedním z nejobtížnějších rozložení je balíček seřazený ve vzestupném pořadí (1. vodorovná řada - T, 2, 3, 4, 5; 2. - 6, 7, 8, 9, 10; 3. - B, D, TO). Tento problém je vyřešen ve 23 tazích [7] .

Historie

Za předchůdce „Free Cell“ lze považovat solitéry „Eight“ a „Forty Thieves“ (alias „Napoleon na Svaté Heleně“) [8] . V roce 1968 vydal M. Gardner solitérní hru pod autorstvím jistého Bakera, ale v ní byly karty složeny podle barvy. Časopis Science and Life okamžitě přetiskl solitaire, [2] pokřtil jej „Solitaire“ a pravidelně nabízel řešení záhadných nákresů.

Vynálezce Freecell Paul Alfille si jako dítě stěžoval, že většina solitaire her opustila balíček seřazený podle barev; k zahájení nové hry bylo zapotřebí dlouhé a opatrné míchání . Zavedením „černo-červeného“ pravidla zlepšil Alfill stav balíčku: i když je solitaire vyřešen, pozice je zřejmá dlouho předtím, než jsou naskládány všechny karty a část balíčku je přidána podle barvy a část - jeden po druhém [9] . Hra se ukázala jako poměrně těžká, ale neřešitelné kombinace prakticky nevypadaly.

Následně, v roce 1978 , Allfill implementoval svou hru jako součást PLATO Programmed Learning System v programovacím jazyce TUTOR . Díky vysokému (v té době) rozlišení PLATO - 512×512 - bylo možné i přes monochromatický monitor kreslit čitelné obrázky obleků.

Později Jim Horne implementoval "Free Cell" pro DOS (v textové podobě), v roce 1992  - pro Windows . [8] [10] Není známo, kde se Horn o Svobodné buňce dozvěděl – pravděpodobně se jako student zabýval PLATONEM. Microsoft zahrnul hru do Microsoft Entertainment Pack a později do Win32s . Nicméně „Free Cell“ zůstalo málo známé, dokud se neobjevilo ve standardní distribuci Windows 95 . Později byla hra zahrnuta ve všech verzích Windows až po Windows 7 . Hra byla vyhozena z Windows 8 ; je (spolu s dalšími čtyřmi solitaire hrami) k dispozici v obchodě se softwarem.

Až po představení FreeCell od Microsoftu se Olfillův vynález dostal do knih o karetních hrách. [osm]

Implementace

Microsoft

Implementace Jima Horna, publikovaná pod názvem Microsoft FreeCell , je považována za klasiku. Vývojáři třetích stran obvykle vytvářejí generátor rozložení kompatibilní s číslováním Microsoft [8] [11] ve svých programech .

Teoretický počet rozložení v solitaire je 52! nebo 8.06 10 67 . Pokud jsou rozložení s přeskupenými sloupci a přejmenovanými obleky považována za stejná, bude počet rozložení roven 1,75 10 64 . MS FreeCell obsahuje pouze 32 000 rozložení generovaných 15bitovým generátorem pseudonáhodných čísel ; vestavěná nápověda uvádí:

Předpokládá se (ačkoli to není prokázáno), že tento solitér konverguje v jakémkoli scénáři.

V obecném případě to není pravda: vysloveně neřešitelná rozložení -1 a -2 lze ve hře nastavit jako " easter egg ". Pro testování 32 000 spreadů od Microsoftu se na internetu objevil crowdsourcovaný projekt, který měl otestovat, zda jsou všechny spready skutečně řešitelné. Do projektu bylo zapojeno více než 100 zapálených hráčů; do roku 1995 nepodlehlo žádnému účastníkovi pouze zarovnání č. 11982. Navzdory skutečnosti, že problém je z hlediska počtu map NP-úplný [12] , do poloviny 21. století bylo možné implementovat poměrně rychlé vyčerpávající vyhledávání a ukázat, že pro tento scénář skutečně neexistuje žádné řešení.

Ve Windows XP byl počet spreadů zvýšen na 1 milion, prvních 32 000 spreadů bylo stejných. Kromě spreadu 11982 neexistuje žádné řešení pro spready 146692, 186216, 455889, 495505, 512118, 517776 a 781948.

Ve verzi Microsoftu jsou super tahy implementovány, ale ne úplně: pokud je více než jeden sloupec nebo nejsou žádné volné buňky, program si super tah nemusí všimnout [8] . Například s jednou prázdnou buňkou a dvěma sloupci lze přenést osm karet; [13] MS FreeCell bude migrovat pouze čtyři.

Existuje způsob, jak rychle vyhrát: stiskněte současně klávesy ⇧ Shift+ Ctrl+ F10, ve výsledném okně vyberte: "Přerušit" - vyhrát, "Opakovat" - prohrát, "Přeskočit" - zrušit.

Jiné typy

• Aisleriot  je hra solitaire.
• KPat  je solitaire hra od KDE Games .

Pravděpodobnost výhry

Podle moderních údajů se pravděpodobnost získání řešitelné kombinace odhaduje na více než 99,99 % – jedna neřešitelná kombinace na 78 000 řešitelných. Bez volných buněk se sbíhá pouze 0,2 % rozvržení. Aby bylo zaručeno, že se jakékoli zarovnání bude sbíhat, potřebujete alespoň sedm volných buněk. [osm]

Pokud pravidla zjednodušíme a umožníme přesunutí celého objednaného zásobníku bez použití volných buněk, všech 1 milion spreadů Microsoftu je rozpustných – ale zůstanou i ty potenciálně neřešitelné. [8] Protože šance na špatné zarovnání bez něj jsou extrémně malé, je takové zjednodušení považováno za pochybné.

Viz také

• Microsoft Solitaire
• šátek
• Pavouk

Poznámky

1. ↑ Název ve Windows 95
2. ↑ 1 2 3 Martin Gardner . Kombinační úkoly  // Věda a život  : časopis / Přeložil B. Koltovoi. - 1968. - č. 11 . - S. 114 .
3. ↑ Důkaz. Základ indukce : bez sloupců, n +1 karet lze přesunout na stejné buňky . Indukční krok: přeneste ( n +1) 2 m karet do ( m +1)-tého sloupce pomocí zbývajících m sloupců a buněk; pak další ( n +1) 2 m do konečné polohy; nakonec obsah ( m +1) sloupce na konečnou pozici.
4. ↑ 1 2 Vysvětlení PowerMoves Freecell
5. ↑ "Věda a život", 1976, č. 11, s. 101.
6. ↑ "Věda a život", 1978, č. 2, s. 97.
7. ↑ "Věda a život", 1978, č. 7, s. 143.
8. ↑ 1 2 3 4 5 6 7 FreeCell  FAQ
9. ↑ Rozhovor s Paulem Alfillem 
10. ↑ Microsoft FreeCell, "O"
11. ↑ Jim Horn.  Algoritmus míchání karet Microsoft
12. ↑ Malte Helmert, Výsledky složitosti pro standardní referenční domény v plánování, Artificial Intelligence Journal 143(2):219-262, 2003 ; v souboru c. 44-49  _
13. ↑ 1 buňka a 2 sloupce jsou volné, ale není možné přesunout řetěz 8 karet, viz video: https://www.youtube.com/watch?v=ZfZN5RRW9aM .