Szúdoku

A Wikipédiából, a szabad enciklopédiából
Kezdő szintű szúdokurejtvény...
...a megmaradt lehetőségek...
...és az egyértelmű megoldás

A szúdoku (japánul 数独, angolos átírással sudoku) egy logikai játék, melyben megadott szabályok szerint számjegyeket kell elhelyezni egy táblázatban.

A szúdoku[szerkesztés | forrásszöveg szerkesztése]

A „szúdoku” név egy hosszabb japán kifejezés rövidítése. Az eredeti név jelentése: „a számjegyek csak egyszer szerepelhetnek” (数字は独身に限る, szúdzsi va dokusin ni kagiru). Ez a japán Nikoli Co. Ltd. bejegyzett védjegye.

A megoldott szúdoku egy speciális latin négyzet. Latin négyzetekkel kapcsolatos munkássága miatt sokan úgy tartják, a játék ötlete Leonhard Eulertől származik.

A játék ma ismert változatát az amerikai Howard Garns alkotta meg 1979-ben. A rejtvényt a Dell Magazines adta ki Number Place címmel. A játék 1986-ban nagy népszerűségre tett szert Japánban, mikor a Nikoli kiadta a játék japán változatát. A nemzetközi siker 2005-ben érkezett el.

A szúdoku meglepően egyszerű szabályokon alapul – igazán nem az a fajta rejtvény, amiről azt gondolnánk, hogy álmatlan éjszakákat okoz. Egy 9 x 9 négyzetből álló nagy négyzetben kell elhelyezni a számokat 1-től 9-ig úgy, hogy egy tetszőleges sorban, oszlopban és háromszor hármas négyzetben mindegyik szám csupán egyszer forduljon elő. Segítségül bizonyos számokat előre megadnak.

Változatai[szerkesztés | forrásszöveg szerkesztése]

Renban szúdoku
Killer szúdoku
Szamuráj szúdoku
„Nagyobb” szúdoku

A hagyományos szúdokukban minden mező több olyan blokk része, mely blokkban minden szám (betű) pontosan egyszer szerepelhet. A nem hagyományos szúdokukban a mezőre más szabály is vonatkozik.

Hagyományos szúdokuk[szerkesztés | forrásszöveg szerkesztése]

Négyzet alakú változatok (zárójelben az egyes blokkok mérete):

  • Kisebb táblás verziók: 4×4 (2×2), 6×6 (2×3) és 8×8 (2×4).
  • Nagyobb táblás verziók: 12×12 (3×4), 16×16 (4×4), 20×20 (4×5) és 25×25 (5×5).
  • Szúdoku X: az átlókat is a szabályoknak megfelelően kell kitölteni.
  • 3D szúdoku: a szúdoku háromdimenziós változata több formában létezik, például a Sudokube, amit Rubik Ernőnek köszönhetünk.

Az X-szúdoku annyiban különbözik a többitől, hogy az átlóbeli elemek nem három (sor, oszlop, blokk), hanem négy blokkhoz tartoznak.

Nem négyzetes változatok:

  • Szamuráj szúdoku: több négyzetes szúdoku egyesítése.
  • Renban (amőba) szúdoku: ugyanazok a szabályai mint az eredetinek, de nem szabályos 9x9-es területek vannak, hanem szabálytalan, egybefüggő területek vannak.

Az „összenőtt” shúdokuk számos más verziója ismert a szamuráj szúdokun kívül.

Az amőba shúdoku mindössze annyiban különbözik a szokásosaktól, hogy a blokkok nem négyzet alakúak. Ez az ember számára (aki vizuális információkat használ a megfejtéskor) nagy különbségnek tűnik; a számítógép „észre sem veszi” a különbséget. A lényeg ui. nem az, hogyan helyezkednek el a blokk mezői, hanem az, hogy mely mező mely blokkban szerepel.

Nem hagyományos szúdokuk[szerkesztés | forrásszöveg szerkesztése]

Az ilyen szúdokukban minden mező a szokásos három hagyományos blokk tagja (sor-, oszlop ill. blokk), és ezen felül valamilyen más típusú reláció is érvényes rá:

  • Szúdoku gusu: a szürkével megjelölt mezőkbe csak páros számok (2,4,6,8) kerülhetnek, egyébként a szabályok az eredetiek.
  • Killer (gyilkos) szúdoku: az eredeti szabályokon felül a megjelölt területeken levő számok összege is adott.
  • Nagyobb szúdoku: az egy blokkhoz tartozó szomszédos mezőknél adott, melyik elem a kisebb ill. nagyobb.

Világbajnokságok[szerkesztés | forrásszöveg szerkesztése]

  • Az első szúdoku-világbajnokságot 2006. március 10. és 12. között rendezték meg az olaszországi Luccában. A versenyt egy 31 éves cseh könyvelő, Jana Tylová nyerte.
  • A második szúdoku-világbajnokságra 2007. március 28. és április 1. között került sor a cseh fővárosban, Prágában. Az egyéni versenyt az amerikai Thomas Snyder nyerte, a csapatversenyben pedig Japán diadalmaskodott. Hazánk csapatversenyben a negyedik helyet szerezte meg.
  • A harmadik szúdoku-világbajnokságot 2008. április 14. és 17. között az indiai Goában rendezték meg. Az egyéni versenyt ezúttal is az előző évi bajnok amerikai Thomas Snyder nyerte, a csapatversenyben pedig a cseh csapat vitte el a pálmát.
  • A negyedik szúdoku-világbajnokság 2009. április 24. és 27. között a szlovákiai Zsolnán zajlott. Az egyéni versenyt a lengyel Jan Mrozowski, a csapatversenyt pedig a házigazda Szlovákia nyerte.
  • Az ötödik szúdoku-világbajnokságon, amely 2010. április 29. és május 2. között Philadelphiában zajlott, egyéniben ezúttal a lengyel Jan Mrozowskinak sikerült dupláznia, csapatban pedig Németország lett az első. A magyar csapat a harminc induló nemzet között a tízedik helyen végzett.
  • A hatodik világbajnokságot 2011. november 6. és november 11. között hazánkban, Eger városában rendezték, az amerikai Thomas Snyder nyerte egyéniben, csapatban a németek maguk mögé utasították az ezüstérmes cseh és a bronzérmes amerikai együttest. A magyar csapat a 19. lett.
  • A hetedik szúdoku-világbajnokságnak 2012. október 1. és október 3. között a horvátországi Krajlevica adott otthont. Egyéniben Jan Mrozowski, csapatban pedig Japán nyert, a magyar csapat a nyolcadik lett ezúttal.

Számítógépes megoldások[szerkesztés | forrásszöveg szerkesztése]

Többen foglalkoztak már szúdoku problémák számítógépes megfejtésével, de mindezideig nem volt sikeres általános számítógépes megoldás. A helyzet azonban radikálisan megváltozott az utóbbi időkben. Két, amerikában, a Notre Dame egyetemen (teljes név University of Notre dame du Lac) a matematika egyik ágában, bonyolult számítástechnikai optimálás algoritmus problémáin (angolul: boolean SATisfiability problem) dolgozó magyar matematikus Toroczkai Zoltán és Ercsey-Ravasz Mária kidolgozott egy általános megoldást, ami nemcsak hogy sok töprengés nélkül megold egy szúdoku problémát, hanem a feladatot rettentően gyorsan is elvégzi.[1]

A kutatók azonban úgy látják, hogy algoritmusos megoldásuknak lehet ipari és tudományos (például számítástechnikai ill. biológiai) alkalmazása is számos és változatos problémák megoldására.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. [1] Magyarul francából:Kutatók találnak egy képletet szúdoku prolémák megoldására

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Linkgyűjtemények[szerkesztés | forrásszöveg szerkesztése]