Logikai játékok mindenkinek
Nem régen olvastam egy diplomamunkát, ami a Sudoku megfejtésével foglalkozott, és nagyon érdekesnek tartottam – nem csak ezt a részét, hanem a történeti áttekintést is, hiszen én is sokszor játszottam a logikai játékok eme darabjával, de sosem tudtam honnan is ered! A következőkben ennek a diplomamunkának egy részlete olvasható!
Diplomamunka célja a Sudoku nevű logikai játék megoldását célzó heurisztikák, stratégiák, algoritmusok ismertetése, és számos stratégia implementálásával egy megoldó program létrehozása. A program létrehozásánál a fő szempont, hogy e népszerű játék rejtvényeinek megoldását tisztán a Sudokut ismerő és sokat játszott emberek megfigyeléseiből, tapasztalataiból származó, heurisztikus algoritmusok segítségével képes legyen előállítani. Ezek a heurisztikák, vagy, ahogy az irodalmakban sok helyen említik, stratégiák, felruházzák a programot némi Mesterséges Intelligenciával. A bemutatásra kerülő stratégiák, elemzéseken, megfigyeléseken alapulnak, mellőzik a számítógép erejére támaszkodó próbálgatást. Jelenleg is rengeteg embert foglalkoztat, hogy milyen módszerek alkalmazásával lehet megoldani egyes feladványokat. Egy Sudoku feladatot számítógéppel egyszerűen meg lehet oldatni. Egyik legegyszerűbb módja ún. „brute-force” algoritmus használat. Az ilyen algoritmus lépked végig a cellákon, az üres cellába beírja az első lehetőséget, az 1-est, ellenőrzi, hogy ütközik-e valami szabályba, ha nem, lép a következő cellára oda is beírja az 1-est és ellenőriz, ha szabályba ütközik, akkor írja a következő számot és így tovább. Ha az utolsó beírt számnál is ütközés van, akkor törli és visszalép az előző cellára, egyel nagyobb értéket ad neki. Ezt addig folyatja, míg ki nem tölti a teljes feladatot. Egy ilyen algoritmus forráskódját röviden meg lehet írni, viszont a visszalépések miatt rengeteg munkát végezhet. Egy heurisztikus algoritmus sokkal izgalmasabb és érdekesebb, valamint alkalmazásukkal csökkenthetjük a lépések számát.
A Sudoku története: A rejtvény ma ismert változatát Howard Garns nyugdíjas építész és szabadúszó rejtvénytervező alkotta meg. Először 1979-ben publikálta a Dell Magazine, akkor még „Number Place” néven. Sokak szerint az ötletet Leonhard Euler „latin négyzet”-tel való munkássága ihlette. A latin négyzet egy n * n-es táblázat, amelynek soraiban és oszlopaiban n különböző szimbólum szerepel oly módon, hogy ezek mindegyike minden sorban és oszlopban pontosan egyszer fordul elő. 1984-ben a Nikoli kiadó bemutatta a játékot Japánban, a következő névvel: ????????, Suuji wa dokushin ni kagiru (jelentése: „a számjegyek csak egyszer szerepelhetnek”). Valamivel később Maki Kaji rövidítette a nevét Sudokura. A Föld többi részén 2005 környékén lett közkedvelt. A mai világban már szinte mindenki hallott róla és rengetegen teszik próbára tudásukat egy-egy könnyebb vagy nehezebb feladvánnyal. Számos újságban jelennek meg hetente, vagy naponta feladványok és több, csak Sudoku feladványokat tartalmazó könyv is jelent már meg. Az Interneten is számtalan weboldal van, ami csak a Sudokuval és megoldásával foglalkozik.
Játékszabályok: Az általános, és legelterjedtebb Sudoku egy 9 * 9-es tábla, ami kilenc darab 3 * 3-as blokkból áll. A tábla celláiban úgy kell elhelyezni a számokat 1-től 9-ig, hogy azok minden sorban, oszlopban és blokkban pontosan egyszer szerepelnek. Kezdéshez néhány cella értéke adott. A rejtvény lényege, hogy egy hiányosan kitöltött táblát kitöltsünk a szabályoknak megfelelően. A szabályos Sudoku feladatoknak egyetlen megoldása van, és ellentmondásmentesen van megadva. Az évek alatt a kezdeti szabályok változtatásával, vagy új szabályok hozzáadásával újfajta rejtvényeket állítottak elő. Ilyenek például a kisebb és nagyobb táblás verziók. Ezek is n * n-es táblák, és 1-től n-ig tartalmaznak számokat. A blokkokban lévő cellák száma ugyanúgy n mint az alap verziónál, de a méret miatt ez lehet, hogy nem négyzet alakú. Példák a kisebb és nagyobb Sudokukra: 4 * 4-es tábla (2 * 2-es blokkokkal), 12 * 12-es tábla (3 * 4-es blokkal), 25 * 25-ös tábla (5 * 5-ös blokkokkal).
A Sudoku-X-ben annyival egészül ki az alap feladat, hogy az átlókban is ugyanolyan szabály szerint kell kitölteni, mint a sorokat, oszlopokat, blokkokat. Killer Sudoku rejtvény megadás különösen érdekes. A kezdő táblán általában kevés szám szerepel, de kapunk egy második táblát is. Ezen különböző színekkel jelölt halmazok vannak, melyekben szerepel egy érték, ami azt mondja meg, hogy az adott halmazban mennyi az ott előforduló értékek összege. A Jiggsaw Sudoku esetében az a különbség a blokkok alakjában van. Általában nem négyszög alakot vesznek fel. 3D Sudoku lényegében egy Rubik kocka, ahol színek helyett számok szerepelnek 1- től 9-ig, és az a cél, hogy minden oldalon pontosan egyszer szerepeljen minden szám.
Bónizs Attila: SUDOKU ÉS HEURISZTIKA
Logikai játékok az elme karbantartásáért
A logikai játékok, úgy, mint a sakk és a malom, igazi klasszikus kedvencek, melyekkel nagyon szívesen játszottunk gyermekkorunkban, s melyeket valószínűleg gyermekinkkel is nagy örömmel osztunk meg. A logikai játékok bármely darabját is választjuk is a hétvégi családi összejövetelhez, vagy épp egy céges bulihoz, egészen biztosan nem fogunk unatkozni, hiszen nem csak megmozgatja elméket, de közben teljesen eltölt és ki is kapcsol majd minket! Logikai játékok nélkül igazán unalmas lenne az élet.
