Programozás‎ > ‎Feladatok‎ > ‎

Sudoku

Tihanyi Balázs feladata

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.


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?"
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.

Példa

Bemenet  Kimenet
0 5 0 0 0 1 4 0 0
2 0 3 0 0 0 7 0 0
0 7 0 3 0 0 1 8 2
0 0 4 0 5 0 0 0 7
0 0 0 1 0 3 0 0 0
8 0 0 0 2 0 6 0 0
1 8 5 0 0 6 0 9 0
0 0 2 0 0 0 8 0 3
0 0 6 4 0 0 0 7 0
6 5 8 2 7 1 4 3 9
2 1 3 8 9 4 7 5 6
4 7 9 3 6 5 1 8 2
9 2 4 6 5 8 3 1 7
5 6 7 1 4 3 9 2 8
8 3 1 9 2 7 6 4 5
1 8 5 7 3 6 2 9 4
7 4 2 5 1 9 8 6 3
3 9 6 4 8 2 5 7 1


Tesztadatok

Címkék

A feladat forrása: Tihanyi Balázs feladata a 2005/2006-os tanévből
Algoritmusok: összes eset generálása, kizáró feltételek kezelése

megoldás