SG.hu

Borzasztó egyszerűek az újságok Sudoku feladványai

Bár emberi ésszel legfeljebb a 7-es nehézségi szintű fejtörők oldhatóak meg, egy szegedi matematikus programja akár 100-as nehézségi szintű sudoku 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, 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.

Hozzászólások

A témához csak regisztrált és bejelentkezett látogatók szólhatnak hozzá!
Bejelentkezéshez klikk ide
(Regisztráció a fórum nyitóoldalán)
  • polarka #3
    Ezen hf progit általában úgy oldották meg, h az üres mezőre betippelt 1 lehetőséget a gép és végigment rajta, majd ha ellentmondásra jut, akkor rossz volt a tipp? Vagy milyen módszert használtatok?
  • Argathron #2
    Ez a cikk mekkora egy bullshit hihetetlen...
  • tnm #1
    Most ebben az a lényeg (hír), hogy gráfelméleti alapokon oldja ezt meg? Mert BME-VIK BSC hatodik féléves tárgyának (Deklaratív programozás) házi feladataként olyan programot kellett írni (két prog. nyelven) is, amely megold gyakorlatilag bármilyen sudoku feladványt. (Egy tök üres 9*9 mátrixra is kigenerálja az összes lehetséges kimenetet.) A nehézség nem is a programok megírása volt, hanem az, hogy időkorlát volt a megoldásokra. (Plusz kicsit fűszerezve is volt, mert nem csak 3*3*3*3-as bemenetek voltak, hanem nagyobbak is és nem csak számok lehettek a mezőben, hanem egyéb információk is -de ez csak plusz elágaztatást jelentett, a lényegen nem változtat.)
    Simán lehetett olyan programot írni, ami (persze nem tudom milyen teljesítményű szerveren, de azért biztos nem szuperszámítógépen) 1 perc alatt kihányta 9*9-es bemenetre mind a 2048 lehetséges kimenetet.