Zkoušková úloha: Sudoku
Zadáno v pátek 7. 5.
K odevzdání v pátek 7. 5.
Zkouška je rozdělená na několik částí, které zhruba odpovídají známkám, které za ni dostanete.
- části na sebe navazují, dělejte je tedy popořadě
- můžete používat dokumentaci
- VSTUP NAČÍTEJTE Z TEXTOVÉHO SOUBORU, ten si můžete pojmenovat, jak uznáte za vhodné
- řešení odevzdávejte jako
.py
soubor - dodržujte formát vstupu a výstupu
Informace u vstupu
V souboru je zadána částečně vyplněná tabulka sudoku. Tabulka má následující strukturu:
- 9 řádků
- na každém řádku je 9 čísel 1–9 nebo značek
_
, oddělených mezerami _
značí nevyplněnou buňku
Úroveň 1
Najděte číslo, které můžete doplnit na jedno z prázdných _
míst, tak, abyste dodrželi následující dvě pravidla Sudoku:
- Na jednom řádku musí být všechna čísla různá
- V jednom sloupci musí být všechna čísla různá
ALE POZOR — ne na ledajaké takové místo, ale na místo, kde je pouze jedna možnost, jaké číslo tam podle pravidel výše doplnit. Ve výstupu napište Inserted <NUM> at position <X>, <Y>, the new table is <NEW TABLE>
.
Pokud tam žádné takové místo nebude, místo nové tabulky vypište do konzole "Sorry, there's no obvious next step"
.
Například pro vstup
1 2 3 _ 5 6 7 8 9 _ _ _ 3 _ _ 4 6 _ _ _ 7 2 _ _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _ 9 _ _ _ _ _ _ 1 _ 8 _ _ _ 4 2 _ _ _ 7 _ _ 5 _ _ _ _ _ 6 _ _ _ 3 _ _ _ _ 5 _ _ _ _ _
By výstup byl
Inserted 4 at position (4, 1), the new table is 1 2 3 4 5 6 7 8 9 _ _ _ 3 _ _ 4 6 _ _ _ 7 2 _ _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _ 9 _ _ _ _ _ _ 1 _ 8 _ _ _ 4 2 _ _ _ 7 _ _ 5 _ _ _ _ _ 6 _ _ _ 3 _ _ _ _ 5 _ _ _ _ _
Pokud míst vhodných na doplnění bude více, vyberte to, které má nejnižší souřadnici Y, popř. při rovnosti nejnižší souřadnici X. Bod 1,1 je levý horní roh tabulky.
Úroveň 2
Stejné zadání, jako úroveň jedna, ale berte v úvahu i poslední pravidlo Sudoku:
- V buňce 3x3 musí být všechna čísla různá
Například pro vstup
1 2 3 _ _ _ _ _ _ 4 5 6 _ _ _ _ _ _ 7 8 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
který by v úrovni jedna nefungoval, získáte výstup
Inserted 9 at position (3, 3), the new table is 1 2 3 _ _ _ _ _ _ 4 5 6 _ _ _ _ _ _ 7 8 9 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Úroveň 3
Rozšiřte svůj kód tak, aby umožnil uživateli ptát se na to, jaká čísla může napsat na nějakou konkrétní pozici v tabulce.
- Uživatel spustí program
- Program načte tabuku ze souboru
- Program se zeptá uživatele na dvojici souřadnic, které ho zajímají
- Uživatel určí souřadnici
- Program vypíše všechna čísla, která je možno za současného stavu na dané místo v tabulce napsat
Například tedy pro tabuku
1 2 3 _ _ _ _ _ _ 4 5 6 _ _ _ _ _ _ 7 8 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
A uživatelský vstup
4, 1
Vypíše program
The following numbers 4, 5, 6, 7, 8, 9 are valid at position 1 2 3 X _ _ _ _ _ 4 5 6 _ _ _ _ _ _ 7 8 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Povšimněte si X
, které značí pozici v tabulce, na kterou se uživatel zeptal.
Úroveň 4 (jen kdybyste se někdo nudili)
Napište program, který bude umět lehká sudoku vyřešit. Neřešte efektivitu.