Projekt 3 — Křížovka (Crossword)

Napiš AI, která vytváří křížovky.

$ python generate.py data/structure1.txt data/words1.txt output.png
██████████████
███████M████R█
█INTELLIGENCE█
█N█████N████S█
█F██LOGIC███O█
█E█████M████L█
█R███SEARCH█V█
███████X████E█
██████████████

Kdy úlohu dokončit

Do 2027-06-30T23:59:00+00:00.

Jak získat pomoc

1. Ptej se prostřednictvím Ed!
2. Ptej se v kterékoli komunitě CS50!

Východiska

Jak bychom mohli vytvářet křížovku? Máme-li její strukturu, tedy políčka určená k vyplnění písmeny, a seznam použitelných slov, hledáme slova pro jednotlivé svislé a vodorovné řady políček. Takový problém lze modelovat jako úlohu splňování omezujících podmínek. Každá řada políček je proměnnou, jejíž hodnotu musíme určit: slovo z domény možných slov, které řadu vyplní. Uvažujme následující strukturu křížovky.

Máme zde čtyři proměnné odpovídající čtyřem slovům křížovky, očíslovaným na obrázku. Každou proměnnou definují čtyři hodnoty: počáteční řádek, její i, počáteční sloupec, její j, směr slova, svisle či vodorovně, a délka. Proměnná 1 je například dána řádkem 1, při indexování od 0 shora, sloupcem 1, opět od 0 zleva, směrem across a délkou 4.

Stejně jako u mnoha úloh splňování podmínek mají proměnné unární i binární omezení. Unární omezení vyplývá z délky. U proměnné 1 by například hodnota BYTE podmínku splnila, ale BIT ne, protože má nesprávný počet písmen. Hodnoty nesplňující unární podmínky proto můžeme z domény ihned odstranit.

Binární omezení vyplývají z průniků se sousedními proměnnými. Proměnná 1 má jediného souseda, proměnnou 2; proměnná 2 má dva, proměnné 1 a 3. Každá dvojice sousedů sdílí jedno políčko. Průnik vyjádříme indexy znaků v obou slovech, na nichž musí být stejné písmeno. Průnik proměnných 1 a 2 může být dvojice (1, 0): znak proměnné 1 na indexu 1 se musí rovnat znaku proměnné 2 na indexu 0, opět při indexování od nuly. Průnik proměnných 2 a 3 tedy vyjadřuje dvojice (3, 1): znak 3 hodnoty proměnné 2 se musí shodovat se znakem 1 hodnoty proměnné 3.

Přidáme ještě omezení, že všechna slova musejí být různá: stejné slovo se v křížovce nesmí opakovat.

Úkolem je napsat program, který najde vyhovující přiřazení: každé proměnné přiřadí jiné slovo z daného slovníku a splní všechna unární i binární omezení.

Začínáme

• Stáhni dodaný kód z https://cdn.cs50.net/ai/2023/x/projects/3/crossword.zip a rozbal jej.

Porozumění zadání

Projekt obsahuje dva soubory Pythonu: crossword.py a generate.py. První je celý hotový; ve druhém musíš některé funkce implementovat.

Nejprve se podívej na crossword.py. Definuje třídy Variable, která představuje proměnnou v křížovce, a Crossword, která představuje křížovku samotnou.

Při vytvoření Variable určujeme čtyři hodnoty: řádek i, sloupec j, směr, buď konstantu Variable.ACROSS, nebo Variable.DOWN, a délku.

Třída Crossword pro vytvoření křížovky potřebuje structure_file, který určuje strukturu: _ znamená prázdné políčko a jakýkoli jiný znak nevyplňované políčko. Dále potřebuje words_file, seznam použitelných slov po jednom na řádku. Ve složce data najdeš tři příklady každého souboru; můžeš vytvořit i vlastní.

Každý objekt křížovky crossword uchovává zejména tyto hodnoty:

• crossword.height je celé číslo vyjadřující výšku křížovky.
• crossword.width je celé číslo vyjadřující šířku křížovky.
• crossword.structure je dvourozměrný seznam struktury křížovky. Pro platný řádek i a sloupec j má crossword.structure[i][j] hodnotu True, je-li políčko prázdné a má se vyplnit znakem, jinak False, protože se nevyplňuje.
• crossword.words je množina všech slov, ze kterých lze při vytváření křížovky vybírat.
• crossword.variables je množina všech proměnných křížovky, z nichž každá je objektem Variable.
• crossword.overlaps je slovník mapující dvojici proměnných na jejich průnik. Pro dvě různé proměnné v1 a v2 má crossword.overlaps[v1, v2] hodnotu None, pokud se neprotínají, nebo dvojici celých čísel (i, j), pokud se protínají. Dvojice (i, j) znamená, že i-tý znak hodnoty v1 musí být stejný jako j-tý znak hodnoty v2.

Objekty křížovky také podporují metodu neighbors, která vrátí všechny proměnné protínající danou proměnnou. crossword.neighbors(v1) tedy vrátí množinu všech sousedů proměnné v1.

Dále se podívej na generate.py. Třídu CrosswordCreator používáme k řešení křížovky. Nový objekt CrosswordCreator dostává vlastnost crossword typu Crossword, se všemi vlastnostmi uvedenými výše. Každý CrosswordCreator má také domains: slovník přiřazující proměnným množiny možných slov. Nejprve jsou v každé množině všechna slova našeho slovníku; později napíšeme funkce, které domény omezí.

Pro testování už máš některé funkce hotové. print vypíše do terminálu křížovku podle přiřazení; každé přiřazení zde i jinde představuje slovník proměnných a odpovídajících slov. save vytvoří soubor obrázku podle přiřazení; pro tuto funkci budeš případně potřebovat pip3 install Pillow. Pomocná funkce letter_grid, využívaná funkcemi print i save, vytváří dvourozměrný seznam znaků na odpovídajících pozicích. Patrně ji nebudeš muset volat sama, ale můžeš.

Funkce solve provádí tři kroky. Nejprve volá enforce_node_consistency, která prosadí uzlovou konzistenci: každá hodnota domény musí splňovat unární omezení. Pak volá ac3 pro hranovou konzistenci a binární omezení. Nakonec zavolá backtrack s prázdným přiřazením, tedy prázdným slovníkem dict(), a pokusí se najít řešení.

Funkce enforce_node_consistency, ac3 a backtrack ale zatím spolu s dalšími nejsou implementované. Zde začíná tvoje práce!

Specifikace

V generate.py dokonči enforce_node_consistency, revise, ac3, assignment_complete, consistent, order_domain_values, selected_unassigned_variable a backtrack, aby AI vytvářela úplné křížovky, pokud je to možné.

Funkce enforce_node_consistency má upravit self.domains tak, aby každá proměnná byla uzlově konzistentní.

• Uzlová konzistence znamená, že každá hodnota domény splňuje unární omezení proměnné. V křížovce tedy každé přípustné slovo musí mít tolik písmen, kolik činí délka proměnné.
• Protože self.domains je slovník proměnných a množin hodnot, hodnotu x z domény proměnné v odstraníš voláním self.domains[v].remove(x).
• Funkce nemusí nic vracet.

Funkce revise má zajistit hranovou konzistenci proměnné x vzhledem k y.

• x i y jsou objekty Variable, které představují proměnné křížovky.
• x je hranově konzistentní s y, pokud pro každou hodnotu domény x existuje možná hodnota domény y bez konfliktu. Konflikt znamená, že dvě proměnné požadují pro společné políčko různé znaky.
• Pro hranovou konzistenci x s y odstraň z domény x všechny hodnoty, které nemají odpovídající přípustnou hodnotu v doméně y.
• Průnik dvou proměnných, pokud existuje, najdeš v self.crossword.overlaps.
• Doména y musí zůstat nezměněná.
• Pokud se doména x změnila, funkce vrátí True; jinak vrátí False.

Funkce ac3 má algoritmem AC3 prosadit hranovou konzistenci problému. Té dosáhneme, pokud všechny hodnoty každé domény splňují binární omezení příslušné proměnné.

• AC3 udržuje frontu hran ke zpracování. Volitelný argument arcs určuje jejich počáteční seznam. Je-li arcs None, začni frontou všech hran problému. Jinak začni pouze hranami ze seznamu arcs; každá je tuple (x, y) proměnné x a jiné proměnné y.
• V AC3 postupně reviduješ každou hranu fronty. Po změně domény může být potřeba přidat do fronty další hrany, aby zůstaly konzistentní.
• Při implementaci ac3 může být užitečné volat revise.
• Odstraníš-li při prosazování konzistence všechny zbývající hodnoty některé domény, vrať False: problém nemá řešení, protože proměnné nezbývá žádná hodnota. Jinak vrať True.
• V této funkci nemusíš zajišťovat jedinečnost slov; tuto kontrolu implementuješ v consistent.

Funkce assignment_complete má podle názvu zkontrolovat úplnost daného assignment.

• assignment je slovník s objekty Variable jako klíči a řetězci představujícími přiřazená slova jako hodnotami.
• Přiřazení je úplné, pokud každá proměnná křížovky má hodnotu, bez ohledu na její obsah.
• Funkce vrátí True při úplném přiřazení, jinak False.

Funkce consistent má ověřit konzistenci daného assignment.

• assignment je slovník s objekty Variable jako klíči a řetězci přiřazených slov jako hodnotami. Nemusí být úplný: některé proměnné v něm nemusejí být přítomné.
• Přiřazení je konzistentní, pokud splňuje všechna omezení: hodnoty jsou různé, každé slovo má správnou délku a sousední proměnné nejsou v konfliktu.
• Funkce vrátí True při konzistentním přiřazení, jinak False.

Funkce order_domain_values má vrátit seznam všech hodnot domény var seřazený podle heuristiky nejméně omezujících hodnot.

• var je objekt Variable představující proměnnou křížovky.
• Heuristiku určuje počet hodnot vyloučených u sousedních nepřiřazených proměnných. Pokud určité přiřazení var vyloučí u sousedů n možností, řaď výsledky podle n vzestupně.
• Proměnná obsažená v assignment už hodnotu má, a proto ji při počítání vyloučených hodnot sousedních nepřiřazených proměnných nezapočítávej.
• U hodnot domény, které vyloučí stejný počet možností, je přípustné libovolné pořadí.
• Průnik dvou proměnných, pokud existuje, získáš v self.crossword.overlaps.
• Zprvu může být užitečné vracet hodnoty v libovolném pořadí, což stále umožní správné křížovky. Po zprovoznění algoritmu se vrať a zajisti správné řazení.
• Pomoci může sort podle určitého key; Python k tomu nabízí vhodné funkce.

Funkce select_unassigned_variable má vrátit jednu proměnnou křížovky, která ještě není přiřazena v assignment, podle heuristiky nejméně zbývajících hodnot a poté heuristiky stupně.

• assignment je slovník s objekty Variable jako klíči a řetězci přiřazených slov jako hodnotami. Můžeš předpokládat, že není úplný: některé proměnné v něm chybějí.
• Vrať objekt Variable s nejmenším počtem zbývajících hodnot v doméně. Při shodě vyber z těchto proměnných tu s nejvyšším stupněm, tedy s nejvíce sousedy. Při shodě obou kritérií můžeš vybrat libovolnou z rovnocenných proměnných.
• Nejprve můžeš vracet libovolnou nepřiřazenou proměnnou, což stále umožní správné křížovky. Po zprovoznění algoritmu zajisti výběr podle heuristik.
• Pomoci může sort seznamu podle určitého key; Python k tomu nabízí vhodné funkce.

Funkce backtrack má přijmout částečné přiřazení assignment a prohledáváním se zpětným návratem vrátit úplné vyhovující přiřazení proměnných k hodnotám, pokud existuje.

• assignment je slovník s objekty Variable jako klíči a řetězci přiřazených slov jako hodnotami. Vstup nemusí být úplný: některé proměnné nemusejí mít hodnotu.
• Lze-li vytvořit vyhovující křížovku, vrať úplné přiřazení: slovník, kde klíčem je každá proměnná a hodnotou její slovo. Pokud vyhovující přiřazení neexistuje, vrať None.
• Prokládání hledání a odvozování může algoritmus zefektivnit, například udržováním hranové konzistence po každém přiřazení. Není to povinné, ale je to dovoleno, pokud funkce vrací správné výsledky. Proto ac3 přijímá argument arcs, který umožňuje začít jinou frontou hran.

V generate.py neupravuj nic kromě funkcí určených zadáním, ale můžeš přidat pomocné funkce a importy standardní knihovny Pythonu. Pokud je znáš, můžeš importovat i numpy či pandas, ale žádné jiné moduly třetích stran. V crossword.py nic neupravuj.

Tipy

• order_domain_values a select_unassigned_variable můžeš nejprve implementovat bez heuristik a přidat je později. Algoritmus bude fungovat, jen může před nalezením řešení prozkoumat více přiřazení, než je nutné.
• Program spustíš například příkazem python generate.py data/structure1.txt data/words1.txt, kde určíš soubor struktury a soubor slov. Existuje-li přiřazení, uvidíš jeho výpis. Můžeš přidat argument pro soubor obrázku: python generate.py data/structure1.txt data/words1.txt output.png vytvoří i obrázek výsledné křížovky.
• Třída Crossword má funkci neighbors pro přístup ke všem sousedům, tedy protínajícím se proměnným, konkrétní proměnné. Použij ji kdykoli potřebuješ určit sousedy.

Testování

Chceš-li vyhodnotit správnost kódu, můžeš po nastavení check50 spustit následující příkaz. Není to povinné: při odevzdání podle kroků na konci zadání proběhnou stejné testy na našem serveru. V každém případě kód také sama zkompiluj a otestuj!

check50 ai50/projects/2024/x/crossword

Následujícím příkazem vyhodnotíš styl kódu pomocí style50.

style50 generate.py

Jak odevzdat

1. Otevři tento odkaz, přihlas se účtem GitHub a klikni na Authorize cs50. Pak zaškrtni souhlas s přístupem učitelů k odevzdaným pracím a klikni na Join course.
2. Nainstaluj Git a případně nainstaluj submit50.
3. Pokud máš nainstalované submit50, spusť

   submit50 ai50/projects/2024/x/crossword
   

   Jinak pomocí Gitu odešli práci do https://github.com/me50/USERNAME.git, kde USERNAME je tvoje jméno na GitHubu, na větev ai50/projects/2024/x/crossword.

Práce by měla být ohodnocena do pěti minut. Svůj postup pak můžeš sledovat na https://cs50.me/cs50ai!