\gdef\mujnazevCS{Sudoku s~překryvy: Ahoj, světe!}
\gdef\mujnazevEN{Multi-sudoku: Hello, World!}
\gdef\mujnazevPR{\mujnazevCS}
\gdef\mujnazevDR{\mujnazevEN}
\gdef\mujauthor{Pavel Stříž}

\bonushyper

\nazev{\mujnazevCS}

\nazev{\mujnazevEN}

\author{\mujauthor}

\Email{pavel@striz.cz}%
\label{sugen}%

\Abstrakt{Autor stručně představuje proces generování sudoku s~překryvy. V~pozadí používá program Sugen, který byl pro tyto účely upraven na úrovni jazyka C. Na základním příkladu je proces představen krok za krokem. V~závěru autor zmiňuje omezení tohoto algoritmu. V~principu můžeme říci, že jakékoliv sudoku s~překryvy, které obsahuje cyklus, tímto způsobem nelze generovat, je potřeba jiný přístup, a~to přes rekurzivní funkci.}
\smallskip
\KlicovaSlova{C, Sugen, sudoku}

\Abstract{The article briefly introduces a~process of generating a~multi-sudoku.  Behind the scene, the author uses Sugen program which was modified at a~C level for this specific task.  A~``Hello, World!'' multi-sudoku is presented step-by-step.  In the conclusion, the author mentiones its limits, esp. which multi-sudoku cannot be generated by this algorithm.  It can be stated that any multi-sudoku with cycle would be a~problem, this type of multi-sudoku needs a~different approach, a~recursion function.}
\smallskip
\KeyWords{C, Sugen, sudoku}


\section{Nápad}

Řeším kombinatorické úlohy, především ranking-unranking problem, tedy zjistit počet možností, vybrat si jednu z~nich, zrekonstruovat kombinatorickou situaci, a~naopak, z~jisté kombinatorické situace spočítat její pořadové číslo. To mě přivedlo i~ke klasickému sudoku, kde jsem řešení nezahlédl, ale první experimenty ukazují, že to bude náročné, ale možné. O~tom snad jindy.

Při rešerši kolem sudoku jsem narazil na verze s~překryvy (anglicky overlapping sudoku, multi-sudoku). Pravděpodobně nejznámější je Samurai sudoku.
Ale existuje jich celá plejáda.%, zde jsou vybrané.

%obrázky


\section{Program sugen}

Chtěl jsem si něco takového zkusit naprogramovat. Při rešerši jsem narazil na program Sugen (zkráceno ze sudoku generator) od Daniela Beera, \url{https://dlbeer.co.nz/articles/sudoku.html}.

Ten umí vygenerovat mustr, zadání sudoku ze zadaného mustru i~získat obtížnější variantu řešeného sudoku. Neumí však generovat více sudoku s~překryvy. Poněvadž se učím C, tak jsem začal zdrojový kód zkoumat. Zkusit si vygenerovat sudoku s~překryvy od nuly mě tehdy ani nenapadlo.


\section{Hello, World!}

Našim úkolem je připravit obdobu tohoto sudoku s~překryvy. Překrývá se celý blok, to lze považovat za standard.

%obrázek zadání
%obrázek řešení

\noindent
\includegraphics[width=0.48\textwidth]{prvni-slozeni-zadani}\hfill
\includegraphics[width=0.48\textwidth]{prvni-slozeni-reseni}


\section{Tři injekce od pana doktora (či sestřičky)}

Jakmile jsem princip programu pochopil, použil jsem načtení externích souborů před zavoláním klíčové funkce. Připadal jsem si jako správný hacker.

1. injekce. Číslo sudoku slouží jako počáteční hodnota PRNG, funkce \texttt{srandom}. Pro případ pozdního nového generování jen jednoho sudoku. Nebylo třeba. Pomocný soubor obsahuje jednu hodnotu.

2. injekce. Pro vytvoření řešení, funkce \texttt{choose\_grid} jsem zasahoval do pole \texttt{grid}. Pomocný soubor má dva sloupce, číslo pole (0--80) a~hodnota (1--9). Vzniká soubor s~řešením.

3. injekce. Pro vytvoření zadání, funkce \texttt{harden\_puzzle} jsem zasahoval do pole \texttt{puzzle}. Pomocný soubor má dva sloupce, číslo pole (0--80) a~jeho hodnotu (0 -- musí zůstat prázdné, či 1--9). Plus se načte soubor s~řešením. Výstupem je soubor se zadáním.

Poznámka. Dá se tak řešit i~chtěná obtížnost, nebo program umožňuje si zavolat parametr \texttt{-t} z~příkazového řádku. Toho jsem využil.


\section{Dílčí kroky}

Překryv je pro první sudoku 9. blok (pravý dolní roh), pro druhé sudoku blok 1. (levý horní roh). To když má člověk pořád na mysli, sledovat proces generování není pak tak náročné, hlavně u~složitějších struktur.

Schématicky bychom generování mohli znázornit takto.

Upravený sugen: 1. sudoku, řešení:
\nopagebreak\par
\noindent\hfil
\begin{minipage}{0.6\textwidth}
\begin{verbatim}
_________                     475196823
_________                     896243517
_________                     312857469
_________                     637415298
_________ --> bez injekce --> 258739146
_________                     149682735
_________                     561974382
_________                     724368951
_________                     983521674
\end{verbatim}
\end{minipage}\medskip

Upravený sugen: 1. sudoku, zadání:
\nopagebreak\par
\noindent\hfil
\begin{minipage}{0.6\textwidth}
\begin{verbatim}
475196823                     4_5____2_
896243517                     8________
312857469                     ___8_74__
637415298                     __74__2_8
258739146 --> bez injekce --> 2__7_9__6
149682735                     1_9__27__
561974382                     __19_4___
724368951                     ________1
983521674                     _8____6_4
\end{verbatim}
\end{minipage}\medskip

Upravený sugen: 2. sudoku, řešení:
\nopagebreak\par
\noindent\hfil
\begin{minipage}{0.6\textwidth}
\begin{verbatim}
_________      382______      382574169
_________      951______      951368274
_________      674______      674912835
_________      _________      165423798
_________ ---> _________ ---> 438697521
_________      _________      729185643
_________      _________      896231457
_________      _________      513746982
_________      _________      247859316
\end{verbatim}
\end{minipage}\medskip

Upravený sugen: 2. sudoku, zadání:
\nopagebreak\par\smallskip
\noindent\hfil
\begin{minipage}{0.6\textwidth}
\begin{verbatim}
382574169      000______      ________9
951368274      001______      __1__827_
674912835      604______      6_4___83_
165423798      _________      _6__23___
438697521 ---> _________ ---> 4___9___1
729185643      _________      ___18__4_
896231457      _________      _96___45_
513746982      _________      _137__9__
247859316      _________      2_______6
\end{verbatim}
\end{minipage}\medskip

Z~příkazového řádku jsem si postupně dvakrát volal:

\begin{verbatim}
$ ./sugen gen-grid >reseni.txt
$ ./sugen harden -t 100 <reseni.txt >zadani.txt
\end{verbatim}

Pro první sudoku byly dva pomocné soubory prázdné, pro druhé sudoku s~naznačenými hodnotami u~injekcí. 

Poslední úkol je už čistě typografický, výstupní soubory si vhodně vysázet. 


\section{Kdy to nelze použít}

Je zde omezení. Jakmile bychom měli komplikovanější strukturu překryvů (sudoku vztahy jakoby ob jedno sudoku), dříve či později se dostaneme do konfliktu, kdy musíme sudoku generovat znovu, či samozřejmě lépe, využít rekurze. O~tom více na přednášce. 

Pokud však najdeme pořadí sudoku, abychom jedno negenerovali ze vztahů více nezávislých sudoku, tato metoda nám dostačuje. Termínem z~teorie grafů, do každého sudoku může jít maximálně jedna šipka, ze sudoku ven libovolný počet. Šipky určují pořadí generování.

Pro ilustraci dva náčrtky. Na levém obrázku můžeme generovat sudoku např. v~těchto pořadích: 1--2--3--4--5, 5--4--3--2--1 nebo třeba 3--2--1--4--5. Do problémů se dostáváme např. při 1--2--3--5--4 či 5--1--2--3--4, ale také při pokusu generovat sudoku jakoby po řádcích, tedy 1--3--5--2--4.

Na středním obrázku můžeme využít: 1--2--3--4--5 či 2--1--3--4--5, ale dostaneme se do problémů při 1--3--2--4--5 či 1--3--4--5--2.

\noindent
\includegraphics[height=0.18\textwidth]{rozkres1}\hfill
\includegraphics[height=0.18\textwidth]{rozkres2}\hfill
\includegraphics[height=0.18\textwidth]{rozkres3}%

Tato pomůcka sledu generování sudoku nám nepomůže u~multi-sudoku, které tvoří uzavřený cyklus, kdy každé sudoku má víc nezávislých překryvů, viz pravý obrázek.

Na takovou situaci se už musí jít přes rekurzivní funkci. Či mnou nedoporučený způsob vyřazování nevhodného sudoku a~opakování. V~takovém případě se ale může stát, že řešení ani nalézt nelze a~musí se jít v~procesu generování o~celé sudoku nazpět. Chce to jiný přístup, o~tom víc na konferenci.% osobně.

Tento typ jsem neprogramoval, neb jsem to zatím nepotřeboval, ale kdyby na to došlo, zde je tzv. Venn sudoku (\textit{Taking Sudoku Seriously}, str.\,122), které je ideálním typem na testy. Plus další dva rozsáhlejší cyklické typy přebrané z~internetu z~různých zdrojů (Sudoku Gattai a~Sudoku Sumo).

\noindent
\fboxrule=0pt \fboxsep=0pt
\fbox{\includegraphics[page=135, trim=1.3cm 8.2cm 1.3cm 4.0cm, clip, height=38mm]{tss.pdf}}%
\hfill \fbox{\includegraphics[height=38mm]{sudoku-gattai.png}}%
\hfill \fbox{\includegraphics[height=38mm]{sudoku-sumo.png}}%

\section{Vzorek z vlastní zahrádky}
\enlargethispage{\baselineskip}%

Na této straně je řešení, na další straně zadání 3D sudoku (povrch krychle, tedy 6~sudoku), rozkresleného na ploše se vztahy. Vztahy jsou komplikovanější (hrany sdílí dvě sudoku, rohy dokonce tři), ale princip vzniku je podobný.

\noindent\hfil\label{3dreseni}%
\includegraphics[page=4, width=0.67\textwidth]{3d-s-carami-crop.pdf}%

\newpage\label{3dzadani}%
\vspace*{3mm}%
\noindent\kern-4mm%
\includegraphics[page=1, angle=90, height=.9\textheight]{3d-s-carami-crop.pdf}%

