% -*- mode: LaTeX; -*-
%
\def\timestamp{%
Time-stamp: <nwd-slides.tex: Friday 03-02-2006 at 07:15:46 (cet)>}
\def\stripname Time-stamp: <#1 #2>{#2}
\edef\filedate{\expandafter\stripname\timestamp}
%
\documentclass[a4paper,landscape]{slides}
\usepackage{tuslides}

\usepackage{amsfonts,amsmath}
\DeclareMathSymbol{\varnothing}{\mathord}{AMSb}{"3F}
\DeclareRobustCommand{\stirlingtwo}{\genfrac\{\}{0pt}{}}

\newcommand{\kopje}[1]{{\large\bfseries #1\par}}
\makeatletter
\let\@topfil\relax
\makeatother

\input{sudokumacs}

\def\href#1#2{#2}
%\let\invisible\relax
\begin{document}

\begin{titlepage}
\begin{center}
Non impeditus ab ulla scientia
\end{center}
    
\title{Sudoku's en Wiskunde}
\author{K. P. Hart}
\date{3 februari, 2006}
\maketitle


\end{titlepage}

\skip0=\the\parskip
\large
\parskip=\skip0
\parskip= 20.0pt plus 18.0pt minus 9.0pt

\begin{slide}
\kopje{Programma}

\begin{itemize}
  \item Tellen
  \item Makkelijk, medium, moeilijk
  \item Hoeveel zaadjes?
  \item Een miljoen dollar verdienen?
\end{itemize}

\end{slide}


\begin{slide}
\kopje{Puzzels Tellen}

Vooralsnog onbegonnen werk.

Reden: De verzameling puzzels is nog (lang) niet afgebakend.
Hierover straks meer.
  
\end{slide}


\begin{slide}
\kopje{Latijnse vierkanten tellen}  

Sudoku-vierkanten zijn speciale Latijnse vierkanten.\\
Tot nu toe geteld (Sloane's A002860):

\small

\vfil
{\skip0=0pt plus 1000pt
\tabskip\skip0
\halign to\textwidth{$#$\hfil\tabskip1cm&\hfil$#$\tabskip\skip0\cr
      n&                                             a(n)\cr
      1&                                                1\cr
      2&                                                2\cr
      3&                                               12\cr
\blauw4& \blauw                                       576\cr
      5&                                           161280\cr
      6&                                        812851200\cr
      7&                                   61479419904000\cr 
      8&                            108776032459082956800\cr
\rood 9& \rood               5524751496156892842531225600\cr
     10&            9982437658213039871725064756920320000\cr
     11& 776966836171770144107444346734230682311065600000\cr
\noalign{\smallskip}
\omit\span\omit\hfil\ttfamily 
\href{http://www.research.att.com/~ynjas/sequences/A002860}%
{http://www.research.att.com/\~{}njas/sequences/A002860}\hfil\cr}}

\end{slide}


\begin{slide}
\kopje{Sudoku-vierkanten tellen}  

Een Sudoku-vierkant is een Latijns vierkant met extra beperkingen.

Hoe te tellen?

Verdeel in groepen, tel iedere groep en \\tel de aantallen op.

Beter: verdeel in \emph{even grote} groepen, tel \'e\'en groep en
vermenigvuldig met aantal groepen.
  
(IJdele hoop)
\end{slide}


\begin{slide}
\kopje{Baby-Sudoku\hfill\vbox to 0pt{\kern-1cm 
\begin{babysudoku}
&&&\cr\noalign{\hrd}
&&&\cr\noalign{\hrv}
&&&\cr\noalign{\hrd}
&&&\cr
\end{babysudoku}\vss}}

We tellen alle $4\times4$-sudoku-vierkanten.

We verdelen de totale verzameling in steeds kleinere 
groepen tot het tellen van \'e\'en groep makkelijk genoeg is.
  
\end{slide}


\begin{slide}
\kopje{Stap 1 \qquad $\rood24$ groepen 
\hfill\vtop to 0pt{\vss
\begin{babysudoku}
\rood1&\rood2&&\cr\noalign{\hrd}
\rood3&\rood4&&\cr\noalign{\hrv}
      &      &&\cr\noalign{\hrd}
      &      &&\cr
\end{babysudoku}\kern-1cm}}

Elke linkerbovenhoek bepaalt \'e\'en groep.

Er zijn $4!=24$ verschillende linkerbovenhoeken.

Al die groepen zijn even groot: hernummeren.
 
\end{slide}


\begin{slide}
\kopje{Stap 2 \qquad $24\times\rood 2$ groepen 
   \hfill\vtop to 0pt{\vss
\begin{babysudoku}
1&2&\rood3&\rood4\cr\noalign{\hrd}
3&4&      &      \cr\noalign{\hrv}
 & &      &      \cr\noalign{\hrd}
 & &      &      \cr
\end{babysudoku}\kern-1cm}}
  
Elke aanvulling van {\rood de eerste rij} bepaald een groep.

Twee even grote groepen:\\ verwissel de laatste twee kolommen.

We bekijken \'e\'en zo'n groep.

\end{slide}



\begin{slide}
\kopje{Stap 3 \qquad $24\times 2\times\rood2$ groepen 
   \hfill\vtop to 0pt{\vss
\begin{babysudoku}
1&2&     3&     4\cr\noalign{\hrd}
3&4&\rood1&\rood2\cr\noalign{\hrv}
 & &      &      \cr\noalign{\hrd}
 & &      &      \cr
\end{babysudoku}\kern-1cm}\quad \vtop to 0pt{\vss
\begin{babysudoku}
1&2&     3&     4\cr\noalign{\hrd}
3&4&\rood2&\rood1\cr\noalign{\hrv}
 & &      &      \cr\noalign{\hrd}
 & &      &      \cr
\end{babysudoku}\kern-1cm}}
  
Elke aanvulling van {\rood de tweede rij} bepaald een groep.

We bekijken beide groepen.

\end{slide}


\begin{slide}
\kopje{Stap 4 \qquad De groepen tellen 
   \hfill\vtop to 0pt{\vss
\begin{babysudoku}
     1&2&      3&4\cr\noalign{\hrd}
     3&4&      1&2\cr\noalign{\hrv}
\rood2& &\blauw4& \cr\noalign{\hrd}
\rood4& &\blauw2& \cr
\end{babysudoku}\kern-1cm}\quad \vtop to 0pt{\vss
\begin{babysudoku}
     1&2&      3&      4\cr\noalign{\hrd}
     3&4&      2&      1\cr\noalign{\hrv}
\rood2& &\blauw4&       \cr\noalign{\hrd}
\rood4& &       &\blauw2\cr
\end{babysudoku}\kern-1cm}}

De aanvullingen van {\rood de eerste kolom} geven, in beide gevallen,
even veel completeringen (via verwisseling van de laatste rijen);
we krijgen een factor $2$. (Bonus: $2$ en $4$ liggen meteen vast.)


\end{slide}

\begin{slide}
\kopje{Stap 4 \qquad De groepen tellen 
   \hfill\vtop to 0pt{\vss
\begin{babysudoku}
     1&2&      3&4\cr\noalign{\hrd}
     3&4&      1&2\cr\noalign{\hrv}
\rood2& &\blauw4& \cr\noalign{\hrd}
\rood4& &\blauw2& \cr
\end{babysudoku}\kern-1cm}\quad \vtop to 0pt{\vss
\begin{babysudoku}
     1&2&      3&      4\cr\noalign{\hrd}
     3&4&      2&      1\cr\noalign{\hrv}
\rood2& &\blauw4&       \cr\noalign{\hrd}
\rood4& &       &\blauw2\cr
\end{babysudoku}\kern-1cm}}

Hier zijn alle completeringen.
$$
\hbox to\displaywidth{\hss
\begin{babysudoku}
1&     2&3&     4\cr\noalign{\hrd}
3&     4&1&     2\cr\noalign{\hrv}
2&\rood1&4&\rood3\cr\noalign{\hrd}
4&\rood3&2&\rood1\cr
\end{babysudoku}\hss
\begin{babysudoku}
1&     2&3&     4\cr\noalign{\hrd}
3&     4&1&     2\cr\noalign{\hrv}
2&\rood3&4&\rood1\cr\noalign{\hrd}
4&\rood1&2&\rood3\cr
\end{babysudoku}\hss
\begin{babysudoku}
1&     2&     3&     4\cr\noalign{\hrd}
3&     4&     2&     1\cr\noalign{\hrv}
2&\rood1&     4&\rood3\cr\noalign{\hrd}
4&\rood3&\rood1&     2\cr
\end{babysudoku}\hss
\begin{babysudoku}
1&     2&            3&            4\cr\noalign{\hrd}
3&     4&            2&            1\cr\noalign{\hrv}
2&\rood3&            4&\rood$\times$\cr\noalign{\hrd}
4&\rood1&\rood$\times$&            2\cr
\end{babysudoku}\hss
}
$$
Dus: links $2\times2=4$ en rechts $2\times1=2$.

(Daarom dus ijdele hoop)

\end{slide}



\begin{slide}
\kopje{Stap 5 \qquad  Optellen} 
\iffalse
\begin{babysudoku}
&1&&2&&3&&4&\cr\noalign{\hrd}
&3&&4&&1&&2&\cr\noalign{\hrull}
&2&&\rood1&&\blauw4&&\rood3&\cr\noalign{\hrd}
&4&&\rood3&&\groen2&&\rood1&\cr
\end{babysudoku}
\begin{babysudoku}
&1&&2&&3&&4&\cr\noalign{\hrul}
&3&&4&&1&&2&\cr\noalign{\hrull}
&2&&\rood3&&\blauw4&&\rood1&\cr\noalign{\hrul}
&4&&\rood1&&\groen2&&\rood3&\cr
\end{babysudoku}
\fi
  
De eerste variant levert $24\times2\times1\times2\times2$ vierkanten.

De tweede variant levert $24\times2\times1\times2\times1$ vierkanten.

Optellen: in totaal $24\times 2\times 1\times 2\times3=\rood288$ 
baby-sudoku-vierkanten.

\end{slide}



\begin{slide}
\kopje{Echte Sudoku's tellen\hfill\vbox to0pt{\kern-2cm
\begin{sudoku}
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}\vss}
}  

Meteen: $9!$ groepen

Hoe nu verder?

Net als bij baby-sudoku:

vul de eerste drie rijen aan.

Echter \dots

\end{slide}


\begin{slide}
\kopje{Volgende stappen}

\dots{} reeds bij de eerste rij divergeert de boekhouding, bijvoorbeeld
tussen
$$
\hbox to \hsize{\hss 
$\vcenter{\begin{sudoku}
1&2&3&4&5&6&7&8&9\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}}$\hss
\hbox{ en }\hss
$\vcenter{\begin{sudoku}
1&2&3&4&5&7&6&8&9\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}}$\hss}
$$
\end{slide}

\begin{slide}
\kopje{De eerste\hfill\vbox to0pt{\kern-2cm
\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&\rood7&\rood8&\rood9&&&\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}\vss}}

Deze geeft $(3!)^6$ aanvullingen\\
 van de eerste drie rijen:

\end{slide}

\begin{slide}
\kopje{De eerste\hfill\vbox to0pt{\kern-2cm
\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&\rood7&\rood8&\rood9&\blauw1&\blauw2&\blauw3\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}\vss}}

Deze geeft $(3!)^6$ aanvullingen\\
 van de eerste drie rijen:

\end{slide}

\begin{slide}
\kopje{De eerste\hfill\vbox to0pt{\kern-2cm
\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&\rood7&\rood8&\rood9&\blauw1&\blauw2&\blauw3\cr\noalign{\hrd}
7&8&9&\blauw1&\blauw2&\blauw3&&&\cr
\noalign{\hrv}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrv}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr
\end{sudoku}\vss}}

Deze geeft $(3!)^6$ aanvullingen\\
 van de eerste drie rijen:

\end{slide}

\begin{slide}
\kopje{De eerste\hfill\vbox to0pt{\kern-2cm
\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&\rood7&\rood8&\rood9&\blauw1&\blauw2&\blauw3\cr\noalign{\hrd}
7&8&9&\blauw1&\blauw2&\blauw3&\groen4&\groen5&\groen6\cr
\noalign{\hrv}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrv}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr
\end{sudoku}\vss}}

Deze geeft $(3!)^6$ aanvullingen\\
 van de eerste drie rijen:

Verwissel blok 2 en blok 3:\\
 dat geeft $2\times(3!)^6$ aanvullingen\\
(en a priori \emph{geen} garantie dat die allemaal evenveel completeringen 
 hebben)


\end{slide}



\begin{slide}
\kopje{De tweede\hfill\vbox to0pt{\kern-2cm\begin{sudoku}
1&2&3&4&5&7&6&8&9\cr\noalign{\hrd}
4&5&6&\blauw a&\rood8&\rood9&\rood7&\blauw b&\blauw c\cr
\noalign{\hrd}
7&8&9&\groen6&\blauw b&\blauw c&\groen4&\groen5&\blauw a\cr
\noalign{\hrv}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrv}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr
\end{sudoku}\vss}}

Deze geeft $3\times (3!)^6$: 

De $(3!)^6$ als eerder;\\
de factor $3$ komt van \\
de mogelijkheden\\
$a=1$, $a=2$ en $a=3$ \\
(NB $\{a,b,c\}=\{1,2,3\}$)

\end{slide}

\begin{slide}

\kopje{Alles bij elkaar}

Er zijn $2\times(3!)^6 + 2\times9\times3\times(3!)^6=2612736$ aanvullingen van 
de eerste drie rijen.
Dat is veel. 

Er zijn reducties: 

permuteer kolommen binnen blok 2 en ook binnen blok 3 

verwissel blok 2 en blok 3

geeft equivalentieklassen die $72$ groot zijn: nog maar $36288$ tellingen
  
\end{slide}

\begin{slide}
\kopje{Getruukte reducties}

Voorbeeld
$$
\vcenter{\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&7&9&8&3&1&2\cr\noalign{\hrd}
7&8&9&2&3&1&5&6&4\cr
\end{sudoku}}
\qquad\hbox{en}\qquad
\vcenter{\begin{sudoku}
1&2&3&9&7&8&4&6&5\cr\noalign{\hrd}
4&5&6&1&2&3&8&9&7\cr\noalign{\hrd}
7&8&9&4&5&6&2&3&1\cr
\end{sudoku}}
$$
hebben even veel completeringen.

Verwissel blok 1 en blok 2\phantom{,}
$$
\vcenter{\begin{sudoku}
4&5&6&1&2&3&7&8&9\cr\noalign{\hrd}
7&9&8&4&5&6&3&1&2\cr\noalign{\hrd}
2&3&1&7&8&9&5&6&4\cr
\end{sudoku}}
$$
\end{slide}

\begin{slide}
\kopje{Getruukte reducties}

Voorbeeld
$$
\vcenter{\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&7&9&8&3&1&2\cr\noalign{\hrd}
7&8&9&2&3&1&5&6&4\cr
\end{sudoku}}
\qquad\hbox{en}\qquad
\vcenter{\begin{sudoku}
1&2&3&9&7&8&4&6&5\cr\noalign{\hrd}
4&5&6&1&2&3&8&9&7\cr\noalign{\hrd}
7&8&9&4&5&6&2&3&1\cr
\end{sudoku}}
$$
hebben even veel completeringen.

Verwissel blok 1 en blok 2 en {\rood hernummer}: $4\to\rood1$\phantom{,}
$$
\vcenter{\begin{sudoku}
\rood1&5&6&1&2&3&7&8&9\cr\noalign{\hrd}
7&9&8&\rood1&5&6&3&1&2\cr\noalign{\hrd}
2&3&1&7&8&9&5&6&\rood1\cr
\end{sudoku}}
$$
\end{slide}


\begin{slide}
\kopje{Getruukte reducties}

Voorbeeld
$$
\vcenter{\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&7&9&8&3&1&2\cr\noalign{\hrd}
7&8&9&2&3&1&5&6&4\cr
\end{sudoku}}
\qquad\hbox{en}\qquad
\vcenter{\begin{sudoku}
1&2&3&9&7&8&4&6&5\cr\noalign{\hrd}
4&5&6&1&2&3&8&9&7\cr\noalign{\hrd}
7&8&9&4&5&6&2&3&1\cr
\end{sudoku}}
$$
hebben even veel completeringen.

Verwissel blok 1 en blok 2 en {\rood hernummer}: $5\to\rood2$\phantom{,}
$$
\vcenter{\begin{sudoku}
\rood1&\rood2&6&1&2&3&7&8&9\cr\noalign{\hrd}
7&9&8&\rood1&\rood2&6&3&1&2\cr\noalign{\hrd}
2&3&1&7&8&9&\rood2&6&\rood1\cr
\end{sudoku}}
$$
\end{slide}

\begin{slide}
\kopje{Getruukte reducties}

Voorbeeld
$$
\vcenter{\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&7&9&8&3&1&2\cr\noalign{\hrd}
7&8&9&2&3&1&5&6&4\cr
\end{sudoku}}
\qquad\hbox{en}\qquad
\vcenter{\begin{sudoku}
1&2&3&9&7&8&4&6&5\cr\noalign{\hrd}
4&5&6&1&2&3&8&9&7\cr\noalign{\hrd}
7&8&9&4&5&6&2&3&1\cr
\end{sudoku}}
$$
hebben even veel completeringen.

Verwissel blok 1 en blok 2 en {\rood hernummer}: $6\to\rood3$\phantom{,}
$$
\vcenter{\begin{sudoku}
\rood1&\rood2&\rood3&1&2&3&7&8&9\cr\noalign{\hrd}
7&9&8&\rood1&\rood2&\rood3&3&1&2\cr\noalign{\hrd}
2&3&1&7&8&9&\rood2&\rood3&\rood1\cr
\end{sudoku}}
$$
\end{slide}


\begin{slide}
\kopje{Getruukte reducties}

Voorbeeld
$$
\vcenter{\begin{sudoku}
1&2&3&4&5&6&7&8&9\cr\noalign{\hrd}
4&5&6&7&9&8&3&1&2\cr\noalign{\hrd}
7&8&9&2&3&1&5&6&4\cr
\end{sudoku}}
\qquad\hbox{en}\qquad
\vcenter{\begin{sudoku}
1&2&3&9&7&8&4&6&5\cr\noalign{\hrd}
4&5&6&1&2&3&8&9&7\cr\noalign{\hrd}
7&8&9&4&5&6&2&3&1\cr
\end{sudoku}}
$$
hebben even veel completeringen.

Verwissel blok 1 en blok 2 en {\rood hernummer}: $1\to\rood9$\phantom{,}
$$
\vcenter{\begin{sudoku}
\rood1&\rood2&\rood3&\rood9&\rood7&\rood8&\rood4&\rood6&\rood5\cr
\noalign{\hrd}
\rood4&\rood5&\rood6&\rood1&\rood2&\rood3&\rood8&\rood9&\rood7\cr
\noalign{\hrd}
\rood7&\rood8&\rood9&\rood4&\rood6&\rood5&\rood2&\rood3&\rood1\cr
\end{sudoku}}
$$
\end{slide}


\begin{slide}
\kopje{Uiteindelijk}

Na een serie van dergelijke symmetrie- en permutatie-argumenten kan men de 
totale zoektocht reduceren tot $71$ tellingen (dat mag de computer dan doen).

Resultaat: $6\,670\,903\,752\,021\,072\,936\,960$ Sudoku-vier\-kanten.

Vergelijk: Latijns: $5{,}52\times10^{27}$; Sudoku: $6{,}67\times10^{21}$

\texttt{http://www.shef.ac.uk/\~{}pm1afj/sudoku/}

\end{slide}

\begin{slide}
\kopje{Echt verschillende vierkanten}

De Sudoku-symmetrie-groep is uitgerekend.

Voortgebracht door: hernummeringen, spiegelingen, rotaties, 
permutaties van rijen\slash kolommen 1--3, 
permutaties van rijen\slash kolommen 4--6, 
permutaties van rijen\slash kolommen 7--9,
permutaties van `dikke' rijen\slash kolommen.


Er blijven $5\,472\,730\,538$ `echt verschillende' suduko-vier\-kanten over.

\texttt{http://www.shef.ac.uk/\~{}pm1afj/sudoku/sudgroup.html}

\end{slide}

\begin{slide}
\kopje{Een toepassing}

Als je de symmetriegroep goed kent kun je met een handvol puzzels een
heel boekje vullen.

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


\begin{slide}
\kopje{Hoe bepaal je de moeilijkheidsgraad?}

Algemene methode: laat een programma de puzzel oplossen en bijhouden wat
voor soort stappen het programma moet doet.
Er zijn massa's stappen bedacht, zie:

Matthijs Coster, \textit{Sudoku wiskundig bekeken}, Pythagoras, januari 2006
(\emph{word abonnee}).

Andries Brouwer's website:\\ 
\texttt{http://homepages.cwi.nl/\~{}aeb/games/sudoku/solving0.html}

Wikipedia: \texttt{http://en.wikipedia.org/wiki/Sudoku}
  
\end{slide}

\begin{slide}
  
\kopje{Een voorbeeld}



We nemen drie soorten stappen.

\begin{enumerate}
\item Wegstrepen en kijken wat overblijft. \invisible

\item Uniciteit controleren: een cijfer kan nog maar op \'e\'en plaats
   in een rij\slash kolom\slash blok staan, vul in.

\item Rij\slash kolom in een blok: het cijfer staan binnen een blok in \'e\'en 
   rij\slash kolom, streep weg uit rest van die rij\slash kolom.
\end{enumerate}

\end{slide}

\begin{slide}
  
\kopje{Een voorbeeld}

We nemen drie soorten stappen.

\begin{enumerate}
\item Wegstrepen en kijken wat overblijft.

\item Uniciteit controleren: een cijfer kan nog maar op \'e\'en plaats
   in een rij\slash kolom\slash blok staan, vul in.
\invisible

\item Rij/slash kolom in een blok: het cijfer staan binnen een blok in \'e\'en 
   rij\slash kolom, streep weg uit rest van die rij\slash kolom.
\end{enumerate}

\end{slide}

\begin{slide}
  
\kopje{Een voorbeeld}

We nemen drie soorten stappen.

\begin{enumerate}
\item Wegstrepen en kijken wat overblijft.

\item Uniciteit controleren: een cijfer kan nog maar op \'e\'en plaats
   in een rij\slash kolom\slash blok staan, vul in.

\item Rij\slash kolom in een blok: het cijfer staan binnen een blok in \'e\'en 
   rij\slash kolom, streep weg uit rest van die rij\slash kolom.
\end{enumerate}

\end{slide}

\begin{slide}
  
\kopje{{\invisible Een voorbeeld}}

Zo komen we tot \dots
\end{slide}

\begin{slide}
  
\kopje{{\invisible Een voorbeeld}}


Zo komen we tot \dots

\begin{center}
\Large\bfseries\rood De NWD-classificatie van Sudoku's  
\end{center}

\end{slide}


\begin{slide}
\kopje{Makkelijk\hfill\vbox to0pt{\kern-2cm
\begin{sudoku}
9& & & &5&6&1& &7\cr\noalign{\hrd}
 & &8& & & & & &3\cr\noalign{\hrd}
 & &4& & &9& & & \cr\noalign{\hrv}
 & & & & &5& &4&6\cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrd}
7&3& &2& & & & & \cr\noalign{\hrv}
 & & &9& & &5& & \cr\noalign{\hrd}
8& & & & & &6& & \cr\noalign{\hrd}
5& &2&7&3& & & &8\cr
\end{sudoku}\vss}}

Deze kan met all\'e\'en wegstrepen:
\vfill
Nummer 21 in \textit{The Guardian Sudoku Book 1}, \textbf{Medium}.
  
\end{slide}

\begin{slide}
\kopje{Minder makkelijk\hfill\vbox to0pt{\kern-2cm \begin{sudoku}
 &2& & &9& &7& &5\cr\noalign{\hrd}
3&9& & & &7& & & \cr\noalign{\hrd}
 & &1& & & &9& &8\cr\noalign{\hrv}
 & & & & &3& &1& \cr\noalign{\hrd}
6& & & &5& & & &7\cr\noalign{\hrd}
 &5& &1& & & & & \cr\noalign{\hrv}
7& &8& & & &4& & \cr\noalign{\hrd}
 & & &3& & & &7&6\cr\noalign{\hrd}
5& &2& &6& & &8& \cr
\end{sudoku}\vss}}

Wegstrepen\\ 
\`en af en toe uniciteit controleren.

\vfill
Nummer 1 in \textit{The Guardian Sudoku Book 1}, \textbf{Easy}.
  
\end{slide}

\begin{slide}
\kopje{Moeilijk\hfill\vbox to0pt{\kern-2cm \begin{sudoku}
 & &6&9& & & & & \cr\noalign{\hrd}
 & & &3& & & &4&8\cr\noalign{\hrd}
 & & &7& & & & &2\cr\noalign{\hrv}
 & &3& & & & & &6\cr\noalign{\hrd}
 &4& & & & & &8& \cr\noalign{\hrd}
9& & & & & &5& & \cr\noalign{\hrv}
2& & & & &6& & & \cr\noalign{\hrd}
7&8& & & &4& & & \cr\noalign{\hrd}
 & & & & &5&9& & \cr
\end{sudoku}\vss}}

Lukt met\\ 
wegstrepen, uniciteit controleren  \\
\`en: `rij\slash kolom in een blok'


\vfill
Nummer 209 op \texttt{www.guardian.co.uk/sudoku}, \textbf{Hard}.
  
\end{slide}

\begin{slide}
\kopje{Heel moeilijk\hfill\vbox to0pt{\kern-2cm\begin{sudoku}
 &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}\vss}}

Na\\
 wegstrepen,\\
  uniciteits-controles\\
 en `rij/kolom in een blok':\\
 nog geen enkel nieuw cijfer geplaatst.

\vfill
Nummer 80 in \textit{The Guardian Sudoku Book 1},  \textbf{Hard}.
  
\end{slide}



\begin{slide}
\kopje{Hoeveel zaadjes?}

Hoeveel cijfers moeten er minimaal gegeven zijn om de oplossing uniek
te maken?

{\rood Zeker acht verschillende cijfers gebruiken}

Immers, als twee cijfers, zeg $8$ en $9$, niet gebruikt zijn\\
verwissel dan in een oplossing alle achten en negens:\\
{\rood  nog een oplossing}.
  
\end{slide}


\begin{slide}
\kopje{Hoeveel zaadjes?}

Hoeveel cijfers moeten er minimaal gegeven zijn om de oplossing uniek
te maken?

{\rood Zeventien kan}

Er zijn {\rood$35396$} puzzels met 17 zaadjes gevonden;
alle `irreducibel', er zit geen puzzel met 16 zaadjes in.

\texttt{http://www.csse.uwa.edu.au/\~{}gordon/sudokumin.php}

Hier gaapt nog een groot gat \dots
  
\end{slide}

\begin{slide}
\kopje{Een bijna-voorbeeld\hfill\vbox to0pt{\kern-2cm\begin{sudoku}
 & & & & &5& &8&1\cr\noalign{\hrd}
6& &4&7& & & & & \cr\noalign{\hrd}
 & & & & & & & & \cr\noalign{\hrv}
 & & &2& & &7& & \cr\noalign{\hrd}
 &8& & & & & &4& \cr\noalign{\hrd}
 &1& & & & & & & \cr\noalign{\hrv}
 & & & &1& & & &5\cr\noalign{\hrd}
2& & & & & &4& & \cr\noalign{\hrd}
7& & & & & & & & \cr
\end{sudoku}\vss}}
 
Deze Sudoku heeft $16$ zaadjes.

$3$ en $9$ ontbreken,\\ dus niet uniek oplosbaar

Hij heeft \emph{precies twee} oplossingen

Bedacht door H. N. Post (oud-afstudeerder TUD)
\end{slide}


\begin{slide}
\kopje{Zaadjes voor Baby-Sudoku}

{\rood Vier is genoeg}

$$
\vcenter{\begin{babysudoku}
\rood1& & & \cr\noalign{\hrd}
 & & &\rood3\cr\noalign{\hrv}
 & &\rood2& \cr\noalign{\hrd}
 &\rood4& & \cr
\end{babysudoku}}
\longrightarrow
\vcenter{\begin{babysudoku}
1& & & \cr\noalign{\hrd}
 & &\rood1&3\cr\noalign{\hrv}
 &\rood1&2& \cr\noalign{\hrd}
 &4& &\rood1\cr
\end{babysudoku}}
\longrightarrow
\vcenter{\begin{babysudoku}
1& & &\rood2\cr\noalign{\hrd}
 &\rood2&1&3\cr\noalign{\hrv}
 &1&2& \cr\noalign{\hrd}
\rood2&4& &1\cr
\end{babysudoku}}
\longrightarrow
\vcenter{\begin{babysudoku}
1&\rood3&\rood4&2\cr\noalign{\hrd}
\rood4&2&1&3\cr\noalign{\hrv}
\rood3&1&2&\rood4\cr\noalign{\hrd}
2&4&\rood3&1\cr
\end{babysudoku}}
$$

Hoe zit het met {\rood drie}?  
\end{slide}

\begin{slide}
\kopje{Zaadjes voor Baby-Sudoku}

Zeker drie \emph{verschillende} cijfers gebruiken, dus we nemen 
$1$, $2$ en $3$.

Wat niet kan:
$$
\vcenter{\begin{babysudoku}
\z&\z& & \cr\noalign{\hrd}
\z&\z& &\cr\noalign{\hrv}
\z&\z& & \cr\noalign{\hrd}
\z&\z& & \cr
\end{babysudoku}}
\hbox{\qquad of\qquad }
\vcenter{\begin{babysudoku}
\z&\z&\z&\z\cr\noalign{\hrd}
\z&\z&\z&\z\cr\noalign{\hrv}
 & & & \cr\noalign{\hrd}
 & & & \cr
\end{babysudoku}}
$$
\end{slide}


\begin{slide}
\kopje{Zaadjes voor Baby-Sudoku}

Wat niet kan:
$$
\vcenter{\begin{babysudoku}
\z&\z& & \cr\noalign{\hrd}
\z&\z& &\cr\noalign{\hrv}
\z&\z& & \cr\noalign{\hrd}
\z&\z& & \cr
\end{babysudoku}}
\hbox{\qquad of\qquad }
\vcenter{\begin{babysudoku}
\z&\z&\z&\z\cr\noalign{\hrd}
\z&\z&\z&\z\cr\noalign{\hrv}
 & & & \cr\noalign{\hrd}
 & & & \cr
\end{babysudoku}}
$$
De oplossing is in zo'n situatie nooit uniek:\\ 
links kun je twee kolommen verwisselen;\\
rechts kun je twee rijen verwisselen.
\end{slide}


\begin{slide}
\kopje{Zaadjes voor Baby-Sudoku}

Dus iets als:
$$
\vcenter{\begin{babysudoku}
\z&\z&\z&\z\cr\noalign{\hrd}
\z&\z&\z&\z\cr\noalign{\hrv}
\z&\z& & \cr\noalign{\hrd}
\z&\z& & \cr
\end{babysudoku}}
\hbox{\qquad of\qquad }
\vcenter{\begin{babysudoku}
\z&\z& & \cr\noalign{\hrd}
\z&\z& &\cr\noalign{\hrv}
 & &\z&\z\cr\noalign{\hrd}
 & &\z&\z\cr
\end{babysudoku}}
$$
\end{slide}

\begin{slide}
\kopje{Zaadjes voor Baby-Sudoku}

Na symmetrie-overwegingen blijven zes mogelijkheden over:
$$
\vcenter{\begin{babysudoku}
1& & & \cr\noalign{\hrd}
 & & & \cr\noalign{\hrv}
\rood3&\blauw3&2& \cr\noalign{\hrd}
\groen3&\oranje3&\color[named]{Magenta}3&\color[named]{Cyan}3\cr
\end{babysudoku}}
$$
Geen van deze werkt.

\end{slide}


\begin{slide}
\kopje{Zaadjes voor Sudoku\hfill\vbox to0pt{\kern-2cm\begin{sudoku}
 & & &\z&\z&\z& & & \cr\noalign{\hrd}
 & & &\z&\z&\z& & & \cr\noalign{\hrd}
 & & &\z&\z&\z& & & \cr\noalign{\hrv}
 & & & & & &\z&\z&\z\cr\noalign{\hrd}
 & & & & & &\z&\z&\z\cr\noalign{\hrd}
 & & & & & &\z&\z&\z\cr\noalign{\hrv}
\z&\z&\z& & & & & & \cr\noalign{\hrd}
\z&\z&\z& & & & & & \cr\noalign{\hrd}
\z&\z&\z& & & & & & \cr
\end{sudoku}\vss}}

Een aanloop tot een bewijs van \\
``{\rood acht} is niet genoeg''.

In elke `dikke' rij\\
 en elke `dikke' kolom\\
moet gezaaid zijn

\end{slide}


\begin{slide}
\kopje{Zaadjes voor Sudoku\hfill\vbox to0pt{\kern-2cm\begin{sudoku}
\z&\z&\z& & & &\y&\y&\y\cr\noalign{\hrd}
\z&\z&\z& & & &\y&\y&\y\cr\noalign{\hrd}
\z&\z&\z& & & &\y&\y&\y\cr\noalign{\hrv}
 & & &\z&\z&\z& & & \cr\noalign{\hrd}
 & & &\z&\z&\z& & & \cr\noalign{\hrd}
 & & &\z&\z&\z& & & \cr\noalign{\hrv}
 & & & & & &\z&\z&\z\cr\noalign{\hrd}
 & & & & & &\z&\z&\z\cr\noalign{\hrd}
 & & & & & &\z&\z&\z\cr
\end{sudoku}\vss}}

Na permutatie komt men\\
 tot deze vorm

$\varnothing$ staat voor een leeg vakje

  
\end{slide}


\begin{slide}
\kopje{Zaadjes voor Sudoku\hfill\vbox to0pt{\kern-2cm
\begin{sudoku}
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}\vss}}

Permuteer binnen de dikke rijen en \\
kolommen en hernummer

Ga Uw gang,

 U hoeft maar zo'n $\binom{69}{5}=11\,238\,513$ mogelijkheden
na te lopen \dots
  
\end{slide}


\begin{slide}
\kopje{Kansrekening?}

Hoe strooit men acht zaadjes?
\begin{itemize}
\item kies acht cellen:  $\binom{81}{8}$  manieren; 

\item kies acht cijfers: $\binom98$ manieren

\item strooi de cijfers: $8!$ manieren
\end{itemize}

Dus $\binom{81}{8}\times9\times8!=11\,671\,764\,328\,224\,000$ strooimogelijkheden.

\end{slide}


\begin{slide}
\kopje{Kansrekening?}

$11\,671\,764\,328\,224\,000$ is natuurlijk een grove overschatting van het
aantal `goede' strooimogelijkheden.
 
Maar goed: $1{,}167\times10^{16}\ll6{,}6\times10^{21}$.

De verhouding is ongeveer $1:571\,542$

Dit bewijst natuurlijk, helaas, niets.

 
\end{slide}

\begin{slide}
\kopje{Geld verdienen?}

Sudoku's oplossen is net zo moeilijk als Latijnse vierkanten completeren.

Preciezer: $n^2\times n^2$ Sudoku's oplossen komt overeen met $n\times n$
Latijnse vierkanten completeren.

Dat laatste is NP-volledig, dus algemene Sudoku ook.

  
\end{slide}

\begin{slide}
\kopje{Hoe dan?\hfill\vbox to0pt{\kern-2cm\begin{sudoku}
 &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}\vss}}


Maak een speciale Sudoku:

Deze heeft 12 completeringen 

want op de lege plekken komen \\
de drievouden $3$, $6$ en $9$

Elk $3\times3$ Latijns vierkant past daar

\end{slide}

\begin{slide}
\kopje{Vertaling}

$$
\vcenter{
\begin{sudoku}
\rood3a&1&2&\rood3d&4&5&\rood3g&7&8\cr\noalign{\hrd}
\rood3b&4&5&\rood3e&7&8&\rood3h&1&2\cr\noalign{\hrd}
\rood3c&7&8&\rood3f&1&2&\rood3i&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}  
\rood a&\rood d&\rood g\cr\noalign{\hrd} 
\rood b&\rood e&\rood h\cr\noalign{\hrd}
\rood c&\rood f&\rood i\cr\end{sudoku}}
$$
\end{slide}

\begin{slide}
\kopje{P versus NP}



\textbf{P}: 
de problemen die in polynomiale tijd opgelost kunnen worden, bijvoorbeeld:

\textbf{matrix-eliminatie}: 
het op driehoeksvorm brengen van een $n\times n$-matrix
kost $\frac12n(n+1)$ vermenigvuldigingen. 
Sinds kort: vaststellen of een getal priem is 
 (polynomiaal in het aantal cijfers).

\end{slide}

\begin{slide}
\kopje{P versus NP}


\textbf{NP}: 
de problemen waarvan het controleren van een oplossing polynomiale tijd
kost. Handelsreiziger, Minesweeper, $n^2\times n^2$-Sudoku, \dots

Bewijzen of weerleggen dat \textbf{P}${}={}$\textbf{NP} is \'e\'en van de 
Clay-millennium\-pro\-ble\-men en is dus goed voor een miljoen dollar.

\end{slide}

\begin{slide}
\kopje{NP-volledig}

Het handelsreizigerprobleem is \emph{\textbf{NP}-volledig}: als je bewijst dat
dat in \textbf{P} zit volgt meteen \textbf{P}${}={}$\textbf{NP}.

Ook \textbf{NP}-volledig: Minesweeper en $n^2\times n^2$-Sudoku
\end{slide}

\begin{slide}
\kopje{Back-tracking}

Bruut geweld: probeer \'e\'en voor \'e\'en de vakken te vullen en loop telkens
terug als je vastloopt.

Jos Groot, \textit{Sudoku met de computer},\\ Pythagoras, februari 2006
(\emph{word abonnee}).
  
\end{slide}

\begin{slide}
\kopje{Subtiele Back-tracking}

Sudoku is een speciaal geval van een algemeen combinatorisch probleem:
gegeven een overdekking van een eindige verzameling, dun deze uit tot
een \emph{disjuncte} overdekking.

In dit geval: een verzameling van $324$ punten met een overdekking die
uit $729$ deelverzamelingen bestaat.
De zaadjes komen overeen met elementen uit de overdekking die mee 
moeten doen.

\end{slide}

\begin{slide}
\kopje{Subtiele Back-tracking}

Er is een fraai algoritme voor het overdekkingsprobleem opgesteld; voor
Sudoku komt het neer op wegstrepen tot het niets meer oplevert, 
back-tracken tot je weer kunt wegstrepen, \dots

Zie \texttt{http://en.wikipedia.org/wiki/Dancing\_Links}\\ en de links aldaar
  
\end{slide}


\end{document}

