A sudoku napjaink egyik legnépszerűbb fejtörője, mellyel valószínűleg az olvasók többsége is találkozott napilapok hasábjain, rejtvényújságokban, vagy az interneten. A játék bázisa egy 9×9 cellából álló rács; a 81 cella kisebb, 3×3-as blokkokra oszlik, amelyekben elszórva néhány, 1-től 9-ig terjedő számot találunk. Az üresen maradt cellákat a játékosoknak kell kitölteni saját (ugyancsak 1-től 9-ig terjedő) számaikkal, úgy, hogy minden vízszintes sorban, függőleges oszlopban és 3×3-as blokkban az 1-től 9-ig terjedő számok pontosan egyszer szerepeljenek. A játék alapötletét a híres svájci matematikustól, Leonard Eulertől (1707-1783) eredeteztetik, de csak egy 1892-es francia napilapban publikáltak először ilyen jellegű fejtörőt. A játék mai formáját Howard Garns amerikai építész találta ki 1979-ben, de csak Japánba kerülése után terjedt el igazán. Ott először 1984-ben, a Nikoli magazinban jelent meg megoldandó rejtvényként, majd az egyre növekvő népszerűsége hamarosan világszintűvé vált. A játék japán nevéből (Suuji wa dokushin ni kagiru: a számok csak egyszer szerepelhetnek) alakult ki az általánosan elterjedt sudoku elnevezés.

A sudoku – sok más, matematikai alapokon nyugvó játékhoz hasonlóan – nem csak szórakoztató agytornaként, hanem akár kutatási témaként is szolgálhat. Dr. Makay Géza matematikus, a Szegedi Tudományegyetem docense 2005-ben kezdte el a népszerű fejtörő alaposabb vizsgálatát. Az általa kifejlesztett program különböző nehézségi szintű sudoku példák előállítására és megoldására is képes. A program működése során először megvizsgál néhány alapvető, a megoldás gyorsítását lehetővé körülményt, majd különböző – bonyolultságuk szerinti pontszámmal ellátott – algoritmusokat felhasználva kezdi el az adott példa szisztematikus megoldását. Egy sudoku példa nehézségi foka a példa megoldásában szereplő legnagyobb pontszámú megoldási módszer pontszáma. A program mindig a lehető legkisebb pontszámú módszert alkalmazza.

„A példáknak mindig egyértelmű a megoldásuk, nehézségi fokaik 0-tól akár 100-ig terjedhetnek, bár nem minden nehézségi fok érhető el. Összehasonlításképpen a napilapokban megjelent sudoku példák között (ha nem írták el) még nem találtam 2-es nehézségi fokúnál nehezebbet. Emberi ésszel a körülbelül 7-es nehézségi fokú példák oldhatóak meg” - mondta el Makay Géza.

A népszerű játék beható vizsgálata nemcsak hobbi – kiváló lehetőséget biztosít például gráfelméleti ismeretek alkalmazására; a témából hallgatói diplomamunka is született már.
„Az egész táblát egy gráfnak tekintjük, a tábla mezői a gráf csúcsai. Két csúcs akkor van összekötve, ha a nekik megfelelő mezők egy sorban, oszlopban vagy blokkban vannak. Ezen gráf részgráfjai alapján kitöltjük az adattáblát, amelyben azt tároljuk, hogy melyik mezőben milyen számok szerepelhetnek, és melyek nem. Ezek után nem marad más hátra, mint a meglévő mezők és információk alapján elindítani a módszerek keresését” - tudtuk meg a szegedi matematikustól.

Makay Géza weboldalán bárki kedvére generálhat magának különböző nehézségű sudoku példákat – saját szürkeállományunk próbára tétele mellett minden esetben megtekinthetjük a program által kínált megoldási módot is.

További információk:
Dr. Makay Géza (makayg@math.u-szeged.hu, 62/544-091)