HW02: Sudoku

Vaším úkolem bude řešit pouze sudoku, která mají právě jedno řešení. Tedy taková sudoku, kde mezi žádným řádkem a sloupcem nevzniká konflikt (jinak by řešení neexistovalo) a současně každé pole sudoku má právě jednu validní hodnotu. Ostatní sudoku si budete moci dovolit označit za neřešitelná nebo nevalidní.

Z hlediska návrhu je nejzajímavější možnost uvažovat každou buňku jako množinu možných ohodnocení této buňky. Dotyčné číslo (1, 5, …​) v ní buď je, nebo není. A protože nepotřebujeme obecné řešení pro množiny libovolných prvků, ale jen číslice 1-9, můžeme množinu reprezentovat množinou bitů. Toto uspořádání přináší v praxi výhodu - sudoku v paměti zabere méně místa, protože pro uložení stačí číselný typ s alespoň 9 bity.

Sudoku tedy budeme reprezentovat 2D polem buněk - intů (resp. unsigned intů). Celé sudoku je tedy unsigned[9][9]. Díky tomu, že standard C99 garantuje, že datový typ unsigned int má alespoň 16b, můžeme spolehlivě nejnižšími 9 bity reprezentovat přítomnost čísla v buňce. Pokud je možných očíslování buňky více, bude mít buňka nastaveno více bitů na pravdivou hodnotu. Jinými slovy, na každou buňku nahlížíme jako na množinu možností. Přiřazená čísla pak jsou množinami s jediným prvkem.

Příjemným důsledkem takové reprezentace je, že ji můžeme využít pro popis naplnění sloupce/řádku/čtverce. Stačí nám sečíst všechny buňky v daném regionu, které mají pouze jeden prvek. Chybějící číslice díky této reprezentaci dostaneme obyčejnou negací spodních 9 bitů.

Políčka v sudoku budeme adresovat dvojicí indexů. Levými horním rohem jsou myšleny souřadnice (0, 0), pravým spodním rohem pak souřadnice (8, 8). Sudoku budeme do paměti ukládat po řádcích.

Zadání budete mít za úkol vypracovat formou knihovny funkcí. Abyste si mohli svou implementaci vyzkoušet, přichystali jsme si i ukázkový main.c, který je velmi podobný mainu z referenční implementace.

Funkce, které budete implementovat, můžeme rozdělit do několika logických skupin:

V dodané kostře úlohy dále najdete i důrazně doporučené pomocné funkce, jejichž vypracování a vhodné využití vám umožní snazší řešení úlohy:

Platí, že všechny své pomocné funkce píšete do svého sudoku.c. Vaše řešení se musí zkompilovat bez chyb a varování s námi dodaným sudoku.h a main.c.

Dále implementujte dvojici funkcí pro výpis a načtení sudoku. Začneme tedy požadavky na tu jednodušší.

Tato funkce vytiskne sudoku na standardní výstup tak, aby odpovídalo níže uvedenému formátu mřížky.

Platí, že za X dosadíme:

Tato funkce, jak už název napovídá, načítá sudoku. Musí si ale poradit se dvěma formáty vstupu. V obecné rovině platí:

Pokud se nepovede vstup načíst, oznamte to na jednom řádku uživateli na standardní chybový výstup a vraťte false, v opačném případě true. K vypsání na chybový výstup použijte fprintf(stderr, "…"), kde za výpustku dosadíte vaši chybovou hlášku.

Příkladem vstupu tedy může být:

Je snadné se v 81 číslicích upsat, a proto se nám bude hodit funkce is_valid(). Ta zkontroluje, že mezi nastavenými číslicemi v daném řádku/sloupci/čtverci nejsou některé číslice dvakrát, nebo že v políčku může být alespoň jedna číslice. Pro validní sudoku vrací true, pro nevalidní false bez chybového hlášení. Funkce přitom uvažuje jen čísla, která jsou již dosazena.

Funkce kontroluje jen aktuální stav, nemusí eliminovat nebo řešit sudoku. Zejména tedy neuvažuje políčka, ve kterých je možno více hodnot.

Klíčovou otázkou při řešení sudoku je, zda vůbec potřebuje řešit. Napište tedy funkci needs_solving(), která vrátí true pokud se v sudoku nachází nějaká buňka bez přiřazené unikátní hodnoty.

Dbejte přitom na to, že tato funkce nekontroluje validitu sudoku. Jinými slovy, každá z funkcí kontroluje něco jiného. Z tohoto důvodu tedy můžete předpokládat, že výsledek volání needs_solving() je definován jen pro validní sudoku.

Tyto tři funkce provádí vlastní eliminaci a slouží jako pomocné pro solve(). Návratovou hodnotou true pak signalizují provedení změny v sudoku. Vrácení false naopak signalizuje, že ke změně nedošlo.

Pokud byste při řešení narazili na sudoku, které obsahuje konflikt, tak ze solve() vraťte false.

Funkce solve() dostane na vstupu 2D pole sudoku ve výše popsaném formátu a bude podle pravidel eliminovat možnosti nenastavených číslic, dokud nebude sudoku vyřešené nebo se po eliminaci nic nezmění. Pokud se sudoku podařilo kompletně vyřešit, vrátí solve() hodnotu true. V opačném případě pak false, a to bez ohledu na to, zda byla nějaká čísla dosazena či nikoliv.

Eliminační pravidla (ilustrováno na řádku, vztahuje se nicméně i na sloupce a čtverce 3×3):

Využijte backtracking k řešení libovolného sudoku:

Testy bonus detekují automaticky. Bonus v řešení povolíte tak, že v hlavičkovém souboru sudoku.h odkomentujete níže uvedený řádek.

Napište funkci, která ze sudoku opakovaně zkusí odebrat náhodně číslice tak dlouho, dokud je sudoku řešitelné eliminací (solve(), nikoliv druhý bonus). Výsledkem budiž sudoku, ve kterém odebrání kterékoliv další číslice povede ke ztrátě možnosti získat řešení eliminací.

Tento bonus v mainu povolíte odkomentováním odpovídajícího #define v sudoku.h.

Například ze sudoku na začátku bychom mohli odebrat ještě pár čísel:

Můžete si vyzkoušet, že toto sudoku je ještě řešitelné se solve(), ale po odebrání další číslice bychom museli hádat a zkoušet možnosti. Podobně další aplikací generate() na výsledné sudoku bychom dostali již nezměněné sudoku.

Na nevalidním vstupním sudoku nic nevypisujte, stačí ve funkci solve() nepokračovat.

Vzorovou implementaci naleznete na Aise umístěnou v /home/kontr/pb071/hw02/sudoku. Součástí kostry zadání je i main použitý ve vzorové implementaci, jehož dokončením můžete začít práci na úloze.

Které přepínače zkouší kterou funkci zjistíte pomocí příkazu /home/kontr/pb071/hw02/sudoku --help.

Běžně se standardní a chybový výstup vypisuje přímo do terminálu dohromady. Pokud budete chtít výstup rozdělit, můžete si oba výstupy přesměrovat do dvou souborů, např. takto: