% -*- mode: LaTeX; -*-
%
\def\timestamp{%
Time-stamp: <nwd-handout.tex: Monday 30-01-2006 at 13:05:37 (cet)>}
\def\stripname Time-stamp: <#1 #2>{#2}
\edef\filedate{\expandafter\stripname\timestamp}
%
\documentclass[a4paper]{amsart}
\usepackage[dutch]{babel}

\input{sudokumacs}
\vet=1.5pt
\med=0.9pt
\dun=0.3pt


\DeclareMathSymbol{\varnothing}{\mathord}{AMSb}{"3F}
\renewcommand{\y}{\ensuremath\varnothing}

\iffalse
\makeatletter
\let\@@oddhead\@oddhead
\let\@@evenhead\@evenhead
%\show\@oddhead  \show\@evenhead
\def\@oddhead{\let\noexpand\relax\@@oddhead}
\def\languagename{dutch}
\makeatother
\fi

\begin{document}
\title{Sudoku's en Wiskunde}
\author{Klaas Pieter Hart}
\address{Faculteit EWI\\
         TU Delft\\
         Postbus 5031\\
         2600~GA {} Delft}
\email{K.P.Hart@TUDelft.NL}
\urladdr{http://fa.its.tudelft.nl/\~{}hart}
\date{\filedate}

\maketitle

\section*{Inleiding}

Hoewel ze reeds geruime tijd bestaan 
--- 
sinds 1979 in de V.S. onder de naam \textsl{Number Place},
sinds 1986 in Japan onder the namen \textsl{Nanpure} en \textsl{Sudoku}
--- 
zijn de Sudoku-puzzels pas het afgelopen jaar in onze buurt een ware rage gaan 
vormen, eerst in Groot-Brittani"e en nu ook in Nederland.
Voor degenen die nog in zalige onwetendheid verkeren: hier is een 
Sudoku-puzzel (nummer 80 uit~\cite{Guardianboek}):
$$
\begin{sudoku}[\sffamily]
 &5& & &6& & & & \cr\noalign{\hrd}
 & &1& & & & &9& \cr\noalign{\hrd}
 & & & & &7& & &4\cr\noalign{\hrv}
2&4& &9& & & & & \cr\noalign{\hrd}
 & &8& & & &6& & \cr\noalign{\hrd}
 & & & & &5& &3&7\cr\noalign{\hrv}
7& & &8& & & & & \cr\noalign{\hrd}
 &9& & & & &2& & \cr\noalign{\hrd}
 & & & &3& & &1& \cr
\end{sudoku}
$$
De bedoeling is in elk vak een cijfer van \textsf{1} tot en met \textsf{9}
te plaatsen z\'o dat in elke rij, elke kolom en in elk $3\times3$-blok
(vetomlijnd) elk cijfer \'e\'enmaal voorkomt.
Een goedgestelde Sudoku heeft precies \'e\'en oplossing en dat is iets
dat we in onze beschouwingen altijd mee zullen nemen.

De reactie op de Sudoku's verschilt van persoon tot persoon maar onder
wiskundigen merk ik vooral de neiging tot 
uitzoeken-hoe-het-allemaal-in-elkaar-zit.
%\footnote{OK, niet universeel, er verkeren nog wiskundigen zalige onwetendheid
%          over dit verschijnsel}
Voor degenen die daar nog niet de tijd voor hebben gehad of genomen
zal ik in deze bijdrage een paar wiskundige aspecten van de puzzels
belichten.
De keuze voor onderstaande onderwerpen is tot stand gekomen door rond te vragen
en door eigen voorkeur.
\begin{enumerate}
\item Sudoku's tellen.
\item Moeilijkheisgraad vaststellen.
\item Hoeveel cijfers moet men minimaal geven?
\item Sudoku is moeilijk.
\end{enumerate}
Voor de goede orde: ik beperk mij in dit artikel tot de gewone, $9\times9$,
Sudoku's, voornamelijk om de omvang van het verhaal binnen bepaalde perken
te houden en ook omdat de variaties \emph{wiskundig} niet veel nieuws
opleveren.
Om bepaalde idee"en te illustreren gebruik ik Baby-Sudoku's, met een 
$4\times4$-speelveld.


\section{Sudoku's tellen}

Een veel gestelde vraag, ook op \texttt{www.wisfaq.nl} opgeworpen, is
``Hoeveel puzzels zijn er eigenlijk?''.
Die vraag is nog niet beantwoord; hij is ook nog niet helemaal goed
gesteld omdat bepaalde aspecten van Sudoku's nog niet zijn opgehelderd.
Een indicatie dat die telling een niet-triviale onderneming zal zijn
krijgen we als we bekijken hoe de verzameling van alle ingevulde 
Sudoku-vierkanten geteld is en zien hoe groot die verzameling wel niet is.

\subsection{Baby-Sudoku's tellen}

Om te laten zien hoe zo'n telling in zijn werk gaat tellen we 
Baby-Sudoku-vierkanten.
$$
\begin{babysudoku}[\sffamily]
 & & & \cr\noalign{\hrd}  
 & & & \cr\noalign{\hrv}  
 & & & \cr\noalign{\hrd}  
 & & & \cr  
\end{babysudoku}
$$
De bedoeling is dit diagram, net als in het $9\times9$-geval, te vullen
met de cijfers \textsf{1}, \textsf{2}, \textsf{3} en \textsf{4} en wel zo
dat elk cijfer in elke rij, kolom of blok precies \'e\'en keer voorkomt.

Om al deze invullingen te tellen heeft het zin eerst even na te denken
of het niet handiger kan dan door alle vierkanten uit te schrijven en te 
tellen.
Het grote probleem bij die aanpak is het risco van toch wel erg veel hooi op
de vork en het gevaar van het missen van een paar vierkanten.
Het is zaak het werk verstandig in te delen en zo de telling tot 
overzichtelijke werkjes te reduceren.
De eerste stap geeft een forse reductie: tel alleen de vierkanten die als volgt
beginnen:
$$
\begin{babysudoku}[\sffamily]
1&2& & \cr\noalign{\hrd}  
3&4& & \cr\noalign{\hrv}  
 & & & \cr\noalign{\hrd}  
 & & & \cr  
\end{babysudoku}
$$
Als we deze geteld hebben kunnen we het resultaat met $4!$ vermenigvuldigen
om het eindresultaat te krijgen: elke permutatie van $\{1,2,3,4\}$ levert
een andere linkerbovenhoek met evenveel aanvullingen als het speciale 
voorbeeld.
We gaan nog even door met verdelen; de eerste rij kan op twee manieren
worden aangevuld:
$$
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4& & \cr\noalign{\hrv}  
 & & & \cr\noalign{\hrd}  
 & & & \cr  
\end{babysudoku}}
\hbox{\qquad en\qquad}
\vcenter{\begin{babysudoku}[\sffamily]
1&2&4&3\cr\noalign{\hrd}  
3&4& & \cr\noalign{\hrv}  
 & & & \cr\noalign{\hrd}  
 & & & \cr  
\end{babysudoku}}
$$
Beide hebben evenveel completeringen: verwissel de laatste kolommen.
We werken verder met het linker vierkant, dat representeert dus
$48$ groepen die allemaal even groot zijn.
Door de tweede rij ook aan te vullen ontstaan weer twee mogelijkheden:
$$
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4&1&2\cr\noalign{\hrv}  
 & & & \cr\noalign{\hrd}  
 & & & \cr  
\end{babysudoku}}
\hbox{\qquad en\qquad}
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4&2&1\cr\noalign{\hrv}  
 & & & \cr\noalign{\hrd}  
 & & & \cr  
\end{babysudoku}}
$$
Nu is er geen overduidelijke reden waarom deze evenveel completeringen zouden 
hebben
(het zou kunnen maar we weten het niet \dots),
daarom bekijken we ze apart.
We kunnen de eerste kolom nog aanvullen, `verwisseling van de laatste rijen'
laat zien dat we, in beide gevallen het werk kunnen halveren. 
De posities van \textsf{2} en \textsf{4} liggen dan ook vast.
$$
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4&1&2\cr\noalign{\hrv}  
2& &4& \cr\noalign{\hrd}  
4& &2& \cr  
\end{babysudoku}}
\hbox{\qquad en\qquad}
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4&2&1\cr\noalign{\hrv}  
2& &4& \cr\noalign{\hrd}  
4& & &2\cr  
\end{babysudoku}}
$$
Links hebben we nog twee mogelijkheden maar rechts nog maar \'e\'en:
$$
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4&1&2\cr\noalign{\hrv}  
2&1&4&3\cr\noalign{\hrd}  
4&3&2&1\cr  
\end{babysudoku}}
\hbox{\quad en\quad}
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4&1&2\cr\noalign{\hrv}  
2&3&4&1\cr\noalign{\hrd}  
4&1&2&3\cr  
\end{babysudoku}}
\hbox{\qquad en\qquad}
\vcenter{\begin{babysudoku}[\sffamily]
1&2&3&4\cr\noalign{\hrd}  
3&4&2&1\cr\noalign{\hrv}  
2&1&4&3\cr\noalign{\hrd}  
4&3&1&2\cr  
\end{babysudoku}}
$$
Nu terugrekenen: links krijgen we $4$ completeringen en rechts $2$.
Dus elk van de $48$ groepen heeft $6$ elementen; dus in totaal
zijn er $48\times6=288$ Baby-Sudoku-vierkanten.

Belangrijke punten uit deze telling: we verdeelden de vierkanten in groepen,
eerst $4!=24$ en elk van die nog in twee, en allemaal even groot.
E\'en zo'n groep verdeelden we in twee groepen die niet meer even groot waren
maar wel redelijk snel te tellen.

\subsection{Sudoku-vierkanten tellen}

Dezelfde strategie is gebruikt om de Sudoku-vierkanten te tellen.
Begin met
$$
\begin{sudoku}[\sffamily]
1&2&3& & & & & & \cr\noalign{\hrd}  
4&5&6& & & & & & \cr\noalign{\hrd}  
7&8&9& & & & & & \cr\noalign{\hrv}  
 & & & & & & & & \cr\noalign{\hrd}  
 & & & & & & & & \cr\noalign{\hrd}  
 & & & & & & & & \cr\noalign{\hrv}  
 & & & & & & & & \cr\noalign{\hrd}  
 & & & & & & & & \cr\noalign{\hrd}  
 & & & & & & & & \cr  
\end{sudoku}
$$
dat reduceert het werk met een factor $9!$.
De eerste telling werkte met aanvullingen van de eerste drie rijen en verdeelde
die in, uiteindelijk, $71$ equivalentieklassen van aanvullingen met per klasse
telkens evenveel completeringen. 
De verdeling kwam tot stand door allerlei symmetrie"en uit te buiten:
kolompermutaties binnen de blokken, permutaties van de blokken zelf, 
hernummeringen enzovoort.
Die $71$ tellingen werden, met bruut geweld, door de computer gedaan.
De tellingen gaven $44$ verschillende uitkomsten; enig speurwerk levered
nog wat equivalenties op waardoor men inderdaad het aantal klassen tot
die $44$ kon reduceren.

Zie de slides voor een aantal voorbeelden van het soort reducties dat 
toegepast werd.

\subsubsection*{Het resultaat}
Er zijn $6\,670\,903\,752\,021\,072\,936\,960$ Sudoku-vierkanten.

Een rechtgeaarde wiskundige vraagt zich natuurlijk af: zijn die `echt' allemaal
verschillend?
Natuurlijk niet: permutatie van de cijfers geeft niet wezenlijk andere 
Sudoku's, net als permutatie van rijen\slash kolommen binnen de `dikke'
rijen\slash kolommen of permutatie van de dikke rijen\slash kolommen zelf.
Verder kunnen we nog roteren en spiegelen in de diagonalen.
De hierbij behorende Sudoku-symmetriegroep is ook bepaald en het resultaat
is dat er `maar' $5\,472\,730\,538$ echt verschillende Suduko-vierkanten zijn.
Alle informatie over deze tellingen is te vinden via 
\cite{FelgenhauerJarvis}.

In \cite{Dekking} wordt beschreven hoe die symmetriegroep kan helpen
om wel heel snel een boekje met Sudoku-puzzels in elkaar te zetten.

\section{Moeilijkheidsgraad}

Een andere vraag die vaak terugkwam: ``Hoe bepalen ze de moeilijkheidsgraad?''
Hier is geen eenduidig \emph{wiskundig} antwoord op te geven want moeilijkheid
is een subjectief begrip.
De gang van zaken is in het algemeen als volgt: men laat de puzzel door een
programma oplossen en daarbij bijhouden wat voor oplosstappen worden gebruikt.
De aard van de gebruikte stappen bepaalt de moeilijkheidsgraad.

\subsection{De NWD-classificatie van Sudoku's}

Bij het voorbereiden van mijn lezing heb ik een programmaatje geschreven dat
een paar stappen die ikzelf veel gebruik implementeert.
Die stappen zijn
\begin{description}
\item[wegstrepen] systematisch de rijen, kolommen en blokken aflopen
      en door gegeven cijfers uit andere cellen af te strepen zien
      wat overblijft
\item[uniciteit controleren] zoek per cijfer uit of er in een rij, kolom
      of blok nog maar \'e\'en mogelijke positie vrij is
\item[rij/kolom in blok] als een cijfer binnen een blok in nog maar \'e\'en 
      rij kan zitten kun je het in de rest van die rij wegstrepen (evenzo
      voor kolommen)  
\end{description}
Uitgaande van deze stappen komen we tot de volgende classificatie van Sudoku's,
de \textit{NWD-classificatie van Sudoku's}:
\begin{description}
\item[makkelijk] kan met wegstrepen  
\item[beetje moeilijk] kan niet all\'e\'en met wegstrepen maar heeft
     uniciteitscontroles nodig
\item[moeilijk] heeft al onze stappen nodig
\item[heel moeilijk] lukt niet met mijn programmaatje  
\end{description} 
Op de slides zijn voorbeelden van alle vier moeilijkheidsgraden
te vinden.

Zie \cite{Brouwer,Coster} voor nog meer voorbeelden van oplosstappen.


\section{Hoeveel zaadjes?}

Een nog onopgelost probleem is: ``hoeveel cijfers moeten minimaal gegeven
worden om de puzzel uniek oplosbaar te doen zijn?''

Je moet zeker $8$ \emph{verschillende} cijfers geven anders kun je uit een
oplossing een andere maken door de niet gegeven cijfers om te wisselen.

Verder is er een grote collectie van puzzels met $17$ gegeven cijfers
gevonden maar (nog) geen enkele met $16$, zie~\cite{Royle}.

Ik heb nog geen \emph{bewijs} gezien dat er geen puzzel met $8$ gegeven cijfers
is \dots

\subsection{Zaadjes voor Baby-Sudoku}
Voor Baby-Sudoku is met de hand eenvoudig vast te stellen dat
$4$ cijfers genoeg is:
$$
\begin{babysudoku}[\sffamily]
1& & & \cr\noalign{\hrd}
 & & &3\cr\noalign{\hrv}
 & &2& \cr\noalign{\hrd}
 &4& & \cr
\end{babysudoku}
$$
Het is ook eenvoudig met de hand vast te stellen dat drie \emph{niet} 
genoeg is.
Met moet in ieder geval drie \emph{verschillende} cijfers gebruiken;
we proberen dus met \textsf{1}, \textsf{2} en~\textsf{3} een puzzel te maken.
Na diverse symmetrie-argumenten kom je uit op de de volgende
mogelijkheden
$$
\begin{babysudoku}[\sffamily]
1& & & \cr\noalign{\hrd}
 & & & \cr\noalign{\hrv}
3&3&2& \cr\noalign{\hrd}
3&3&3&3\cr
\end{babysudoku}
$$
met vaste posities voor \textsf{1} en \textsf{2} en zes mogelijkheden 
voor~\textsf{3}.
Even spelen met de zes afzonderlijke diagrammetjes leert dat geen van deze
een unieke oplossing heeft.


\subsection{Kan het met acht?}

Net als bij het tellen wordt het werk bij de stap van Baby- naar echte Sudoku
schier oneindig veel groter.
Met symmetrie-overwegingen komen we tot
$$
\begin{sudoku}[\sffamily]
1& & & & & &\y&\y&\y\cr\noalign{\hrd}
 & & & & & &\y&\y&\y\cr\noalign{\hrd}
 & & & & & &\y&\y&\y\cr\noalign{\hrv}
 & & &2& & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrv}
 & & & & & &3& & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr
\end{sudoku}
$$
waarbij `$\varnothing$' inderdaad `leeg' betekent: met acht cijfers zal 
tenminste \'e\'en $3\times3$-blok leeg blijven.
De overige cijfers \textsf{4}, \textsf{5}, \textsf{6}, \textsf{7} en~\textsf{8}
moeten z\'o gezaaid worden dat in elke dikke rij\slash kolom zeker twee
rijen\slash kolommen iets krijgen; anders kun je door verwisseling van die
twee rijen\slash kolommen een andere oplossing cre"eren.
Omdat de cijfers verschillend zijn zijn alleen de posities van belang:
er zijn $\binom{69}{5}=11\,238\,513$ willekeurige zaaiingen, daarvan valt een
redelijk aantal af maar er blijven genoeg mogelijkheden over \dots;
het lijkt onbegonnen werk die met de hand na te lopen.

\subsubsection*{Kansrekening}

Het totaal aantal puzzels met acht verschillende zaadjes is snel geteld:
kies acht posities, kies acht cijfers en verdeel die.
Het resultaat is 
$\binom{81}{8}\times\binom98\times8!=11\,671\,764\,328\,224\,000$ 
puzzels.
De verhouding tussen het aantal zaaiingen, $1{,}167\times10^{16}$, 
en het aantal Sudoku-vierkanten, $6{,}67\times10^{21}$, 
is ongeveer $1:571\,542$.
Die verhouding wordt alleen maar kleiner als we alleen `goede' zaaiingen
bekijken.
Het lijkt dus nogal onwaarschijnlijk dat er een puzzel met acht zaadjes is
maar helemaal sluitend is dit argument natuurlijk niet.

\subsection{Hoe zit het met negen (of meer)?}

De situatie bij acht zaadjes, zoals boven geschetst, is nog redelijk
overzichtelijk maar bij negen of meer wordt de zaak aanzienlijk 
gecompliceerder.
Omdat er cijfers meer dan \'e\'en keer voor kunnen komen moet men echt op
de plaatsing gaan letten en zo wordt de zoekruimte aanzienlijk groter.


\section{Sudoku is moeilijk}

Wie een Sudoku-oplosser schrijft zal merken dat er altijd wel een puzzel
is die het programma nog niet aankan en wie de fora op, bijvoorbeeld,
\texttt{www.sudoku.com} bezoekt ziet dat er nog steeds over nieuwe
oplosstappen wordt nagedacht.
Dat is niet geheel verwonderlijk want Sudoku's behoren tot een klasse van
problemen die, met de huidige stand van de kennis, als `moeilijk'
worden betiteld.

Het verschil tussen `makkelijke' en `moeilijke' problemen zal ik hieronder
aan de hand van twee voorbeelden duidelijk proberen te maken.


\subsection{Makkelijke problemen}

Het uitrekenen van een $n\times n$ determinant is `makkelijk'.
Dat wil zeggen, na enig denkwerk.
Wie de offici"ele recursieve definite door middel van 
`ontwikkelen naar de eerste rij'
implementeert overleeft het uitrekenen van een $25\times25$-determinant niet.
De ontwikkelformule komt namelijk naar op het uitvoeren van 
veel meer dan $n!$ vermenigvuldigingen en bij $n=25$ wordt dat 
$25!\approx1{,}55\times10^{25}$ (een computer die $10^{12}$ 
vermenigvuldigingen per seconde kan uitvoeren doet er dus zeker
$490\,513$ jaar over).

Door de matrix eerst op driehoeksvorm te brengen en dan de 
diagonaalelementen te vermenigvuldigen reduceert men het werk tot
$n+(n-1)+\cdots+1+(n-1)=\frac12n^2+\frac32n-1$ vermenigvuldigingen.
Bij $n=25$ wordt dat $349$, een redelijk tijdsbesparing.

Het uitrekenen van determinanten is iets dat in \emph{polynomiale} tijd
gedaan kan worden; dat wil zeggen: er is een polynoom $p$ met de eigenschap
dat de rekentijd bij een invoer ter grootte~$n$ niet langer duurt dan $p(n)$
tijdseenheden.
Voor het determinant-uitrekenen hebben we dus $p(n)=\frac12n^2+\frac32n-1$ 
gevonden.

De letter $\mathrm{P}$ staat voor de klasse van dergelijke problemen; bepalen
of een getal~$n$ priem is is ook in $\mathrm{P}$ \emph{als functie van het
aantal cijfers van~$n$}, zie~\cite{Wiki-P-and-NP}.
Dit zijn de `makkelijke' problemen; de rest is `moeilijk'.

\subsection{Moeilijke problemen}

Een bekend combinatorisch probleem is het volgende:
{\slshape 
Gegeven een eindige verzameling en een overdekking van die verzameling,
dun die overdekking uit tot een \emph{disjuncte} overdekking}.
Zo'n probleem is met behulp van een matrix met nullen en enen te coderen.
De punten van de verzameling komen overeen met de kolommen
en de rijen geven de verzamelingen uit de overdekking weer.
Een $1$ op de positie $(i,j)$ in de matrix geeft aan dat punt~$j$
tot de $i$-de verzameling behoort.

Hier is een voorbeeld, waarin de vetgedrukte rijen een disjuncte overdekking
vormen.
$$
\begin{matrix}
1&0&0&1&0&0&1\\
\mathbf1&\mathbf0&\mathbf0&\mathbf1&\mathbf0&\mathbf0&\mathbf0\\
0&0&0&1&1&0&1\\
\mathbf0&\mathbf0&\mathbf1&\mathbf0&\mathbf1&\mathbf1&\mathbf0\\
0&1&1&0&0&1&1\\
\mathbf0&\mathbf1&\mathbf0&\mathbf0&\mathbf0&\mathbf0&\mathbf1\\  
\end{matrix}
$$
Voor dit probleem is (nog) geen polynomiaal algoritme bekend, dus
we weten (nog) niet of het tot $\mathrm{P}$ behoort.
Op dit moment is het dus een `moeilijk' probleem.
 
Het behoort wel tot de klasse $\mathrm{NP}$, dat zijn problemen waarvan het
verifi"eren dat een oplossing inderdaad correct is wel in~$\mathrm{P}$ zit.
De $\mathrm{N}$ staat voor 
`$\mathrm{N}$on-deterministic': het oplossen is polynomiaal
als je maar een orakel tot je beschikking hebt dat op cruciale momenten
tijdens het oplossen duidelijke informatie in de goede richting geeft
(dat kan dus ook een oplossing zijn).

Het overdekkingsprobleem is wat \emph{$\mathrm{NP}$-volledig} heet: als men 
kan bewijzen dat dit probleem toch in $\mathrm{P}$ zit dan heeft men
gelijk bewezen dat $\mathrm{P}=\mathrm{NP}$.
De geldigheid van die laatste gelijkheid is \'e\'en van de Clay
Millenium-problemen; het vaststellen of ontkrachten daarvan levert 
een miljoen dollar op.

Andere $\mathrm{NP}$-volledige problemen: het handelsreizigerprobleem
en Minesweeper.
Voor meer over $\mathrm{P}=\mathrm{NP}$ zie 
\cite{Clay,Wiki-P-and-NP}.


\subsection{Sudoku is $\mathrm{NP}$-volledig} 

We zullen zo dadelijk zien dat het oplossen van Sudoku's een speciaal
geval van het oplossen van overdekkingsproblemen is.
Dit laat zien dat het oplossen van willekeurige Sudoku's tot de klasse
$\mathrm{NP}$ behoort.

Aan de andere kant: het completeren van parti"ele Latijnse vierkanten,
ook een bekend $\mathrm{NP}$-volledig probleem, kan men oplossen door
Sudoku's op te lossen; dit maakt het algemene Sudoku-probleem dus
ook $\mathrm{NP}$-volledig.

Een (partieel) $n\times n$ Latijns vierkant wordt hierbij gerelateerd 
aan een $n^2\times n^2$ Sudoku.
Dat gaat eigenlijk redelijk eenvoudig,
we construeren eerst een speciale Sudoku:
$$
\begin{sudoku}[\sffamily]
 &1&2& &4&5& &7&8\cr\noalign{\hrd}
 &4&5& &7&8& &1&2\cr\noalign{\hrd}
 &7&8& &1&2& &4&5\cr\noalign{\hrv}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&7&8&9&1&2&3\cr\noalign{\hrd}
7&8&9&1&2&3&4&5&6\cr\noalign{\hrv}
2&3&4&5&6&7&8&9&1\cr\noalign{\hrd}
5&6&7&8&9&1&2&3&4\cr\noalign{\hrd}
8&9&1&2&3&4&5&6&7\cr\noalign{\hrd}
\end{sudoku}
$$
elke completering van deze Sudoku hoort bij een $3\times3$ Latijns vierkant
en omgekeerd:
$$
\vcenter{
\begin{sudoku}[\sffamily]
3a&1&2&3d&4&5&3g&7&8\cr\noalign{\hrd}
3b&4&5&3e&7&8&3h&1&2\cr\noalign{\hrd}
3c&7&8&3f&1&2&3i&4&5\cr\noalign{\hrv}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&7&8&9&1&2&3\cr\noalign{\hrd}
7&8&9&1&2&3&4&5&6\cr\noalign{\hrv}
2&3&4&5&6&7&8&9&1\cr\noalign{\hrd}
5&6&7&8&9&1&2&3&4\cr\noalign{\hrd}
8&9&1&2&3&4&5&6&7\cr\noalign{\hrd}
\end{sudoku}}
\qquad\Leftrightarrow\qquad
\vcenter{\begin{sudoku}[\sffamily]  
 a& d& g\cr\noalign{\hrd} 
 b& e& h\cr\noalign{\hrd}
 c& f& i\cr\end{sudoku}}
$$
In het algemeen relateert men $n\times n$-Latijnse vierkanten aan 
$n^2\times n^2$-Sudoku's.
Dus elk algoritme dat (willekeurige) Sudoku's oplost kan ook aangewend
worden om parti"ele Latijnse vierkanten te completeren.

Dat Sudoku inderdaad de status van $\mathrm{NP}$-volledig heeft is ook te 
zien aan de oplosstappen die op de bovengenoemde fora besproken worden: 
die komen vaak neer op het onderzoeken
van elk tweetal\slash drietal\slash\dots{} in iedere rij, iedere kolom
of ieder blok.
Dat komt uiteindelijk neer op het onderzoeken van \emph{elke} deelverzameling
van zo'n rij, kolom of blok.
Dit betekent dat, dankzij die varianten mee, een doorsnee gericht 
oplosprogramma voor een $n^2\times n^2$-Sudoku al gauw (veel meer dan) 
$2^{n^2}$ stappen zal moeten doen.
Een polynomiaal algoritme voor Sudoku zal er derhalve heel anders uit moeten 
zien dan de standaard oplossers die voor het $9\times9$-geval zijn geschreven.


\subsection{Back-tracking}

Sudoku's zijn ook met bruut geweld op te lossen: probeer gewoon
\'e\'en voor \'e\'en de vakken te vullen en ga telkens terug als je vastloopt.
Deze methode werkt altijd maar kost nogal wat tijd en ruimte: zo'n programma
werkt normaal gesproken recursief en dat betekent dat er voortdurend een
heleboel uitgesteld werk op de stapel blijft staan.
Zie \cite{Groot} voor een eenvoudige beschrijving van dit proces.
Voor alle duidelijkheid: back-tracking werkt zeker \emph{niet} in
polynomiale tijd (het zou in polynomiale tijd werken als iedere keer
het \emph{juiste} cijfer gekozen wordt).

Nu is Sudoku te herformuleren tot een overdekkingsprobleem.
Voor $9\times9$-Sudoku een verzameling met $324$ punten en een overdekking
met $729$ deelverzamelingen (die allen precies vier punten hebben).
De zaadjes komen dat overeen met verzamelingen uit de overdekking die zeker
in de te construeren uitdunning moeten zitten.
In~\cite{Wiki-Dancing-Links} wordt de vertaling netjes uitgelegd;
het is de moeite waard die pagina even met pen en papier bij de hand
door te lezen om wat schetsjes te kunnen maken.

Voor het overdekkingsprobleem is een algemeen algoritme opgesteld dat,
vertaald naar de Sudoku-situatie, neerkomt op back-tracken, waarbij telkens 
een cel met een minimaal aantal mogelijkheden wordt gekozen.
Het is daarmee een mix van wegstrepen en back-tracken.

Zie \cite{Wiki-Dancing-Links} voor een volledige beschrijving van het
algoritme, links voor meer informatie
en ook programma's die het algoritme implementeren.
Waarschuwing: zelfs een Baby-Sudoku geeft aanleiding tot een matrix met
$64$~kolommen;
men kan de uitvoering van het algoritme beter aan de computer overlaten.

\begin{thebibliography}{10}
  
\bibitem{Brouwer}
Andries Brouwer, \emph{Solving sudokus},\\ 
\texttt{http://homepages.cwi.nl/\~{}aeb/games/sudoku/solving0.html}

\bibitem{Clay}
Clay Mathematics Institute,
\emph{Millennium Prize Problems},\\
\texttt{http://www.claymath.org/millennium/}

\bibitem{Coster}
Matthijs Coster, \emph{Sudoku wiskundig bekeken}, Pythagoras, januari 2006

\bibitem{Dekking}
Michel Dekking, \emph{Meta Sudoku: hoe produceer je een puzzelboekje
voor een habbekrats}, Volkskrant.
Origineel via \texttt{http://dutiaw37.twi.tudelft.nl/\~{}kp/nwd}

\bibitem{FelgenhauerJarvis}
Bertram Felgenhauer en Frazer Jarvis,
\emph{There are 6670903752021072936960 Sudoku grids},
\texttt{http://www.shef.ac.uk/\~{}pm1afj/sudoku/}

\bibitem{Groot}
Jos Groot, \emph{Sudoku met de computer}, Pythagoras, februari 2006

\bibitem{Guardianboek}
The Guardian, \emph{Sudoku, 100 original puzzles}, Guardian Books, 2005

\bibitem{Guardiansudoku}
The Guardian, \emph{Sudoku classic},
\texttt{http://www.guardian.co.uk/sudoku}

\bibitem{Royle}
Gordon Royle,
\emph{Minimum Sudoku},
\texttt{http://www.csse.uwa.edu.au/\~{}gordon/sudokumin.php}

\bibitem{Sloane}
Neil J. A. Sloane,
\emph{The On-Line Encyclopedia of Integer Sequences},\\
\texttt{http://www.research.att.com/\~{}njas/sequences/Seis.html},
zie vooral A002860 (Latijnse vierkanten) en A107739 (Sudoku-vierkanten)

\bibitem{Wiki-P-and-NP}
Wikipedia, \emph{Complexity classes P and NP},\\ 
\texttt{http://en.wikipedia.org/wiki/Complexity\_classes\_P\_and\_NP}

\bibitem{Wiki-Dancing-Links}
Wikipedia, \emph{Dancing Links}, 
\texttt{http://en.wikipedia.org/wiki/Dancing\_Links}

\bibitem{Wiki-Sudoku}
Wikipedia, \emph{Sudoku}, \texttt{http://en.wikipedia.org/wiki/Sudoku}



\end{thebibliography}



\end{document}

