Ingabe ulahlekelwa kuphela ku-Tetris ngoba awudlali kahle noma awenzi amaphutha? Ngisho nanoma yisiphi isikhathi sokucabanga ngakho, ukulandelana okungalungile kwamatshe akukwazi ukusindiswa. Isici esinqumayo yimizila emihlanu emincane kanye nenombolo eyinqaba. Sicabangela inkundla yokudlala enamakholomu \(10\) kanye \(20\) nemigqa ngaphandle kwebhodi lokunamathisela (bamba): Itshe ngalinye elisha lidwetshwa ngokuzimela futhi lisatshalaliswe ngokulinganayo ukusuka kuma -tetrominoes ayisikhombisa . Umumo ngamunye uqukethe izikwele ezine ezixhunyiwe. Sonke isiqephu singaziwa kusenesikhathi.
Iqiniso lokuthi umdlalo cishe uyaphela akusho ukuthi ukulandelana okungacatshangwa kwamatshe kuyaphela. Ukulandelana okumsulwa kwe-O-stones kungadlalwa ngokungapheli: izikwele ezinhlanu ezibekwe eduze kwesinye zisusa imigqa emibili bese zikhipha ibhodi. Ku-7-Bag, isikhwama ngasinye esixutshwe ngokungahleliwe siqukethe zonke izimo eziyisikhombisa kanye; ukuphikisana kwethu kwethuba akusebenzi kulokhu. Kwethi Ulahlekelwa Kanjani e-Tetris, u-Heidi Burgiel ubonisa ukulandelana okuthi ngisho nokudlala okuphelele okungasizi: \(S,Z,S,Z,\ldots\) .
U-S no-Z yizithombe zesibuko, hhayi ukuzungezisa okuhlukile kwetshe elifanayo. Incazelo ehambisana nalokhu ichaza umqondo wejiyomethri esiwubeka lapha njengobufakazi ngokuphikisana. Isimangalo esisobala "ngesikhathi esithile kuvela amatshe angu-Z kuphela futhi akukho mugqa onyamalala nawo" akulungile. Amatshe ka-S amahlanu nje afanayo, abekwe mpo ahlinzeka ngohlelo olulandelayo ebhodini elingenalutho ekuqaleni. Izinhlamvu ezifanayo zibonisa itshe elifanayo; Amachashazi aphawula izikhala ezikhululekile:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eUmugqa omaphakathi uqedile futhi uyasuswa. Uma ulinganisa ukuhlelwa, uthola isibonelo esifanayo samatshe angu-Z. Inkinga ayisusi imigqa ngayinye, kodwa umbuzo wokuthi ungakwazi yini ukulawula konke ukungalingani okuvela kwinani elingenamkhawulo lamatshe. Masibale amakholomu ukusuka ku \(1\) kuye kokuthi \(10\) . Ngo \(b_i\) sibonisa ingqikithi yenani lawo wonke amaseli amasha abekwe kukholomu \(i\) , kuhlanganise nalawo asuswa kamuva.
\(h_i\) ibala amatshe avundlile u-S noma u-Z anekholomu emaphakathi \(i\) , \(v_i\) amatshe aqondile kumakholomu \(i\) kanye \(i+1\) . Izibali zirekhoda ukuhamba kwegeyimu, hhayi nje isitaki esibonakalayo njengamanje. Itshe elivundlile lisabalalisa amaseli alo esilinganisweni \(1,2,1\) phezu kwamakholomu amathathu, itshe elime mpo esilinganisweni \(2,2\) kumakholomu amabili. Zombili izithombe zesibuko zinebhalansi yekholomu efanayo. Uma uhlanganisa le minikelo kukho konke ukubekwa, uthola kukholamu ngayinye:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Ngaphandle kwebhodi sibeka zonke izinto zokubala kokuthi \(0\) ; ikakhulukazi \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Le ngqungquthela yonqenqema ivimbela ibhalansi ekubaleni amatshe angadlulela ngaphesheya konqenqema lwenkundla yokudlala. Ukubekwa okunjalo akuvunyelwe kumodeli yethu. Uma ukulandelana kwe-S/Z okucatshangelwayo kuqala ebhodini eseligcwalisiwe kakade, makube \(a_i\) amaseli asetshenziswa ekuqaleni kanye \(c_i\) namaseli okukhona njengamanje kukholomu \(i\) . Ngemuva kokuthi \(R\) imigqa esusiwe:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Uma nje igeyimu isaqhubeka, zonke \(a_i,c_i\) ziphakathi kuka \(0\) kanye \(20\) . Ngakho-ke \(|b_i-b_j|\leq40\) iyasebenza. Uma ibhodi lingenalutho ekuqaleni \(20\) kwanele. Umugqa ngamunye osusiwe ususa iseli elilodwa ncamashi kukholomu ngayinye. Yingakho inani lemigqa esusiwe lincishiswa lapho kuqhathaniswa amakholomu amabili, ngisho noma izibali zamaseli asethiwe ziqhubeka nokukhula. Ubala amaseli athathiwe esikhundleni sobude besitaki; Amasayizi amabili ayahluka uma kuziwa emigodini. Uma sibhala lo mkhawulo ngokuvamile ngokuthi \(D\) , uphumela onqenqemeni lwesokunxele noma kwesokudla:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Kumapheya ekholomu engaphakathi sengeza umehluko wekholomu emibili ekhawulelwe: \(b_4-b_3\) kanye \(b_2-b_1\) kwesokunxele, \(b_7-b_8\) kanye \(b_9-b_{10}\) kwesokudla. Ngemva kokufaka ibhalansi yekholomu, izinto zokubala phakathi kwazo zikhansele ngokunembile. Lokhu kushiya kuphela iminikelo engeyona emibi ohlangothini ngalunye olungakwesokunxele, oluboshwe ngokuhlanganyela ngu \(2D\) . Lokhu kuphinda kusinikeze umkhawulo ophezulu wezinombolo zokubeka ezihambisanayo zamapheya amabili angaphakathi:
$$\begin{aligned}2v_4+h_4+h_5&=(b_4-b_3)+(b_2-b_1)\\&\leq2D,\\2v_6+h_6+h_7&=(b_7-b_8)+(b_9-b_{10})\\&\leq2D.\end{aligned}$$
Uma sengeza ukungalingani okune, itshe ngalinye elivundlile libalwa kanye ncamashi. Izinhlobo ezine zokubekwa okuqondile kwe-cross-track nazo zinama-coefficients amahle. Amatshe avundlile athatha amakholomu amathathu ngakho-ke awangeni ngokuphelele kwenye yezindlela zamakholomu amabili ezicatshangelwa kamuva. Ngamatshe aqondile, sihlukanisa amathrekhi ngokwekholomu yesokunxele. Njengoba zonke izinto zokubala zingezona ezinegethivu, ayikho kule minikelo engakhanselwa omunye:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Ukubekwa okuvundlile nokubekwa okuqondile okunekholomu engakwesokunxele eqondile ngakho-ke kungenzeka izikhathi ezingaphezu kwezingu \(120\) ebhodini elingenalutho noma \(240\) izikhathi kunoma yiliphi ibhodi eligcwaliswe ngaphambili. Lokhu kuyisibopho esingaphezulu, hhayi isimangalo sokuthi empeleni singafezwa. Kunoma ikuphi, lezi zinyathelo zokugwema azikwazi ukusetshenziswa kaningi. Manje ake sicabange ukuthi ungadlala ngokulandelana okushintshanayo unomphela.
Ngemva kwenombolo yokugcina enomkhawulo yokunyakaza okugwedlwayo, ukubekwa okuqondile kuphela emigwaqweni engaguquki emihlanu engenzeka: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Amajamo afanayo angena komunye nomunye ngephethini efana nesinyathelo: okuphansi kuhlangana phezulu okufanayo kwetshe langaphambilini. Ukushintsha ukusuka ku-S kuye ku-Z noma okuphambene nalokho kushiya igebe ububanzi beseli elilodwa namaseli amabili ukushona. Imininingwane ibonisa itshe elingu-Z phezu kwetshe elingu-S; kokubili “o” maka igebe:
.Z
ZZ
Zo
So
SS
.SElinye itshe elime mpo emzileni ofanayo alikwazi ukugcwalisa lesi sikhala: ikholomu yalo yesibili ingashayisana namaseli akhiwe angomakhelwane. Ukususa imigqa akusizi futhi inqobo nje uma igebe livuliwe, ngoba yomibili imigqa ayiphelele. Ukulungisa kudinga eyodwa yezingoma ezihlukene esezivele zingabaliwe noma ukubekwa okuvundlile. Ngemuva kokunyakaza kokugcina, izikhala ezinjalo zihlala njalo. Inombolo engapheli yezikhala ezintsha, ezingahlangani azikwazi ukuvela ebhodini elinomkhawulo.
Ngenxa yalokho, kungaba nenani elilinganiselwe kuphela lezinguquko efomini kumathrekhi. Umzila ongenalutho ekuqaleni awukushintshi lokhu: itshe lakho lokuqala elingu-S noma u-Z selivele lishiya igebe lekholomu eyodwa phansi elingakwazi ukuvalwa ngokuqhubekayo ngokudlala komzila omsulwa. Emdlalweni ocatshangwa ukuthi awunamkhawulo, umzila ngamunye kufanele ubambe inani elingapheli lamatshe. Uma umzila ubuzohlala ungakathintwa ngesikhathi esithile, inani elilinganiselwe kuphela lamaseli elingafakwa emigwaqweni esele ngenxa yebhalansi yekholomu elinganiselwe.
Ngakho-ke sifinyelela eqophelweni lapho yonke imizila emihlanu seyihlala unomphela futhi yabelwa ngokuqinile efomini. Kusukela kuleli qophelo kuqhubeke sibala \(t\) amatshe engeziwe futhi \(n_j(t)\) nenombolo yethrekhi \(j\) . Ngalinye lalawa matshe linikela ngamaseli amabili kukholamu ngayinye yomzila walo. Ngenxa yokuthi ukususwa kwemigqa kuphatha wonke amakholomu ngokulinganayo, umehluko \(n_j(t)-n_k(t)\) uhlala unomkhawulo. Esikhathini eside, yomihlanu imizila kufanele ngamunye abambe ingxenye yesihlanu yamatshe:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Uma \(k\) wemizila emihlanu igcinelwe ama-S-stones, isabelo sabo kufanele sibe ngu \(k/5\) . Nokho, ngokulandelana okushintshanayo ithi \(1/2\) : kusiqalo ngasinye izinombolo zamatshe u-S no-Z zihluka ngokuningi \(1\) . Ukuhlukaniswa kwemizila kuzodingeka kugcwalise zombili izingxenye ngesikhathi esisodwa. Nokho, ingxenye yesigamu ayikwazi ukumelwa njengesamba sengxenye yesihlanu ephelele. Yilapho imvamisa yamafomu ashintshanayo kanye nenombolo eyinqaba yamathrekhi asetshenziswa ngokulinganayo kuhlangana khona. Lokho kungaba yimpoqo:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Inombolo yemizila iyinombolo ephelele. Lokhu kungqubuzana kuqeda ukucatshangwa kwegeyimu engapheli. Ingxabano iphinde ibonise ukuthi kungani ububanzi bebhodi buyingxenye yalo: Ngezitimela ezine, ukuhlukaniswa kwezitimela ezimbili ze-S kanye nezimbili Z ngeke kukhishwe yilokhu kungqubuzana. Ngobufakazi obungahleliwe sidinga ubude bebhulokhi obulinganiselwe \(N\) obuholela ekulahlekelweni kungakhathaliseki ibhodi lamanje. "Wonke amasu alahlekelwa ngesikhathi esithile" kuphela akwanele.
Ukufana kulandela inombolo elinganiselwe yezifunda ezingaba khona. Ngemva kokubekwa ngakunye okuqediwe, kunamaphethini okuhlala \(2^{200}\) kakhulu. Kuphinde kube nolwazi lokuthi u-S noma u-Z uyavela ngokulandelayo, okusho ukuthi inani eliphezulu \(2^{201}\) lithi. Uma ubungasinda \(N=2^{201}\) amatshe, \(N+1\) uthi ngaphambi nangemuva kwalokhu kunyakaza bekungaba nokuphindaphinda. Ngenxa yebhodi elifanayo kanye nesimo esilandelayo esifanayo, ukuhamba okusemthethweni phakathi kungaphinda kuphindwe noma yiziphi izikhathi: igeyimu engapheli isanda kukhishwa.
Umkhawulo uphinda ubala amaphethini ebhodi angafinyeleleki futhi awubikezeli ubude begeyimu obusebenzayo. Ukubala kwejiyomethri kaBurgiel kunikeza imingcele emincane; lapha \(N\) okuphelayo kwanele. Isebenza kuwo wonke ama-assignment okuqala avumelekile kanye nezigaba zombili zokulandelana kwe-S/Z. Ake sihlukanise ukulandelana okungahleliwe okungapheli kube amabhulokhi ahlukene obude \(N\) . Ibhulokhi ngayinye ilandelana ngokuqondile \(S,Z,S,Z,\ldots\) okungenzeka \(q=7^{-N}>0\) . Amabhulokhi azimele. Ngakho-ke kungenzeka ukuthi awekho amabhulokhi \(m\) wokuqala aqukethe lokhu kulandelana:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Ngakho-ke ngamathuba okuthi \(1\) ibhulokhi ebulalayo izovela ngesikhathi esithile, ngaphandle uma umdlalo uphela ngaphambi kwalokho. Lokhu kusebenza nanoma yisiphi isikhathi sokucabanga ngakho kanye nolwazi oluphelele lwemiphumela. Lokhu akuholeli esikhathini esifushane somdlalo ongokoqobo, futhi isiqalo esibi sisodwa akusho ukunqotshwa: Opopayi abalandelayo babonisa ukulandelana okuxubile okubalwe kusengaphambili okuyisihlanu, ngakunye kufinyelela ebhodini elingenalutho ngemva kokubekwa kwemibhoshongo eyisishiyagalolunye engashintshiwe. Akayona i-bot ye-Tetris yendawo yonke.