Szabad sejt

Ez a pasziánsz változat a standard 52 lapos pakli felét használja [6] . Bármely két szín (26 kártya) választható ki belőle. 6 oszlopban vannak elhelyezve: négy oszlopban 4 kártya és kettőben 5 kártya.

Két szabad cellát használunk. Az alapsorban természetesen csak két hely van az ászoknak.

A kártyákat egyenként, csökkenő sorrendben válthatja át az oszlopok között. Az alapsorban a kártyákat öltönként gyűjtik, növekvő sorrendben.

Létezik egy öltönyös pasziánsz változat is (13 kártya). 5 oszlopban vannak elhelyezve (három lapból három és kettő a 2 lapból). Egy szabad cella és egy alaphely egyetlen ász számára használatos.

A pasziánsznak ez a változata mindig a megfelelő játékhoz hasonlít. Az egyik legnehezebb elrendezés a növekvő sorrendben rendezett fedélzet (1. vízszintes sor - T, 2, 3, 4, 5; 2. - 6, 7, 8, 9, 10; 3. - B, D, TO). Ez a probléma 23 mozdulattal megoldható [7] .

Történelem

A "Free Cell" előfutárai a "Nyolc" és a "Negyven tolvaj" (más néven "Napoleon on St. Helena") [8] pasziánsznak tekinthetők . 1968-ban M. Gardner kiadott egy pasziánsz játékot egy bizonyos Baker szerzője alatt, de abban a kártyák öltöny szerint voltak egymásra rakva. A Science and Life magazin azonnal újranyomtatta a pasziánszt, [2] „Solitaire”-nek keresztelve, időnként felajánlva rejtélyes elrendezések megoldását.

A Freecell feltalálója , Paul Alfille gyerekkorában panaszkodott, hogy a legtöbb pasziánsz játék öltöny szerint rendezve hagyta el a paklit; hosszas és óvatos kevergetésre volt szükség egy új játék elindításához . A „fekete-piros” szabály felállításával Alfill javította a pakli állapotát: még ha a pasziánsz meg is van oldva, a pozíció már jóval azelőtt nyilvánvalóvá válik, hogy az összes kártya felhalmozódna, és a pakli egy része a színnek megfelelően hozzáadódik. - egyesével [9] . A játék elég nehéznek bizonyult, de megoldhatatlan kombinációk gyakorlatilag nem estek ki.

Ezt követően 1978 -ban Allfill a PLATO programozott tanulási rendszer részeként implementálta játékát a TUTOR programozási nyelven . A nagy (akkori) PLATO felbontásnak köszönhetően - 512×512 - a monokróm monitor ellenére is jól olvasható képeket lehetett rajzolni az öltönyökről.

Később Jim Horne megvalósította a "Free Cell"-t DOS -hoz (szöveges formában), 1992 -ben  - Windowshoz . [8] [10] Nem ismert, hogy Horn honnan szerzett tudomást a szabadsejtről – valószínűleg diákként foglalkozott PLATON-nal. A Microsoft belevette a játékot a Microsoft Entertainment Packbe , majd később a Win32s -be . A "Free Cell" azonban kevéssé ismert volt, amíg meg nem jelent a Windows 95 szabványos disztribúciójában . Később a játék a Windows összes verziójában a Windows 7 -ig bekerült . A játékot kidobták a Windows 8 -ból; ez (négy másik pasziánsz játékkal együtt) elérhető a szoftverboltból.

Olfill találmánya csak a Microsoft FreeCell megjelenéséig került be a kártyajátékokról szóló könyvekbe. [nyolc]

Megvalósítások

Microsoft

Klasszikusnak számít Jim Horn Microsoft FreeCell néven megjelent implementációja. A külső fejlesztők általában a Microsoft [8] [11] számozásával kompatibilis elrendezésgenerátort készítenek programjaikban .

Az elrendezések elméleti száma pasziánszban 52! vagy 8.06 10 67 . Ha az átrendezett oszlopokkal és átnevezett öltönyökkel rendelkező elrendezéseket azonosnak tekintjük, akkor az elrendezések száma 1,75 10 64 lesz . Az MS FreeCell mindössze 32 000 elrendezést tartalmaz , amelyeket egy 15 bites pszeudo-véletlenszám-generátor generál ; a beépített súgó ezt írta:

Úgy gondolják (bár nem bizonyított), hogy ez a pasziánsz minden forgatókönyvben konvergál.

Általános esetben ez nem igaz: a kifejezetten megoldhatatlan -1 és -2 elrendezés beállítható " easter egg "-ként a játékban. A Microsoft 32 000-es terjedésének tesztelésére megjelent az interneten egy közösségi forrásból származó projekt, amely azt vizsgálta, hogy valóban minden szpred feloldható-e. Több mint 100 lelkes szerencsejátékos vett részt a projektben; 1995- re csak az 11982. számú igazítás nem engedett egyetlen résztvevőnek sem. Annak ellenére, hogy a probléma a térképek számát tekintve NP-teljes [12] , a 2000-es évek közepére sikerült egy meglehetősen gyors kimerítő keresést végrehajtani, és megmutatni, hogy erre a forgatókönyvre valóban nincs megoldás.

A Windows XP-ben a spreadek számát 1 millióra emelték, az első 32 000 szórás ugyanennyi volt. Az 11982-es spreaden kívül nincs megoldás a 146692, 186216, 455889, 495505, 512118, 517776 és 781948 szpredekre.

A Microsoft verzióban a szupermozgások megvalósulnak, de nem teljesen: ha egynél több oszlop van, vagy nincsenek szabad cellák, előfordulhat, hogy a program nem veszi észre a szupermozgást [8] . Például egy üres cellával és két oszloppal nyolc kártya vihető át; [13] Az MS FreeCell csak négyet fog migrálni.

Van egy módja annak, hogy gyorsan nyerjen: nyomja meg egyszerre a ⇧ Shift+ Ctrl+ billentyűket F10, a megjelenő ablakban válassza ki: "Megszakítás" - nyer, "Ismétlés" - veszít, "Kihagyás" - mégse.

Egyéb típusok

• Az Aisleriot  egy pasziánsz játék.
• A KPat  a KDE Games pasziánsz játéka .

A nyerési valószínűség

A modern adatok szerint a megoldható kombináció megszerzésének valószínűsége több mint 99,99% - egy megoldhatatlan kombináció a 78 000 megoldható közül. Szabad cellák nélkül az elrendezéseknek csak 0,2%-a konvergál. Ahhoz, hogy minden igazítás garantáltan konvergáljon, legalább hét szabad cellára van szüksége. [nyolc]

Ha leegyszerűsítjük a szabályokat, és lehetővé tesszük a teljes rendezett verem áthelyezését szabad cellák használata nélkül, akkor mind az 1 millió Microsoft-szpred oldható lesz, de az esetlegesen megoldhatatlanok is megmaradnak. [8] Mivel enélkül rendkívül kicsi az esélye annak, hogy rossz az igazítás, egy ilyen egyszerűsítés kétséges.

Lásd még

• Microsoft Solitaire
• sál
• Pók

Jegyzetek

1. ↑ Név a Windows 95 rendszerben
2. ↑ 1 2 3 Martin Gardner . Kombinatorikus feladatok  // Tudomány és élet  : folyóirat / Koltovoi B. fordítása. - 1968. - 11. sz . - S. 114 .
3. ↑ Bizonyítás. Indukciós alap : oszlopok nélkül n +1 kártya mozgatható ugyanazokon a cellákon . Indukciós lépés: vigyen át ( n +1) 2 m kártyát az ( m +1)-edik oszlopba a fennmaradó m oszlop és cella felhasználásával; majd még egy ( n +1) 2 m a végső pozícióig; végül az ( m +1)-edik oszlop tartalma a végső pozícióba.
4. ↑ 1 2 Freecell PowerMoves magyarázata
5. ↑ "Tudomány és Élet", 1976, 11. sz., p. 101.
6. ↑ "Tudomány és Élet", 1978, 2. sz., p. 97.
7. ↑ "Tudomány és Élet", 1978, 7. sz., p. 143.
8. ↑ 1 2 3 4 5 6 7 FreeCell  GYIK
9. ↑ Interjú Paul Alfille -lel 
10. ↑ Microsoft FreeCell, "Névjegy"
11. ↑ Jim Horn. Microsoft kártyakeverő  algoritmus
12. ↑ Malte Helmert, Complexity results for standard benchmark tartományok a tervezésben, Artificial Intelligence Journal 143(2):219-262, 2003 ; fájlban c. 44-49  _
13. ↑ 1 cella és 2 oszlop ingyenes, de nem lehet mozgatni egy 8 kártyából álló láncot, lásd a videót: https://www.youtube.com/watch?v=ZfZN5RRW9aM .