Program na tvorbu křížovek Křižák

Křižák je počítačový program k tvorbě křížovek vycházející z algoritmů umělé inteligence, pomocí něhož všichni naši autoři tvoří křížovky do našich časopisů. Program používá sofistikované algoritmy na bázi slepého prohledávání stavového prostoru v modifikaci backtracking a využívá heuristiky. Stavový prostor tvoří množina všech křížovek, do kterých je kamkoliv vepsán libovolný počet správně se křižujících existujících výrazů. K řazení polí výrazů vhodných k vepsání je použit řadicí algoritmus quicksort v rekurzivní modifikaci, avšak s omezenou hloubkou zanoření. Některá současná literatura uvádí, že u rekurzivního quicksortu může dojít k přetečení zásobníku, neboť maximální hlouba zanoření je rovna délce pole. Je-li však rekurzivní quicksort dobře napsán, lze maximální hloubku zanoření výrazně redukovat a toto nebezpečí zcela vyloučit. Maximální možná hloubka zanoření je potom dána vztahem:

h = log₂ n,

kde n představuje délku pole, takže v žádném případě nemůže dojít k přetečení zásobníku. Konkrétní podobu tohoto klíčového algoritmu si však ponecháme jako jedno z firemních tajemství.

Program Křižák má ke konci roku 2008 v databázi více jak 305.000 křížovkářských výrazů a více jak 95.000 legend. Legendy jsou neustále průběžně doplňovány, nicméně každá nově vytvořená křížovka již obsahuje zpravidla více jak 95 % výrazů, ke kterým již je legenda obsažena v databázi. Autor tak nemusí legendu zadávat, což výrazně urychluje vytváření křížovek. Další velkou výhodou tohoto programu je, že generuje exportní soubory obrazců a legend křížovek přímo v příkazech sázecího systému TeX, takže sazbu a předtiskovou přípravu jsme schopni udělat velice rychle. Díky tomu dosahujeme oproti konkurenčním vydavatelstvím několikanásobně vyšší produktivity, stránka se švédskou křížovkou může být od zadání křížovky autorovi až po hotovou sazbu vytvořena během půl hodiny.