Student World

(Dokončení ze včerejšího dne, 1. díl viz http://www.scienceworld.cz/sw.nsf/ID/6B2256EA7BC78D21C1257093005DE338)

Na naše otázky týkající se sudokománie odpovídá Luboš Bokštefl (* 1963), povoláním hudebník a učitel matematiky, který se zabývá luštěním a sbíráním hádanek už od svých dětských let. Stejně jako řada dalších i on propadl sudokománii. Sestavil dvě sbírky 100+1 Sudoku pro nakladatelství Dokořán
(http://www.dokoran.cz/index.php?p=book.php&id=209,
http://www.dokoran.cz/index.php?p=book.php&id=210).
Výběr sudoku, který připravil, se liší od řady podobných výběrů především tím, že každá hádanka prošla lidským testem, tj. byla skutečně vyřešena; nejde jen o prostý výpis z nějakého generátoru sudoku, jehož hádanky není v normálních lidských silách v rozumném čase vyřešit

Napadla mě jedna možná příčina rozšíření sudoku. Je to multietnická společnost či obecněji celková "fragmetace", kdy se ztrácí společně sdílený kulturní kontext. Těžko pak můžete oslovit celou společnost křížovkami, k jejichž luštění potřebujete znát – dejme tomu – Shakespearovo dílo. Čísla jsou ale přece jen univerzální.

Nevím, nejsem sociolog. O tomhle výkladu ale spíše pochybuji. Tak by se dala vysvětlit snad popularita hry v USA nebo Británii, ale hra je populární prakticky ve všech evropských zemích včetně střední Evropy a taktéž v Japonsku, které jsou z tohoto ohledu podstatně homogennější. Ale jak jsem říkal, v téhle otázce se necítím příliš pevný v kramflecích.

Teď přejdeme od vlastní hry k sestavování hádanek. Jak při tom postupujete vy sám a jakou roli v tom hrají počítače?

Začnu banalitou. Počítače samozřejmě pomáhají při kontrole sazby hádanek ve sborníku. Taktéž pomocí počítače ověřuji, zda úloha, kterou jsem sestavil, má pouze jedno řešení. Jiná věc ale je, že mi počítač neřekne, zda k řešení vede nějaká logická sekvence kroků, nejen hrubá síla.
Já sám postupuji následujícím způsobem. Vezmu si nějaké počítačem vygenerované cele vyplněné sudoku a postupně čísla odmazávám. Přitom stále kontroluji, zda úloha má jediné řešení, ale také, zda k němu lze logicky dospět. Tak dojdu až do chvíle, kdy už další čísla z mřížky vyřadit nelze (z jednoho ze dvou výše uvedených důvodů), a to je finální úloha – tedy alespoň pokud chci sestavit úlohu obtížnou.
A pak zde zůstává ještě několik drobností řekněme estetických. Předvyplněná mřížka by měla být nějak rámcově symetrická. Nebo mohou předvyplněná čísla vytvářet nějaký vzor/obrázek apod.

Jak rozdělujete úlohy do kategorií podle obtížnosti?

Vesměs subjektivně, podle toho, jak mně samotnému jde řešení. Při počítačově tvořeném zadání se obtížnost někdy stanovuje jako poměr vyplněných a nevyplněných čtverečků v zadání, ale to je strašně zjednodušující. Sudoku s chybějícími třemi řadami nahoře by třeba bylo předvyplněné ze dvou třetin, ale řešit by se nedalo (a kdo ví, jak by se řešilo sudoku s chybějícími dvěma řadami nahoře).
Obtížné jsou právě úlohy, kde existují zcela prázdné velké útvary – třeba dva čtverce 3 * 3 proti sobě na diagonále. Pokoušel jsem se sestavit sudoku, které by v zadání mělo zcela prázdné tři čtverce 3 * 3, ale to se mi nepodařilo. Takové zadání by buď mělo více řešení, nebo by se alespoň nedalo řešit logickým postupem. To bych měl vůbec zdůraznit – dobré sudoku se luští opravdu logicky, ne kombinatoricky (tedy ne tak, že čísla tipujete a pak, když se dostanete do slepé uličky, příslušný kus odgumujete). Projít všechny možnosti dokáže počítač, pro hráče je radostí jednoznačný postup řešení a s tím související uplatňování dedukce.

Poznámka:
Příklad úlohy sudoku z kategorie "evil" vygenerovaného podle http://www.websudoku.com/?level=4 (úplně volný je stejně jen jeden čtverec 3 * 3). Na první pohled lze doplnit pouze číslo 5 nad dvojkou vlevo dole. Pak pětku do úplně spodní řádky do prostředního sektoru. Pak devítku doprostřed čtverce vpravo dole.

Skutečně mají dobré úlohy sudoku jediný postup řešení, respektive jedinou sekvenci kroků, která je "logická"?
V zásadě ano, samozřejmě s několika výhradami. Na začátku, když můžete třeba doplnit několik číslic, tak můžete učinit v různém pořadí. Taktéž v závěru, kdy volná políčka ubývají, už lze dojít k cíli řadou cest. Dobrá úloha by ale měla podle mého názoru umožňovat jedinou cestu "v jádru", tedy prostřední – a nejobtížnější – fázi řešení. Samozřejmě je těžké získat jistotu, že zde opravdu neexistuje nějaká vedlejší větev…

Pokud by si čtenáři chtěli nějaké sudoku sami sestavovat, jaké jim k tomu doporučujete programy, nebo alespoň generátory úplně vyplněných polí? Kde najdeme sudoku na internetu?

http://www.sudoku.com/
http://www.websudoku.com/

Výpočet veškerých možností Sudoku s jediným řešením:
http://www.shef.ac.uk/~pm1afj/sudoku/sudoku.pdf

Úvod do luštění a pravidel Sudoku
http://www.sudoku.cz

Sudoku ve Wikipedii
http://en.wikipedia.org/wiki/Sudoku

autor Pavel Houser