Ma már ritkán kerül a kezembe papír újság. Általában a híreket, publicisztikákat a neten olvasom. Egy ideje már annyit, hogy RSS olvasót kell használnom a szelektálásra.De most nem erről van szó. Volt pár szabad percem a melóhelyen, ezért öregesen hátradőltem a kávé mellett és lapozgattam az újságot. Nem lényeges melyik volt az, egyébként egy nem mainstream hetilap, és inkább az olvasás korábban megszokott technikája vonzott, mint a tartalom. Érdekes volt újra megélni pár percre ahogy nem 2 munkahelyi feladat közt kapkodva a képernyőn nyálazom át a híreket, hanem a régi módon, kényelmesen elhelyezkedve, ráérősen, kezemben kitapintva a médiát jutok információhoz.
Az újsággal gyorsan végeztem, nem volt benne sok számomra érdekes cikk. Igazából egy másik oka a választásnak az volt, hogy angol nyelvű volt és kikapcsolódásként akartam egy kis jellemző angol újságírós szöveget olvasgatni.
A lap hátulján volt egy rejtvény. Milyen furcsa érzés volt ez is, hogy a webes hírportálokon nincs ilyen, pedig a papír újságok elengedhetetlen tartozéka volt ez annak idején, mindig azonos helyen. Ahol a keresztrejtvény szokott lenni, ott most egy Sudoku volt, egy japán játék, aminek megfejtéséért kis szerencsével egy 10.000 Ft-os vásárlási utalványt lehet nyerni, amit stílusosan az Asia Center valamelyik boltjában lehet levásárolni.
Aki nem tudja mi a Sudoku, de mondjuk suliból emlékszik a bűvös négyzetre, az igazából már csak egy lépésre van a megismerésétől. Természetesen több fajtája létezik, ezért maradjunk a legelterjedtebb formánál:
9x9 cella, mely 3x3 db 3x3 cellát magában foglaló logikai részre (továbbiakban: blokk) van osztva. A kép és a wiki cikke segít a vizualizálásban. A játék lényege, hogy a cellákba az 1-9 számjegyeket kell beírni úgy, hogy minden sorban, minden oszlopban, valamint blokkban minden számjegy csak egyszer szerepeljen. Persze kezdésnek pár szám előre be van írva, ami nehezíti a dolgot, de egyúttal kiindulási alapként szolgál a mechanikus algoritmusunkhoz. Gondoltam, ha már a cikkekkel nem sok időt töltöttem, akkor az önként kijelölt kávészünetből még van annyi, hogy ezzel az agytornával ellegyek kicsit.
Arra hamar rájöttem, hogy valahogy jelölni kéne minden üres cellában, hogy mely számjegyek jöhetnek nála szóba és akkor jó esetben kijön majd jó sok olyan cella, ami már csak egyféle lehet. Az adott sorban és oszlopban már előforduló számok ugye kiesnek (sőt, az adott blokkban találhatók is). Sőt, akkor már jobb azt jelölni, ami NEM szerepelhet az adott cellában, mert ahogy haladunk előre, csökken a szóbajöhető számok köre, ezért ne kihúzogassunk, hanem hozzáírjunk egy listához. De minden üres cellánál jelölni, hogy mi nem lehet, az egyrészt igen fáradságos, mert sok üres cella van, másrészt kivitelezhetetlen, mert kicsik a cellák.
Ha nem lennék megáltalkodott wikipédia rajongó, akkor még biztos hagytam volna időt magamnak rájönni arra, hogy egy cellában jelölni 9 lehetséges szám meglétét (ezt értsük fordítottan: nem lehet az a szám) igen elegánsan lehet pöttyök használatával, ezért mégsem olyan kivitelezhetetlen és egyúttal elég gyorsan is lehet vele haladni anélkül hogy sokat kéne rajta gondolkodni. Az angol wiki cikk kimerítően ír a megfejtési módozatokról.
A cella ugyan kicsi, de azért ahhoz még épp elég nagy, hogy 3x3 pontot elhelyezzünk benne megbízható pozícionálással, így meg is van az implementáció ezen része és ezzel igazából a mechanikus felderítés kézi algoritmusa is. Csak végig kell menni minden olyan cellán, amiben szám már be van írva és a hozzá tartozó sorban, oszlopban és blokkban az üres cellákban pöttyözni azt a pozíciót, amit a számunk kijelöl. Úgy is mondhatjuk, hogy minden cellát újabb 3x3 részre osztunk fel. Itt beugrott, hogy jobb lenne mindezt nagyban, egy Excel táblában vezetni, ahol egy cella már ezt az újabb logikai felosztást jelölné, így 27x27 excel cellát használva. (Később kiváncsiságból össze is dobtam egy ilyen excel táblát teleírva számokkal, de ott is gyorsan kiderült, hogy semmivel sem kényelmesebb és gyorsabb onnan törölgetni vagy jelölgetni a számokat, mint papíron pöttyözni, sőt épp ellenkezőleg.)
Vissza tehát a megfejtéshez: Ha megvagyunk minden cellában az összes ismert szám kizárásával, ideális esetben lesznek olyan üres cellák, amikben 8 pötty van (9-cel már egyértelműen és fatálisan túllőttünk a célon) és heuréka, megvan, hogy oda milyen számot kell írnunk. Minden egyes ilyen új számnál pedig újra végig kell szaladnunk a hozzá tartozó soron, oszlopon és blokkon és a további üres cellák pöttyeit frissíteni ezen módon. Ha szerencsénk továbbra is kitart, akkor ahogy haladunk, újabb 8 pöttyös cellák keletkeznek és végül minden cellába szám kerül.
Itt, az algoritmus biztos tudatában, a megoldást elérhető távolságban érezve jogosnak láttam a racionális go - no go döntés kérdését. Gondoltam biztos nem küldenének be olyan sokan rejtvényt ebbe a nem túl nagy példányszámban nyomott újságba, és akik mégis, azok biztos vagy tök hülyék az ilyen "bonyolult keleti" rejtvényekhez, vagy nem fáradoznának ennyit. Ezért gyakorlatilag annak eldöntése, hogy érdemes-e megfejtenem a rejtvényt túl a szórakoztatáson, lényegében annak a kérdésnek a megválaszolására redukálódott, hogy (saccom szerint) 1 óra munkával amit jó eséllyel rá kell szánni a megfejtésre, akarok-e 10,000 Ft-ot keresni? Erre elég hamar igenlő választ adtam, mert jelenlegi órabérem egyelőre még nem közelíti ezt az értéket, ezért el is kezdtem azonmód futtatni az algoritmusomat, eszközként egy ceruzát használva. Továbbra is lelkesítőleg hatott rám, hogy papírral és ceruzával ilyen jól haladok egy problémában és ezek most nem csak a puszta jegyzetelés eszközei voltak.
Gyorsan haladtam, de közben néha ellenőrző köröket futottam, mert világos volt, hogy elég egy hiba és az borítja az egész rendszert. Szerencsére a kör végén találtam 8 pöttyös cellát, így nagy magabiztossággal kanyarítottam be a kapott számot a cellába. Önbizalmam tovább nőtt azzal, hogy a kapott számot végigpöttyözve további megfelelő helyeken újabb 8 pöttyös cellákat láttam a szemem sarkából.
De aztán beütött a ménkű. Elfogytak a 8as cellák, de még nagyon sok üres cella volt hátra. Kiderült, hogy itt minőségileg újfajta problémába ütköztem, kénytelen leszek tippelni, hogy a következő cellában a lehetséges 2 szám közül melyiket teszem meg tippnek és folytatom a kitöltést abban a reményben, hogy sehol sem ütközöm ellentmondásba. Beírtam hát a tippet és dolgoztam tovább. Felcsillant a remény, mert újabb 8 pöttyös cellák keletkeztek, látszólag minden rendben volt. Aztán persze, ahogy lelkem mélyén valahol sejtettem, előbb utóbb zsákutcába futottam, megjelent egy 9 pöttyöt tartalmazó cella. Próbáltam visszatáncolni, kiradírozni az utóbbi pár lépést, de már olyan mélyen begyalogoltam a dzsungelbe, hogy nem találtam vissza, pedig még arra is volt gondom, hogy az általam beírt számok után a pöttyök helyett már kis karikákkal jelölgettem, hogy egy esetleges visszafejtésnél legalább ennyi támpontom legyen.
De belezavarodtam, a szünetnek meg már testvérek közt is vége volt, ezért feladtam. Gondoltam most akkor nem nyerem meg a 10,000-et, mert másnap reggelig kellett a megoldást beküldeni emailen, erről lecsúsztam.
Csalódottan visszatértem a computerizált székembe, ezzel gyakorlatilag egycsapásra visszaváltozva web-enabled problémamegoldóvá (szakmai ártalom). Nem tudtam ellenállni a kísértésnek, hogy hátha egy gyors választ kaphatok a wiki cikkből prózában vagy forráskódban és akkor volna még remény... Megeresztettem egy keresést. Sejtettem, hogy ha józan ésszel ilyen mechanikus megoldás létezik, akkor azt már nyilván leprogramozták mások, és akkor már miért ne egy webes alkalmazásként, tehát beütöttem a Google-ba, hogy online sudoku solver, a választ megkaptam 0,11mp alatt, rákattintottam a 2., meggyőzőnek tűnő találatra, beírtam az újságból a számokat a megfelelő helyekre, a Solve gombra kattintottam és a megoldást megkaptam 1mp alatt. Fél perccel később elégedetten dőltem hátra, hogy a megfejtés elpostázva, tutira enyém lesz a nyeremény. Papíron meg majd megcsinálom hétvégén...
