Sudoku
Előszó
Rövid összefoglaló
A Sudoku egy japán játék, amely napjainkban Japántól Ausztráliáig szerte a világon százezrek kedvenc időtöltésévé vált. Több száz lap közöl naponta Sudoku-rejtvényeket, köztük az olyan tekintélyesek is, mint a The Times vagy a Die Zeit.
A „SU” azt jelenti „szám”, a „DOKU” meg azt, hogy „egyedülálló”. A Sudoku ugyanis egy olyan egy 9x9-es négyzetrács, amelyben 9 darab 3x3-as, egyenként 9 darab négyzetet tartalmazó kisebb négyzet van. Összesen tehát 81 darab négyzetből áll. A négyzetrácsban számok vannak megadva és a négyzetrács üres négyzeteibe úgy kell beírnunk a hiányzó számokat, hogy a négyzetrács mind a 9 sorában és mind a 9 oszlopában megtalálható legyen 1-től 9-ig minden egyes szám. De mindezt úgy, hogy ezeknek a feltételeknek a teljesülése mellett még az is igaz legyen, hogy valamennyi (9 darab) kis négyzetben (blokkban) is szerepeljen az összes szám 1-től 9-ig. Ez a rejtvény-megoldás azonban csak akkor érdemli ki a Sudoku elnevezést, ha a nagy négyzetrácsba az előre megadott számok olyan módon vannak megadva, hogy a rejtvénynek csak egyetlenegy megoldása van.
További leírások
A feladat
Írjunk programot, amely képes megoldani egy egyértelmű lépésekből álló Sudoku rejtvényt!
A rejtvények megfejtéséhez alapvetően két különböző technikára van szükség:
- Minden újabb lépés egyértelmű, a meglévő számokból kizárásos alapon ki lehet találni a következőt.
- Több lépésre kell előre gondolkodnunk: "Mi lenne, ha oda raknék?"
- Minden újabb lépés egyértelmű, a meglévő számokból kizárásos alapon ki lehet találni a következőt.
- Több lépésre kell előre gondolkodnunk: "Mi lenne, ha oda raknék?"
A feladat szempontjából elég, ha a program egy újabb lépéshez nem gondol végig előre több esetet, és csak az egyértelmű, kizárásos alapú helyzetek alapján tölti ki a Sudoku tábla többi részét.
Bemenet
A bemeneti fájl írja le a megoldandó Sudoku táblát. Összesen 9 sorból áll; minden sor pontosan 9 db, szóközzel elválasztott, egyjegyű számot tartalmaz. Ha egy szám 0, akkor az adott mezőnek nincs meghatározott értéke. Ha nem nulla, akkor a mező értéke maga a szám lesz (1-9).
Kimenet
A kimenet a bemenethez hasonlóan 9 sort tartalmaz, soronként pedig 9 számot, szóközzel elválasztva. Egy rejtvény sikeres megoldásakor a kimenetben csak 1 és 9 közötti számok szerepelhetnek.