crossword

Můj zápočtový prográmek na /NeprocedurálníProgramování s Ondřejem Zajíčkem.
Zadání a o co jde

Program v Prologu, generuje třeba takovéhle křížovky:
**v*v*v*v*s*v*v*v*v*
*-C R O S S W O R D
*>Y O R E *>O L E O
*>S T A R *>S E E P
*>T A L E *>T O L E
(I když to tak nemusí vypadat, jedná se ve všech řádcích a sloupcích o skutečná anglická slova.)
Jediná vada je, že konstrukce složitější křížovky trvá věčnost.
Z dokumentace

====Konstrukce křížovek====

=====Popis problému=====

Vstup:
	1.	Databáze povolených slov.
	2.	Švédská křížovka bez popisků a s tajenkou zadaná maticí. Tzn. je určeno, kde popisky a případné výplně (viz poznámka níže) budou.

Výstup: Matice s vyplňenými prázdnými políčky křížovky, tak, aby každá skupina polí odpovídající nějaké nápovědě obsahovala nějaké platné slovo a aby každá skupina polí tajenky obsahovala zadanou tajenku.

Pozn.: Buňka švédské křížovky může být buď výplň, prázdné pole na vyplňení nebo pole s popiskem. Pole s popiskem může obsahovat nápovědu pro přilehlé buňky nebo označení tajenky. Každé prázdné pole musí odpovídat dvěma nápovědám, případně nápovědě a tajence nebo dvěma tajenkám.


=====Rozbor problému a nápady pro řešení=====

Řešení bude prohledávání stavového prostoru do hloubky, kde stavy jsou množiny dvojic (vyplněné slovo, místo v křížovce). V každém kroku se budeme snažit do nějaké skupiny polí odpovídající nápovědě (této skupině budeme říkat výplň, anglicky fill, výplň odpovídá určitému místu v křížovce) snažit dát platné slovo, které má na odpovídajících pozicích již vyplněná písmena. Pokud takové slovo neexistuje, dostali jsme se v prohledávání do slepé uličky.

Pozorování 1: Neustále budeme přistupovat k databázi slov, je třeba ji efektivně reprezentovat. Hezké by bylo získávat slova potřebných parametrů v konstantním čase.

Pozorování 2: Databáze slov nemusí obsahovat slova delší, než se budou vyskytovat v naší křížovce.

Pozorování 3: Když hledáme slovo do určité výplňě, známe vždy jeho délku. Je tedy vhodné mít slova roztříděná podle délky.

Pozorování 4: Když hledáme slovo do určité výplně, známe písmena na některých jeho pozicích. Protože třídit slova podle různách kombinací vyplněných písmen by vedlo k příliš velkému objemu dat, zvlášť při implementaci v Prologu, potřebujeme  nějaké jiné řešení.

Pozorování 5: Často by se mohlo stát, že zbytečně vyřešíme mnoho výplní jen, abychom se později vraceli zpět. Bylo by nešťastné například vyplňovat nejdříve všechny řádky a potom všechny sloupce. Jako dobrý nápad se jeví, vyplňovat křížovku vyplňovat v následujícím pořadí (říkejme mu diagonální, viz zdroják), přičemž vodorovná a svislá nápověda pro dané pole se vyplňuje současně.

(tabulka viz dokumentace)

Pozorování 6: Ukazuje se, že při postupu zvoleném v pozorování 5 většinou (podle uspořádání popisků) budeme mít při řešení výplně k dispozici její prefix tvořený dřívě zvolenými písmenky, ji protínajících výplní. Další kritérim roztřídění slov je tedy jejich prefix (to není nutně totéž jako mít slova podle abecedy, realizace viz později).

Pozorování 7: Přistupovat na náhodné prvky matice reprezentované vnořenými seznamy trvá dlouho. Hezké by bylo mít hashovací tabulku podle souřadnic. (Možná je to v Prologu blbost, něco jsem zkusil, viz níže a implementace.)


=====Vybrané řešení=====

Databáze slov: Zvláštním skriptem v Prologu si zkonstruujeme databázi slov, která bude také v Prologu a rozhraní k ní bude:

w(+Délka, +Prefix, -Slovo).

Experimentálně jsem zjistil, že nejvhodnější je mít vnitřně predikáty ve formátu w(+Délka, +Prefix, [Slovo1,Slovo2,?])., kde Prefix a SlovoN jsou atomy, a následně vybírat jedno slovo ze seznamu a převádět atomy na řetězce a naopak. Je trochu překvapivé, že není výhodné mít predikát pro každé slovo zvlášť ani předávat Délku a Prefix jako jeden parametr, dvojici. SWI prolog by měl predikáty hashovat podle prvního paramatru, pak by teoreticky měly být přístupy do databáze na základě parametru (Délka, Prefix) v konstantním čase, to se mi ale nepodařilo uvést do praxe, zjevně je to totiž pomalejší než s oddělenými parametry. Nevím, kolik času to zabere teď.

Databáze slov se konstruuje ze seznamů slov podle délky. Použil jsem středně rozsáhlý anglický slovník, který je přiložený.

Vlastní algoritmus: Algoritmus se skládá ze
	1.	zpracování matice křížovky na seznam výplní (fills) a jejich průsečíků (letters)
	2.	vyplnění výplní platnými slovy (v této fázi se vůbec nepracuje s maticí)
		-	Prohledává se do hloubky podle diagonálního (viz pozorování 5) seznamu výplní.
		-	Aktualizují se přitom především prefixy výplní a písmena na průsečících.
		-	Další obecné věci plynou z pozorování, konkrétní detaily viz komentáře v crossword.pl.
	3.	uspořádání výsledných písmen na průsečících zpět do matice a výpis

Implementace: Při implementaci by se mi bylo hodilo pole (to nejde) nebo aspoň hashovací tabulka. Nakonec používám AVL stromy ze SWI-prologovského balíku assoc nebo obyčejné seznamy párů klíč-hodnota. Více informaci v tables.pl, tam jde také implementaci přepínat mezi seznamy a stromy. Více poznámek k implementaci ve zdrojových kódech.

Řešení se bohužel ukazuje jako dost pomalé, viz příklady a níže. Zkoušel a promýšlel jsem všechno možné, nic lepšího jsem ale nebyl schopen dát dohromady:(. Některá drobná vylepšení jako hned zavrhnout slova, která v jiných výplních tvoří nepoužitelné prefixy, v praxi program ještě zpomalovala.


=====Sestavení, použití=====

Databáze slov (words.pl) se konstruuje makefilem (tzn. stačí v adresáři napsat make, případně make clean; make). Přikládám také již vygenerovanou databázi.

POZOR: Makefile je nastavený na generování slov nejvýše délky 5 znaků. To stačí pro řešení všech přiložených příkladů. Hodnotu lze v makefilu změnit.

Pro vlastní konstrukci křížovek se používá spustitelný soubor (skript) solveTool.pl, (zřejmě bude v závislosti na instalaci třeba upravit cestu k swipl). Na vstupu očekává matici křížovky ve formátu

[[buňka11, buňka12, ?, buňka1N], [buňka21, buňka22, ?, buňka2N], ..., [buňkaM1, buňkaM2, ?, buňkaMN]].

Přitom buňka je:
	-	prázdný seznam [] pro prázdnou buňku
	-	dvojice ?popisků? pro vodorovný a svislý směr: (X-N,Y-M)
	-	_-0 je výplň,
	-	Řetězec-N je tajenka Řetězec o délce N (malými písmeny!),
	-	c-N je nápověda pro vyplnění slova o délce N.

V adresáři examples jsou příklady v tomto formátu. Pro některé není možné křížovku s pomocí přiloženého seznamu sestavit, u ostatních jsou uvedeny výstupy jako komentáře. Zpravidla uvádím také spotřebovaný procesorový čas na Intel Core 2 Duo 1.83 GHz. Bohužel časy jsou vysoké, na opravdové velké křížovky je to naprosto nepoužitelné:(, ale nenapadá mě, jak to zlepšit.
Stažení

file:crossword.tar.gz — tarball.
Matfiz: AdamNohejl/crossword

crossword

Zadání a o co jde

Z dokumentace

Stažení
