Vapaa solu

Tämä pasianssiversio käyttää puolta 52 kortin tavallisesta pakkasta [6] . Siitä valitaan mitkä tahansa kaksi maata (26 korttia). Ne on asetettu 6 sarakkeeseen: neljä saraketta 4 korttia ja kaksi 5 korttia.

Käytetään kahta vapaata solua. Perusrivillä on tietysti vain kaksi paikkaa ässälle.

Voit siirtää kortteja sarakkeiden välillä maun mukaan laskevassa järjestyksessä, yksi kerrallaan. Perusrivillä kortit kerätään maun mukaan nousevassa järjestyksessä.

Saatavilla on myös yksipukuinen pasianssi (13 korttia). Ne on asetettu 5 sarakkeeseen (kolme 3 kortista ja kaksi 2 kortista). Käytetään yhtä vapaata solua ja yhtä peruspaikkaa yhdelle ässälle.

Tämä pasianssin variantti sulautuu aina oikean pelin kanssa. Yksi vaikeimmista asetteluista on nousevassa järjestyksessä oleva kansi (1. vaakarivi - T, 2, 3, 4, 5; 2. - 6, 7, 8, 9, 10; 3. - B, D, TO). Tämä ongelma ratkaistaan ​​23 siirrolla [7] .

Historia

"Vapaan solun" edelläkävijöitä voidaan pitää pasianssi "Eight" ja "Forty Thieves" (alias "Napoleon on St. Helena") [8] . Vuonna 1968 M. Gardner julkaisi pasianssipelin tietyn Bakerin kirjoittamana, mutta siinä kortit pinottiin maun mukaan. Science and Life -lehti julkaisi heti uusintapainos pasianssin [2] ja kastoi sen "Solitaireksi", tarjoten määräajoin ratkaista hämmentäviä asetteluja.

Freecellin keksijä Paul Alfille valitti lapsena, että useimmat pasianssipelit lähtivät pakasta puvun mukaan lajiteltuina; Uuden pelin aloittaminen vaati pitkää ja huolellista sekoittamista . Luomalla ”musta-punaisen” säännön Alfill paransi pakan tilaa: vaikka pasianssi olisi ratkaistu, asema tulee selväksi kauan ennen kuin kaikki kortit on pinottu, ja osa pakkasta lisätään maun mukaan ja osa. - yksitellen [9] . Peli osoittautui melko vaikeaksi, mutta ratkaisemattomia yhdistelmiä ei käytännössä pudonnut.

Myöhemmin vuonna 1978 Allfill toteutti pelinsä osana PLATO - ohjelmoitua oppimisjärjestelmää TUTOR - ohjelmointikielellä . Korkean (silloin) PLATO- resoluution - 512×512 - ansiosta pukuista pystyttiin piirtämään luettavia kuvia yksivärisestä näytöstä huolimatta.

Myöhemmin Jim Horne toteutti "Free Cell" DOS :lle (tekstimuodossa), vuonna 1992  - Windowsille . [8] [10] Ei tiedetä, mistä Horn sai tietää Free Cellistä - hän luultavasti oli tekemisissä PLATON kanssa opiskelijana. Microsoft sisällytti pelin Microsoft Entertainment Packiin ja myöhemmin Win32s :iin . "Free Cell" jäi kuitenkin vähän tunnetuksi, kunnes se ilmestyi Windows 95 :n vakiojakeluun . Myöhemmin peli sisällytettiin kaikkiin Windows-versioihin Windows 7 :ään asti . Peli heitettiin pois Windows 8 :sta; se (yhdessä neljän muun pasianssipelin kanssa) on saatavilla ohjelmistokaupasta.

Vasta Microsoftin FreeCellin esittelyssä Olfillin keksintö sisällytettiin korttipeleihin liittyviin kirjoihin. [kahdeksan]

Toteutukset

Microsoft

Jim Hornin Microsoft FreeCell -nimellä julkaistua toteutusta pidetään klassikkona. Kolmannen osapuolen kehittäjät tekevät yleensä ohjelmissaan asettelugeneraattorin, joka on yhteensopiva Microsoftin [8] [11] numeroinnin kanssa .

Teoreettinen asettelujen määrä pasianssissa on 52! tai 8.06 10 67 . Jos asetteluja, joissa on uudelleen järjestetyt sarakkeet ja uudelleen nimetyt puvut, pidetään samoina, asettelujen lukumäärä on 1,75 10 64 . MS FreeCell sisältää vain 32 000 asettelua, jotka on luotu 15-bittisellä näennäissatunnaislukugeneraattorilla ; sisäänrakennettu ohje sanoi:

Uskotaan (vaikkakaan ei todistettu), että tämä pasianssi konvergoi missä tahansa skenaariossa.

Yleisesti ottaen tämä ei pidä paikkaansa: nimenomaisesti ratkaisemattomat asettelut -1 ja -2 voidaan asettaa " pääsiäismunaksi " pelissä. Microsoftin 32 000 leviämisen testaamiseksi Internetiin ilmestyi joukkolähdeprojekti , jossa testattiin, ovatko kaikki leviämät todella selvitettävissä. Yli 100 innokasta pelaajaa oli mukana projektissa; vuoteen 1995 mennessä vain linjaus nro 11982 ei antanut periksi yhdellekään osallistujalle. Huolimatta siitä, että ongelma on NP-täydellinen karttojen lukumäärän suhteen [12] , 2000-luvun puoliväliin mennessä oli mahdollista toteuttaa melko nopea ja kattava haku ja osoittaa, että tähän skenaarioon ei todellakaan ole ratkaisua.

Windows XP :ssä levitysten määrä nostettiin 1 miljoonaan, ensimmäiset 32 ​​000 leviämistä olivat samat. Levyä 11982 lukuun ottamatta ei ole ratkaisua spreadeille 146692, 186216, 455889, 495505, 512118, 517776 ja 781948.

Microsoft-versiossa supersiirrot toteutetaan, mutta ei kokonaan: jos sarakkeita on enemmän kuin yksi tai vapaita soluja ei ole, ohjelma ei välttämättä huomaa supersiirtoa [8] . Esimerkiksi yhdellä tyhjällä solulla ja kahdella sarakkeella voidaan siirtää kahdeksan korttia; [13] MS FreeCell siirtää vain neljä.

On olemassa tapa voittaa nopeasti: paina näppäimiä ⇧ Shift+ Ctrl+ samanaikaisesti F10, valitse avautuvassa ikkunassa: "Keskeytä" - voita, "Toista" - häviä, "Ohita" - peruuta.

Muut tyypit

• Aisleriot  on pasianssipeli.
• KPat on KDE Gamesin  pasianssipeli .

Voiton todennäköisyys

Nykyajan tietojen mukaan todennäköisyydeksi saada ratkaistava yhdistelmä on arvioitu yli 99,99 % - yksi ratkaisematon yhdistelmä 78 000 ratkaistavasta. Ilman vapaita soluja vain 0,2 % asetteluista konvergoi. Tarvitset vähintään seitsemän vapaata solua, jotta kaikki kohdistukset suppenevat taatusti. [kahdeksan]

Jos yksinkertaistamme sääntöjä ja sallimme koko tilatun pinon siirtämisen ilman vapaita soluja, kaikki miljoona Microsoftin leviämistä ovat liukenevia - mutta myös mahdollisesti ratkaisemattomia jää jäljelle. [8] Koska huonon kohdistuksen mahdollisuus ilman sitä on erittäin pieni, tällaista yksinkertaistamista pidetään kyseenalaisena.

Katso myös

• Microsoft Solitaire
• huivi
• Hämähäkki

Muistiinpanot

1. ↑ Nimi Windows 95 :ssä
2. ↑ 1 2 3 Martin Gardner . Kombinatoriset tehtävät  // Tiede ja elämä  : lehti / Kääntäjä B. Koltovoi. - 1968. - Nro 11 . - S. 114 .
3. ↑ Todistus. Induktion perusta : ilman sarakkeita n +1 korttia voidaan siirtää samoissa soluissa . Induktiovaihe: siirrä ( n +1) 2 m korttia ( m +1) sarakkeeseen käyttämällä jäljellä olevia m saraketta ja solua; sitten toinen ( n +1) 2 m lopulliseen sijaintiin; lopuksi sarakkeen ( m +1) sisältö lopulliseen paikkaan.
4. ↑ 1 2 Freecell PowerMoves Explained
5. ↑ "Tiede ja elämä", 1976, nro 11, s. 101.
6. ↑ "Tiede ja elämä", 1978, nro 2, s. 97.
7. ↑ "Tiede ja elämä", 1978, nro 7, s. 143.
8. ↑ 1 2 3 4 5 6 7 FreeCell  UKK
9. ↑ Paul Alfillen haastattelu 
10. ↑ Microsoft FreeCell, "Tietoja"
11. ↑ Jim Horn. Microsoft Card Shuffling  Algorithm
12. ↑ Malte Helmert, Monimutkaisuustulokset standardien vertailualueille suunnittelussa, Artificial Intelligence Journal 143(2):219-262, 2003 ; tiedostossa c. 44-49  _
13. ↑ 1 solu ja 2 saraketta ovat ilmaisia, mutta 8 kortin ketjua ei voi siirtää, katso video: https://www.youtube.com/watch?v=ZfZN5RRW9aM .