Latin négyzet, avagy 2006.02.06. Sudoku probléma és számítástudomány Számokkal telnek meg a háromszor hármas négyzetek, majd a nagyobb, kilencszer kilences úgyszintén. A játék nem újkeletű, ilyesmi volt a Bűvös Kocka is, de gyökerei még messzebb, a XVIII. századi svájci matematikusig, Leonhard Eulerig nyúlnak vissza. Hasonlóan a legtöbb logikai játékhoz (sakkhoz, gohoz, Rubik-kockához, stb.) a sudoku is ideális bonyolult számítástudományi problémák megválaszolására. Sudoku-történelem A később Latin négyzetnek elnevezett játékot Euler találta ki. Az 1970-es években az amerikai Dell Magazin publikálta a svájci zseniből jócskán merítő Howard Garnes független puzzletervező által kidolgozott posztmodernkori fejtörőt. Egy évtizeddel később Maki Kaji, a japán Nikoli elnökének biztatására a cég létrehozta saját, immáron sudoku nevű, a távol-keleti szigetországban óriási népszerűségnek örvendő puzzle-változatát. Következő fontos lépésként Wayne Gould, új-zélandi származású, nyugalmazott hongkongi bíró hosszú évek munkájával fejlesztett számítógépes sudoku-programokat, majd 2004 őszén sikerült meggyőznie a londoni The Times szerkesztőit, hogy a rejtvényrovatban naponta jelentessenek meg szoftverét használó puzzle-t. Az elsőn 2004. november 12-én törhette a fejét az olvasóközönség. Néhány hónappal később az újság már saját sudoku-változattal rukkolt elő. 2005 nyarára a legjelentősebb amerikai napilapokat (New York Post, San Francisco Chronicle, USA Today) is megfertőzték a bűvös négyzetek. Külön érdekesség, hogy míg az egyre nagyobb kereslethez nélkülözhetetlenek a hatékony szoftverek, magának a játéknak a világsikere a hagyományos – írott – médiának köszönhető. (Természetesen az interneten szintén hódít; 2005. októberben pedig már az első bajnokságot is megrendezték az Egyesült Királyságban.) Egyszerű szabályok, bonyolult megoldások Több változat ismert: a kilencszer kilences a legelterjedtebb, de játsszák – mobiltelefonra könnyebben alkalmazható – négyszer négyesben, vagy ötször ötösben, hatszor hatosban, hétszer hetesben is. Sőt, az igazi függők a tizenhatszor tizenhatos, esetleg a Nikoli által nemrég bevezetett huszonötször huszonötös igézetében töltik napjaikat. Az összetettebb verziók szimpla (1-től 9-ig terjedő) számok helyett betűket, jelképeket, alkalmasint szavakat használnak. Egyikhez-másikhoz komoly számítógépes ismeretek is kellenek. A sudoku – a kilences „prototípusnál” – nyolcvanegy kockát kilenc vízszintes és kilenc függőleges sorban tartalmazó négyzet, amit további kilenc kisebb négyzetre osztanak fel. Harminc, egytől kilencig terjedő számot helyeznek el bennük. A számokat (1-9) három szabály szerint kell az üres kockákba rakni: egyetlen vízszintes, egyetlen függőleges sorban és egyetlen háromszor hármas négyzetben sem szerepelhet kétszer ugyanaz. Egy computer logikai műveleteket használva egy másodperc alatt képes abszolválni a kilencszer kilences játékot. Ugyanakkor – szélesebb skálán nézve – a lehetséges összes kombináció száma olyan magas, hogy a világ leggyorsabb gépe sem boldogulna. Algoritmusok Egyelőre nem áll rendelkezésünkre a sok-sok kombináció tesztelését helyettesítő algoritmus. Márpedig ez azt jelenti, hogy a sudoku a tíz legizgalmasabb megoldatlan matematikai probléma közé tartozó NP-egészbe (NP-complete) sorolandó, ahol P=NP. P a hatékonyan abszolválható feladatokra, míg NP azokra vonatkozik, melyeknek a megoldása eredményesen verifikálható. Például annak ellenére könnyen ellenőrizhető, helyesen töltöttünk-e ki egy sudokut, hogy maga a kitöltés rengeteg időnkbe telhet. Az ütemezés, a hálózati útválasztás, vagy a gének sorokba rendezése szintén ilyen, rengeteg fejtörést okozó feladatok. Viszont, ha az egyik legnehezebb NP-problémára – alkalmasint a sudokura – találunk megfelelő algoritmust, az összest megoldhatjuk vele. Más kérdés, hogy – noha rendületlenül folytatják a kutatásokat – a legtöbb szakértő szerint nem létezik ilyen. A játék máris hasznára vált az algoritmustervezésnek. A Cornell Egyetem Intelligens Információs Rendszerek Intézetének igazgatónője, Carla Gomes a latin négyzettel kísérletezve jutott arra a következtetésre, hogy ugyanannak a puzzle-nak számítógépes megoldása akár néhány másodpercbe, de akár időtlen időkbe is telhet. A drasztikus különbséget olyan egyszerű tények okozzák, hogy a computer másként, más sorrendben értelmezi a négyzetrácsokat. A korábbitól eltérő módszerrel kell próbálkozni – állapította meg a kutató. Észrevételeit máris figyelembe veszik hardververifikáló programok fejlesztésekor. Ő pedig változatlanul tanulmányozza, miként alkalmazunk mintákat és szabályokat sudoku közben. Cikk küldése ismerősnek Nyomtatóbarát verzió Kapcsolódó anyagok Carla Gomes Sudoku    Ágens portál AITIA Informatikai Rt.
Jogvédelem - Oldaltérkép - Impresszum Az Agent Portal kísérleti üzemeltetését az AITIA Rt végzi. Minden jog fenntartva.
BŰVÖS LATIN NÉGYZETEK, "EXTRÁKKAL" Egy-egy bûvös négyzet összeállítása a matematika történetének hajnalán még nem számított könnyû feladatnak, ezért nem csodálkozhatunk, hogy azoknak valamilyen mágikus erõt tulajdonítottak. Az utóbbi századokban sokat foglalkoztak a bûvös négyzetek matematikai tulajdonságaival, s minden méretre kidolgozták készítésük módszereit. Ezek után a figyelem a "még valamit tudó" bûvös négyzetek felé fordult. A BŰVÖS NÉGYZET n sorból és n oszlopból álló táblázat, amelynek mezõin bizonyos egész számokat helyezünk el úgy, hogy minden sorban és oszlopban, továbbá a két átlóban ugyanakkora legyen a számok összege. (Az átlókra vonatkozó kikötés gyakran elmarad.) Eredetileg az is elõírás volt, hogy a számok az 1-tõl n2-ig terjedõ egészek legyenek, ma már inkább általánosabb értelemben használják a bûvös négyzet fogalmát, és ettõl a követelménytõl eltekintenek. Már Albrecht Dürernek, a reneszánsz kor nagy német festõjének a figyelmét is egy "többszörösen" bûvös négyzet ragadta meg, és ezt építette be Melankólia címû rézmetszetének hátterébe. Ez a négyzet már Dürer korában jó ezeréves múltra tekinthetett vissza, valószínûleg Indiából került át Európába. A mûvész a sorokat kissé átrendezte, hogy az alsó sor közepére a 15 és a 14 kerüljön, jelezve mûve készítésének évét, 1514-et. (Ha a Dürer család származási helyén, a magyarországi Ajtóson maradt volna, a mester aligha rajzolgatott volna ebben az évben bûvös négyzeteket.) Dürer négyzete egyrészt teljesen korrekt: mezõin az 1-tõl 16-ig terjedõ egészek helyezkednek el, soraiban, oszlopaiban és átlóiban a számok összege mindenütt 34, másrészt az említett dátumot adó két számon kívül több egyéb különlegessége is van. Alsó és felsõ sorában a számok négyzeteinek összege is egyenlõ, és ugyanez áll a két szélsõ oszlop számaira is. A négyzetet két középvonala négy darab 2X2-es négyzetre vágja szét, ezek mindegyikében ugyancsak 34 a számok összege, de ugyanannyi a középen elhelyezkedõ 2X2- es négyzetben is. A négyzet négy csúcsánál levõ számok összege is 34, s ugyanez áll azoknak a 3X3-as négyzeteknek a sarokszámaira is, amelyeket az eredetibõl egy szélsõ sor és oszlop elhagyásával nyerünk (1. cédula), és ez a felsorolás még folytatható... A játékos elme bravúros teljesítménye a sakktáblára írt lóugrásos bûvös négyzet. Ezen ha a huszár elindul az 1- es számot tartalmazó mezõrõl, bejárhatja a sakktáblát úgy, hogy mindegyik ugrása a következõ számot tartalmazó mezõre vezet, ráadásul a 64. ugrás visszajuttathatja a kiindulási helyére. Bemutatunk egy ilyen sakktáblát (2. cédula): minden sorában és oszlopában 260 a számok összege (az átlókra ez most nem teljesül). Az igazán "szép" bûvös négyzetben minden mezõn különbözõ szám áll, egyes matematikai feladatokban azonban éppen az olyan nXn-es négyzetek vizsgálata szükséges, amelyeknek minden sorában és oszlopában ugyanaz az n darab szám áll. Az ilyen táblázat neve: latin négyzet. Egy-egy latin négyzet szerkesztése nagyon egyszerû: az elsõ sorba beírjuk valamilyen sorrendben az 1, 2, ..., n számokat, majd a következõ sorok mindegyikében ezt a sorrendet eggyel "továbbtoljuk" a felette levõhöz képest, hivatalos nevén ciklikusan permutáljuk. (A latin négyzetekben az átlók általában nem játszanak szerepet.) Érdekes kapcsolat van a 3. vázlatcédulánkon látható két 3X3-as latin négyzetet között. Helyezzük õket egymásra, és az azonos mezõre kerülõ számokat írjuk egy 3X3-as táblázatba rendezett számpárok formájában, ahol a számpár elsõ tagja az I-es, második tagja a II-es táblázatból származik. Az egyesített táblázatban nincs azonos számpár (a sorrend is számít!). Az ilyen két latin négyzeteket, amelyek egyesítésekor a létrejövõ számpárok mind különbözõk, ortogonálisnak mondjuk. Az ortogonális latin négyzetek kutatása egy nevezetes kombinatorikai feladattal indult. Az 1770-es években L. Eulernek, a zseniális svájci matematikusnak feltették a következõ kérdést: Egy díszszemlére hat különbözõ regimentbõl hathat tisztet rendelnek fel, mai rangmegjelöléssel: egy hadnagyot (1), egy fõhadnagyot (2), egy századost (3), egy õrnagyot (4), egy alezredest (5) és egy ezredest (6). Hogyan kell a díszszemlén a 36 tisztet egy 6X6-os négyzetes alakban felvonultatni úgy, hogy mind a hat sorban és hat oszlopban minden regimentbõl és minden rangból pontosan egy meneteljen? Vegyük észre, hogy ha három regimentbõl kellene három különbözõ tagú tisztet így felsorakoztatnunk, akkor elõzõ táblázatunk éppen egy ilyen díszszemle. Ha az I. táblázat a tisztek rang szerinti beosztását, a II. a regimentejük számát jelenti, akkor egyesített táblázatunk éppen a katonák kívánt elhelyezését kódolja. A magyarázat a két négyzet ortogonális voltában rejlik. A kilenc számpár különbözõsége egyúttal azt is jelenti, hogy minden lehetséges számpár elõfordul, hiszen 3 számból 9 rendezett számpár készíthetõ. A 36 tiszt problémája - a matematikai irodalomba ezen a néven került be - tehát két 6X6-os ortogonális latin négyzet szerkesztését igényli. Euler nem tudta megoldani ezt a feladatot, de sejtette, hogy nem is oldható meg; ezt azonban nem tudta bebizonyítani. Sõt, azt a sejtést is kimondta, hogy akkor sem létezik kér ortogonális nXn-es latin négyzet, ha n 4- gyel osztva 2-t ad maradékul, tehát, az n = 2, 6, 10, 14, 18, ... esetekben. Ezeknek a problémáknak a megoldásával a múlt században sokan foglalkoztak, de csak a századfordulón (1900-ban) sikerült G. Tarrynak nagyon szorgalmas munkával kimutatnia, hogy a 36 tiszt problémájának valóban nincs megoldása. Euler általánosított sejtését azonban az 1960-as évek elején egy amerikai kutatócsoport megcáfolta: szerkesztettek két 10X10-es ortogonális latin négyzetet. Bebizonyítható, hogy nXn-es latin négyzetekbõl legfeljebb n-1 olyan létezhet, amelyek közül bármely kettõ ortogonális, ha viszont ezek mind léteznek, akkor az ortogonális latin négyzetek teljes rendszerérõl beszélünk. A század elején kiderült, hogy számos súlyos kombinatorikai probléma mélyén az ilyen rendszerek létezésének kérdése rejlik. Lássunk egy példát ebbõl a problémakörbõl! Egy evezõsklub 21 versenyzõjébõl ki kell választani azt az ötöt, akik együtt evezve a legjobb eredményt érik el. Az ideális természetesen az lenne, ha összeállítanák az összes lehetséges evezõsötöst, és megmérnék mindegyiknek az eredményét. Ez azonban gyakorlatilag kivihetetlen, mert húszezernél több ötöst kellene kipróbálni. Ehelyett megelégszenek egy teljességre ugyan nem törekvõ, de azért mégis módszeres, valamennyi versenyzõt egyaránt figyelembe vevõ válogatással. Elhatározzák: úgy állítják össze a próbákra kijelölt legénységeket, hogy bármely két versenyzõ kerüljön össze egy ötösben, továbbá bármely két ötöst tekintik is, legyen pontosan egy olyan versenyzõ, amelyik mindkettõben szerepel. Megmutatható, hogy ilyen rendszer létezik, és megadható az az összesen 21 olyan evezõsötös, amely eleget tesz a megszabott feltételeket. (Ha ezt a válogatási elõírást olvasva ismerõsnek tetszik a szöveg, s eszünkbe idéz egy másikat: "bármely két pont meghatároz egy egyenest, és bármely két egyenesnek van egy közös pontja", akkor elárulhatjuk, ez a hasonlóság nem véletlen.) Ha ezt a feladatot általánosan fogalmaznánk meg, és az evezõsklub versenyzõinek számát n-nel, az egy hajóban evezõk számát k-val jelölhetnénk. Igazolható, hogy szükségképpen n=k2-k + 1, de hogy a fenti szervezés milyen k értékek esetében valósítható meg, az mindeddig még nem ismeretes. Mintegy százéves sejtés szerint k értéke csak valamely prímszám pozitív egész kitevõs hatványánál 1-gyel nagyobb szám lehet. (Mindenesetre a legkisebb ilyen rendszer: k=3=(2+1), n=9-3+1=7. Tessék megszervezni a hét versenyzõbõl a fenti "egyszerûsített" válogatót - bár ilyen kevés versenyzõ esetében az összes lehetséges hármasok száma is csak 35 lenne.) Végezetül térjünk vissza a klasszikus bûvös négyzetekhez! A gondolkodás iskolája rovatunk legutóbbi versenyében az egyik feladat megoldása egy angol nyelvû hiperbûvös négyzet volt; ez azt jelenti, hogy ha a négyzetbe írt számok helyébe a megfelelõ számnevek betûinek számát írjuk, ismét bûvös négyzetet kapunk. Ehhez kapcsolódva felvetettük a magyar hiperbûvös négyzet kérdését, tehát amelyben a magyar számnevek betûinek számai alkotnak újabb bûvös négyzetet. Korábban Bakos Tibor matematikus már közzétett ilyeneket a Középiskolai Matematikai Lapokban, de most több olvasónk figyelmét is felkeltette a játékos probléma. Szalay Endre balassagyarmati olvasónk hosszabb tanulmányt írt errõl a kérdésrõl, s nemcsak harmadrendû, hanem negyed-, sõt hatodrendû hiperbûvös négyzeteket is szerkesztett. Kovács Krisztián (Békéscsaba) számítógéppel mintegy huszonhat harmadrendû négyzetet állított elõ; Orosz Kálmán (Fislisbach, Svájc) magyar nyelvûn kívül orosz és francia nyelvû példát is küldött. Némiképp csorbította a hiperbûvösséget, ha a számot nem a szokásos, hanem a néha hivatalosan használatos formában kellett olvasni: mondjuk a kétszáztizenhét helyett kettõszáztizenhetes formában, amit a magyar nyelv megenged. (Még a hiperbûvösségben is vannak kiskapuink!) Az egyik legjobban sikerült tiszta megoldásnak Czimber László (Budapest) négyzetét tartjuk, ezt közöljük a betûk számait tartalmazó második négyzettel együtt (5. ábra), amelynek külön "szépsége", hogy a természetes számsor kilenc egymást követõ számát tartalmazza. REIMAN ISTVÁN

   DT                    D é n e s   T a m á s matematikus                                         TD

független szakértõ            

   e-mail: tdenest@freemail.hu

Latin és bûvös négyzetek a játékos alkalmazásoktól az ûrtávközlésig

Nem egyedülálló a matematika történetében, hogy egyes fejezetei a szórakozás, a játék területén fogantak és hosszabb-rövidebb fejlõdés után a matematika új fejezeteivé váltak. Ezt az utat járta be a kombinatorika egy alig 300 éves fejezete, a latin négyzetek elmélete. Különössége mégsem abban áll, hogy fejlõdésének és fõleg alkalmazásainak jelentõs része a XX. század gyümölcse, hanem abban, hogy a klasszikus numerikus gondolkodást felcserélte a struktúrák belsõ összefüggéseinek elemzésével és igen szemléletes ábrázolásával.

Jelen dolgozatomban a latin négyzetek szerteágazó, klasszikus és egészen modern alkalmazásainak és lehetõségeinek vázlatos bemutatását tûztem ki célul, a szórakoztató matematikától, a XXI. század információs társadalmában kulcs jelentõségû adatátvitelen keresztül, a kriptográfiáig[1].

Alapfogalmak és definíciók történeti illusztrációkba ágyazva

Mivel a latin négyzetek elmélete egyelõre nem képezi matematika oktatásunk törzsanyagát, így a jelen dolgozat megértéséhez az olvasónak néhány alapfogalom megismerésére lesz szüksége. Ezeket az alapvetõ fogalmakat és összefüggéseket, valamint a keletkezésük történeti hátterét ismertetem vázlatosan a következõkben.

Egy n-ed rendû latin négyzeten egy olyan n x n méretû négyzetes mátrixot értünk, amelynek soraiban és oszlopaiban az a_1, a₂,………,a_n  elemek mindegyike pontosan egyszer szerepel. Általában az a_1, a₂,………,a_n  elemek az 1,2,……,n természetes számok. Az 1/a., 1/b.ábra példát mutat egy-egy 4-ed rendû latin négyzetre.

                                 1/a. ábra 

                                                  1/b.ábra

A definícióból világosan kiderül, hogy jelen esetben nem az a_1, a₂,………,a_n  elemek számértéke számít, csupán csak különbözõségük, valamint a mátrixban elfoglalt helyük (struktúrájuk).

Egy latin négyzetet ciklikusnak nevezünk, ha egymás alatti soraiban az elemek sorrendje azonos, csak egy hellyel jobbra (vagy balra) vannak az elemek eltolva (lásd 1/b.ábra).

Egy n-ed rendû latin négyzet egy tranzverzálisán értjük n darab olyan elemét, amelyek mindegyike különbözõ sorában, illetve oszlopában helyezkedik el és nincs köztük két azonos. Az 1/a. ábrán látható latin négyzetben a satírozott négy elem például egy tranzverzálist alkot.

Két n-ed rendû latin négyzetet akkor nevezünk ortogonálisnak, ha egymásra helyezve õket, az egymás felett levõ elemekbõl alkotott párok mind különbözõek. Példaképpen bemutatjuk az l/a. ábrán szereplõ latin négyzet egy ortogonális párját (lásd 2.ábra), majd a két latin négyzet egymásra helyezésével nyert számpárokat. (Az olvasó a 3.ábra segítségével könnyen meggyõzõdhet arról, hogy a 16 számpár mind különbözõ.)

2.ábra