Beatrix, Erna
9 °C
24 °C

Sudokufejtő program magyar matematikustól

2012. 02. 14. 16:31
| Módosítva: 2012. 02. 14. 16:31
A tapasztalatok azt mutatják, hogy az emberi agy legfeljebb hetes nehézségű sudokukat tud megoldani, de egy szegedi matematikus programja akár százas nehézségi szintű példák előállítására és megoldására is képes.

A sudoku napjaink egyik legnépszerűbb fejtörője. A játék alapja egy kilencszer kilences négyzetrács, amelynek 81 cellája 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 csak egyszer szerepeljenek a számok.

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 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.

Algoritmusok előzik az agyat

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 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 – algoritmusokkal elkezdi az adott példa szisztematikus megoldását. Egy sudokupé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 nullátóltól akár százig 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 még nem találtam 2-esné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 nem csak hobbi: kiváló lehetőséget ad 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”.  Makay Géza weboldalán bárki  generálhat magának különböző nehézségű sudoku példákat ahol megtekinthetőek a program által kínált megoldási módok is.