Sudoku elemek
Feladvány
Addot egy NxN méretű tábla. Ebbe a táblába kell elhelyezni pálcikákat úgy,
hogy a táblát teljesen lefedje.
Egy m hosszú pálcika m db különböző szimbolumot tartalmaz. Úgy kell
elhelyezni a pálcikákat a táblában, hogy a tábla ne tartalmazzon olyan sort vagy
oszlpot, ami két azonos szimbólumot tartalmaz.
A pálcikák elforgathatóak és tükrözhetőek. Pl. a { 1, 2, 3 } elem ekvivalens a { 3, 2, 1} pálcikával, és behelyezhető függőlegesen és vízszintesen is a táblába.
Egy konkrét feladat
Adott egy 5x5-ös tábla.
Az pálcikáink a következőek (Jelen esetben 3 és 2 hosszú pálcikákat definiáltunk.)
- 5, 4, 3
- 4, 1, 2,
- 3, 1, 2,
- 2, 1,
- 5, 3,
- 4, 2, 3
- 5, 4, 1,
- 1, 3, 5,
- 2, 5, 4,
Algoritmus
Az algoritmus a bactracking elvét követi.
-
Inicializálunk egy üres táblát. Az elemekhez rendelünk egy sorrendet.
-
A bal fölső sarokból az első üres helyre (az algoritmus elején ez pont a bal fölső sarok, utána pedig olvasásirányba az első üres cella) elindulva megpróbálunk bepakolni egy pálcikát.
-
Ha a pálcikát sikeresen le tudtuk rakni, akkor folytatjuk a 2. lépésnél.
-
Ha nem sikerült lerakni, akkor megváltoztatjuk az elem elhelyezkedését (forgatjuk)
-
Ha nem sikerült lerakni egyik állapotában sem, akkor új element próbálunk lerarkni.
-
Ha egyik pálcikát se sikerült lepakolni, akkor felvesszük az utoljára letett pálcikát, és folytatjuk a 2. lépésnél.
-
-
A feladvány akkor van kész, ha a tábla összes cellája foglalt.
