Zotya blogja: Sudoku

A SUDOKU szabályai, története

A Sudoku egy 9 × 9 cellából álló rács. A rács kilenc kisebb, 3 × 3-as blokkra oszlik, amelyben elszórva néhány 1-től 9-ig terjedő számot találunk. Az üresen maradt cellákat a játékosok töltik ki 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ötlete Leonard Euler matematikustól ered, aki a XVIII. században élt Svájcban. Ő találta ki azt, amit ma ”latin négyzetnek” hívunk: egy k×k-s latin négyzetben az 1, 2, ..., k számok mindegyike minden sorban és oszlopban pontosan egyszer fordul elő. A név onnan származik, hogy Euler számok helyett latin betűket használt.

Egy francia napilapban 1892-ben megjelent a sudoku elődje, amelyben már a 9 × 9 cella 3 × 3-as blokkokra volt bontva. Ebben még többjegyű számok voltak, és más szabályok szerint kellett kitölteni a cellákat. A játékot mai formájában Howard Garns amerikai építész találta ki 1979-ben. A játék 1984-ben érkezett meg Japánba, ahol először a Nikoli magazinban jelent meg megoldandó rejtvényként. Az akkori elnevezésből (Suuji wa dokushin ni kagiru: a számok csak egyszer szerepelhetnek) alakult ki a mai sudoku elnevezés.

Nyilván sokan találkoztak már az ausztrál matematikus, Gordon Royle nevével, aki összegyűjtötte a mindössze 17 számot tartalmazó úgynevezett „minimum sudokukat” (lásd: http://school.maths.uwa.edu.au/~gordon/sudokumin.php). A nyilvánosságra hozott, és honlapjáról letölthető 49151 szúdokut – ez elnevezéséből is látható – úgy tartja nyilván, mint a legkevesebb számot tartalmazó rejtvények, melyek között nincs egyikből a másikba tükrözéssel, forgatással, vagy egyéb formális átalakítással előállítható változat. Mivel 16 számot tartalmazó, egy megoldást adó rejtvényt még senki sem készített, elfogadott az az állítás, hogy ilyen rejtvény nincs, bár ezt matematikailag egzakt módon bebizonyítani még senkinek nem sikerült. Néhány leírásban, amelyek e rejtvényekkel foglalkoznak, az olvasható, hogy 17-es rejtvényt nehéz elkészíteni, és egytől egyig nehéz megfejteni őket.

Az állítás második felével szeretnék vitába szállni. Mert általában igaz ugyan, hogy ha sok számot adunk meg, akkor így könnyebb rejtvényeket kapunk, de az már nem igaz, hogy a megadott számok darabszáma és a rejtvény nehézségi foka között egyértelműen lineáris az összefüggés.

Ahhoz, hogy objektívan meghatározzuk a könnyű- és nehéz rejtvény fogalmát, némi kapaszkodóra van szükségünk. A kérdésről, a matematika nyelvezetében kicsit jártas olvasónak jó olvasmány lehet Dr. Makay Géza szegedi matematikus sudokukról szóló rövid, de igen szemléletes összefoglalója (lásd: http://www.math.u-szeged.hu/Sudoku/sudoku.pdf).

Kevésbé matematikus módon megfogalmazva az alábbiak állapíthatók meg:

A legkönnyebb rejtvények olyanok, amelyekben a fejtés során mindig találunk legalább egy olyan következő helyet, ahová csak egyetlen szám írható, mert a helyhez tartozó sorban, oszlopban vagy blokkban (ez utóbbiak a rejtvény 3x3 elemből álló részei) a többi nyolc szám már előfordul (első módszer). Természetesen ezen belül is megkülönböztethetünk „könnyű és még könnyebb” rejtvényeket, attól függően, hogy egyidejűleg hány ilyen hely található menet közben. Nos, az ismert 17-es rejtvények között ilyen rejtvény egy sem akad, ami azért nem tekinthető meglepőnek. Ezzel szemben igencsak meglepő, hogy a következő nehézségi fokú – még mindig könnyűnek számító – rejtvényekből 21905 darab található, ami az összes rejtvénynek csaknem 45%-a. Ezek a rejtvények úgy fejthetők meg, hogy az előző módszer mellé még a következő, második módszert is alkalmazzuk: A fejtés során mindig található legalább egy következő olyan hely, ahová azért írható be egy szám, mert abban a sorban, oszlopban vagy blokkban az adott szám más helyre nem írható. Tehát mindössze e két szabály felhasználásával ezek a rejtvények végigfejthetők.

Ami ugyancsak érdekes, hogy az ennél nehezebb 17-es rejtvényeknek mindössze 15%-a (pontosan 7526 darab) olyan, amelyik a már említett Makay Géza által meghatározott, akár 100-ig is elmenő nehézségi fok-skálán a négyes fokot meghaladja. A négyes nehézségi fokú rejtvényről azt kell tudni, hogy az egy gyakorlott rejtvényfejtő számára minden segédeszköz, próbálgatás nélkül megfejthető. Viszont tény, hogy az átlagfejtőt egy ilyen rejtvény már igencsak megdolgoztatja.

Amit a nyomtatott sajtóban és a Web-en megjelenő sudokukról elmondhatunk: Azokban általában a legritkább esetben találkozhatunk nehéz rejtvénnyel. Amit ott nagyon nehéznek neveznek, többnyire az sem nehezebb a már említett négyes fokozatúnál. Sőt, pl. a Metró újság honlapján felkínált rejtvények esetében a legnehezebb, ott 5-ös fokozatúnak minősített rejtvények között – néhány rejtvényt megvizsgálva – kizárólag 0-s és nagyobb részt 1-es nehézségi fokú rejtvényeket találtam. Ennél komolyabb erőpróbát igénylő, és a tényleges nehézségi fokokat jobban demonstráló rejtvények találhatók a http://www.websudoku.com/ angol nyelvű honlapon, ahol az ingyen letölthető és fejthető rejtvények négy (könnyű, közepes, nehéz és ördögi) kategóriája közül választhat. De ugyanez az oldal a még ezzel sem elégedett fejtőknek – igaz már nem ingyen – az extrém kategóriát is felkínálja.

Néhány alapvető szabály, ami gyorsíthatja a SUDOKU megoldását

Ha egy cellában egy számot sikerült meghatározni, akkor azt a számot a cella sorában, oszlopában és blokkjában minden más cellából töröljük. Így gyorsan csökkenthető más cellákban a lehetőségek száma.
Ha sikerült egy szám helyét meghatározni, akkor érdemes azzal a számmal tovább foglalkozni: megnézni, hogy sikerül-e máshol kitölteni ugyanezt a számot. Ugyancsak hasznos felírni azokat a számokat, amelyeket már minden sorban/oszlopban/blokkban kitöltöttünk, hogy többet nem kell velük foglalkozni.
Ha sikerült a lehetőségek számát egy adott cellában csökkenteni, akkor érdemes annak a cellának a sorát/oszlopát/blokkját megnézni, hogy a kevesebb lehetőség lehetővé teszi-e valamelyik módszer alkalmazását.
Érdemes azokkal a sorokkal/oszlopokkal/blokkokkal foglalkozni, ahol már sok cella ki van töltve, a maradékot általában egyszerűbb kitölteni.
Az alábbi módszerekből néhány arra épít, hogy egy vagy több adott cellában csak kevés (konkrét darabszámú, általában 2–3) lehetőség fordulhat elő. Az ilyen cellákat érdemes megkeresni és a módszer eljárása szerinti kapcsolatait megnézni.
Néhány módszer arra épít, hogy egy sorban/oszlopban/blokkban csak kevés (konkrét darabszámú, általában 2–3) helyen fordulhat elő egy adott szám. Az ilyen sorokat/oszlopokat/blokkokat érdemes megkeresni és a módszer eljárása szerinti kapcsolataikat megnézni.

A SUDOKU megoldásában használható néhány módszer

1. n-es lehetőség (n ≥ 1, 2n − 2 pont): Ha egy adott sorban, oszlopban vagy blokkban van n db cella, amelyen legfeljebb n db különböző szám fordulhat elő, akkor ennek az n db számnak valamilyen sorrendben pontosan ebben az n db cellában kell előfordulnia. Tehát ez az n db szám az adott sorban, oszlopban vagy blokkban minden más cellából törölhető a lehetőségek közül.

2. n-es rejtett lehetőség (n ≥ 1, 2n−1 pont): Ha egy adott sorban, oszlopban vagy blokkban van n db szám, amelyek csak n db cellában fordulhatnak elő, akkor ennek az n db számnak valamilyen sorrendben pontosan ebben az n db cellában kell előfordulnia. Tehát az n db cellából az adott n db számon kívül minden más lehetőség törölhető.

3. Zárolt lehetőség (4 pont): Ha egy S sorban vagy oszlopban egy n szám csak egy B blokkon belül fordul elő, akkor ez az n szám a B blokkban nem fordulhat elő az S soron vagy oszlopon kívül, tehát a blokk megfelelő celláiból ez a szám törölhető a lehetőségek közül. Ebben az okoskodásban a sor/oszlop és a blokk felcserélhető, tehát a következő módszer is működik. Ha egy B blokkban egy n szám csak egy S soron vagy oszlopon belül fordul elő, akkor ez az n szám az S sorban vagy oszlopban nem fordulhat elő az B blokkon kívül, tehát a sor vagy oszlop megfelelő celláiból ez a szám törölhető a lehetőségek közül.

4. 2-es sor/oszlop X-szárny (6 pont): Ha az S1, S2 sorok vagy oszlopok olyanok, hogy azonos blokkokon mennek át, és található bennük egy olyan n szám, amely csak a B1, B2 blokkokban fordul elő, akkor ebben a két sorban/oszlopban az n számnak elő kell fordulnia mind az B1, mind az B2 blokkban. Tehát a két blokkban az adott S1, S2 sorokon/oszlopokon kívül nem szerepelhet az n szám, így ezeknek a blokkoknak a megfelelő celláiból törölhető a szám a lehetőségek közül. Természetesen az X-szárny megfogalmazható úgy is, hogy csak a sorok és az oszlopok szerepeljenek benne, sőt ebben az esetben kettőnél több sor/oszlop is szerepet játszhat:

5. n-es X-szárny (n ≥ 2, 3n pont): Ha az S1, S2, ..., Sn soron belül a k szám csak az O1, O2, ..., On oszlopokban fordulhat elő, akkor ebben az n × n-es cellarészben a k számnak minden sorban és oszlopban elő kell fordulnia pontosan egyszer. Tehát az O1, O2, ..., On oszlopokban a k szám nem fordulhat elő az S1, S2, ..., Sn sorokon kívül, így az oszlopok megfelelő celláiból a k szám törölhető a lehetőségek közül. Itt is felcserélhető a sor és az oszlop szerepe.

Definíció: Ha egy A cella egy sorban, oszlopban vagy blokkban van egy másik B cellával, akkor azt mondom, hogy az A és a B cella egy házban van.

6. XY-szárny (néha Y-szárnynak is nevezik, 7 pont): Ha az A cellában csak két szám (n1, n2) fordulhat elő lehetőségként, az A és a B cella egy házban van, a B cellában is csak két szám lehet, mégpedig n1, n3, az A és a C cellák szintén egy házban vannak, és a C cellában ugyancsak két szám lehet csak, mégpedig n2, n3, akkor az A cellában akár az n1, akár az n2 szám van, a B vagy a C cellában az n3 számnak kell lennie. Így az n3 szám törölhető minden olyan cellából a lehetőségek közül, amelyek egy házban vannak mind a B, mind a C cellával.

7. XYZ-szárny (10 pont): Ha az A és a B illetve az A és a C cellák egy házban vannak, az A cellában csak három szám (n1, n2, n3) fordulhat elő lehetőségként, a B cellában csak két szám lehet, mégpedig n1, n3, és a C cellában ugyancsak két szám lehet, mégpedig n2, n3, akkor vagy az A cellában kell az n3 számnak lennie, vagy (az előző okoskodás szerint) a B és C cellák valamelyikében az n3 számnak kell lennie. Így az n3 szám törölhető minden olyan cellából a lehetőségek közül, amelyek egy házban vannak mind az A, mind a B, mind a C cellával.

8. Erőltetett lehetőség (pont: lépések számának négyszerese): Ez gyakorlatilag nem nagyon más, mint a találgatás. Egy eddig még ki nem töltött cellában az ottani lehetőségek közül választunk egy számot, és feltesszük, hogy az a szám van abban a cellában. Elkezdjük megoldani a SUDOKU-t (általában az egyszerűbb módszerekkel), és ha ellentmondásra jutunk, akkor a kiinduló cellában nem az a szám volt, amit beírtunk, az a szám törölhető a lehetőségek közül.