A megoldás algoritmusa
Az alap algoritmus igen egyszerű:
- Az ismert számokat a táblába helyezzük.
- Megnézzük, hogy van-e olyan üres mező, amelybe csakis egy újabb szám kerülhet (kizárásos alapon). Ha van legalább egy ilyen mező, visszatérünk az előző pontra. Ha nincs, készen vagyunk.
De hogyan tároljuk az adatokat? Hogyan keressük meg az olyan mezőket, amelyeknél egyértelműen meghatározható az új érték? Egy alapos rendszertervezéssel megkaphatjuk a választ ezekre a kérdésekre.
Adatszerkezet
A Sudoku tábla 9×9 db mezőből áll. Minden egyes mezőnek van egy értéke: 1-től 9-ig, ha ismerjük, illetve 0, ha még nem. Továbbá minden mezőnél fel kell jegyezni, hogy melyek azok a számok, amiket kizártunk, tehát nem szerepelhetnek az adott mezőben.
A legegyszerőbb egy struktúrában tárolni a mezők egybetartozó adatait. Ebben a struktúrában szükség lesz egy egész számra a mező értékéhez, továbbá egy boolean elemekből álló, Lehet[1..9] nevű tömb, melynek kezdetben minden eleme Igaz.
A Sudoku tábla memóriában tárolásához fel kell vennünk egy mezok[0..8,0..8] tömböt, melynek minden eleme az előbb megbeszélt struktúrából áll. Célszerű a mezők indexelését 0-tól kezdeni, ez a későbbi számolásoknál lesz igen kedvező.
Az algoritmus lépései
Új érték beszúrása
Ha egy új számot elhelyezünk a táblában, figyelnünk kell arra, hogy bizonyos mezők már nem tartalmazhatják ugyanazt az értéket. Így az érintett mezőknél - az adott sorban, oszlopban illetve 3×3-as blokkban - a beírt számhoz tartozó Lehet értékeket Hamis-ra kell állítani.
Vigyázzunk arra, hogy nemcsak a többi mezőnél csökken a értékek lehetőségeinek száma. Abba a mezőbe ugyanis, ahová az új szám kerül, semmilyen más számot nem írhatunk a későbbiekben; a mezőhöz tartozó összes Lehet értéket Hamis-ra kell állítani.
Új érték keresése
Az algoritmus a következő:
- Sorban megnézzük az 1 és 9 közötti értékekre a 2. és 3. pontot.
- Végignézzük az összes sor/oszlop/blokk minden egyes elemét, felveheti-e az adott értéket.
- Ha egy szakaszon belül csak egy ilyen elemet találtunk, az a mező megkapja az adott értéket.
Megoldások
További megoldások
