\documentclass[a4paper,10pt]{article}
\usepackage[dutch]{babel}
\usepackage{array}
\usepackage{color}
\usepackage{colortbl}

\newcommand{\mc}[3]{\multicolumn{#1}{#2}{#3}}
\definecolor{tcA}{rgb}{0,0,0.5}

\title{Artifici\"{e}le Intelligentie \\ Project 2 - Constraint Processing}
\author{Philippe Dellaert \\ 3$^{e}$ Bachelor Computerwetenschappen - Elektrotechniek}
\date{\today}
% 13 mei 2007

\begin{document}

\maketitle

\section{Een logisch circuit}
\subsection{Variabelen en constraints}
\begin{verbatim}
	Name: In1, domain: (0..1)
	Name: In2, domain: (0..1)
	Name: In3, domain: (0..1)
	Name: Tussen1, domain: (0..1)
	Name: Tussen2, domain: (0..1)
	Name: Uit, domain: (0..1)
	Constraint: In1#=1
	Constraint: In2#=0
	Constraint: In3#=1
	Constraint: min(In1,In2) #= Tussen1
	Constraint: In3 #\= Tussen2
	Constraint: max(Tussen1,Tussen2) #= Uit
\end{verbatim}

\subsection{Uitvoer}
\begin{verbatim}
	Backtracks: 0
	Runtime: 0.0s
	[In1,In2,In3,Tussen1,Tussen2,Uit] = [1,0,1,0,0,0]
\end{verbatim}

\subsection{Besluit}
De bekomen uitvoer komt overeen met de verwachte waarde.

\section{Ge\"{i}ndexeerde variabelen}
\subsection{Variabelen en constraints}
Aangezien R2 niet gebruikt wordt, wordt er ook geen variabele voor aangemaakt. Ook kunnen J2 en K2 weggelaten worden aangezien deze toch altijd gelijk zijn aan Q1 en R1.

\begin{verbatim}
	Name: In(i), i=1..3, domain: 0..1
	Name: J1(i), i=1..3, domain: 0..1
	Name: K1(i), i=1..3, domain: 0..1
	Name: Q1(i), i=1..3, domain: 0..1
	Name: R1(i), i=1..3, domain: 0..1
	Name: Q2(i), i=1..3, domain: 0..1
	Constraint: In(i)=1, range: i>0/\i<4
	Constraint: J1(i)=In(i), range: i>0/\i<4
	Constraint: K1(i)\=In(i), range: i>0/\i<4
	Constraint: R1(i)\=Q1(i), range: i>0/\i<4
	Constraint: J1(i)=0 /\ K1(i)=0 => Q1(i+1)=Q1(i), range: i>0/\i<3
	Constraint: J1(i)\=K1(i) => Q1(i+1)=J1(i), range: i>0/\i<3
	Constraint: J1(i)=1 /\ K1(i)=1 => Q1(i+1)\=Q1(i), range: i>0/\i<3
	Constraint: Q1(i)=0 /\ R1(i)=0 => Q2(i+1)=Q2(i), range: i>0/\i<3
	Constraint: Q1(i)\=R1(i) => Q2(i+1)=Q1(i), range: i>0/\i<3
	Constraint: Q1(i)=1 /\ R1(i)=1 => Q2(i+1)\=Q2(i), range: i>0/\i<3
	Constraint: Q1(i)=0, range: i=1
	Constraint: Q2(i)=0, range: i=1
\end{verbatim}

\subsection{Uitvoer}
\begin{verbatim}
	Backtracks: 0
	Runtime: 0.01s
	[In,J1,K1,Q1,R1,Q2] = [[1,1,1],[1,1,1],[0,0,0],[0,1,1],[1,0,0],[0,0,1]]
\end{verbatim}

\section{Sudoku}
\subsection{Variabelen}
We gebruiken maar \'{e}\'{e}n variabele, namelijk die die alle elementen voorsteld.

\begin{verbatim}
	Name: EL(i), i=0..80, domain: 1..9
\end{verbatim}

\subsection{Constraints}
Er zijn drie beperkingen bij het oplossen van een sudoku. Deze worden hieronder verder besproken en er wordt een constraint gekozen die kan gebruikt worden in het programma.

\subsubsection{Rij beperking}
Op een rij mogen geen twee dezelfde waarden voorkomen. Aangezien de deling door 9 aangeeft op welke rij het element zich bevindt, kunnen we dit makkelijk oplossen door de onderstaande constraint op te leggen.

\begin{verbatim}
	Constraint: EL(i)\=EL(j), range: i/9=j/9 /\ i\=j
\end{verbatim}

\subsubsection{Kolom beperking}
Op een kolom mogen geen twee dezelfde waarden voorkomen. Aangezien de modulo 9 bewerking aangeeft op welke kolom het element zich bevindt, kunnen we dit makkelijk oplossen door de onderstaande constraint op te leggen.

\begin{verbatim}
	Constraint: EL(i)\=EL(j), range: i mod 9 = j mod 9 /\ i \= j
\end{verbatim}


\subsubsection{3x3 vierkant beperking}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{c|c|c|c||c|c|c||c|c|c|}
		\mc{1}{c||}{} & \mc{3}{|c||}{\bfseries Kolom 0 } & \mc{3}{|c||}{\bfseries Kolom 1 } & \mc{3}{|c|}{\bfseries Kolom 2} \\
		\hline
		\hline
		\mc{1}{c||}{} 			& \mc{1}{|c|}{0}  & \mc{1}{|c|}{1}  & \mc{1}{|c||}{2}  & \mc{1}{|c|}{3}  & \mc{1}{|c|}{4}  & \mc{1}{|c||}{5}  & \mc{1}{|c|}{6}  & \mc{1}{|c|}{7}  & \mc{1}{|c|}{8}  \\
		\cline{2-10}
		\mc{1}{c||}{\bfseries Rij 0} 	& \mc{1}{|c|}{9}  & \mc{1}{|c|}{10} & \mc{1}{|c||}{11} & \mc{1}{|c|}{12} & \mc{1}{|c|}{13} & \mc{1}{|c||}{14} & \mc{1}{|c|}{15} & \mc{1}{|c|}{16} & \mc{1}{|c|}{17} \\
		\cline{2-10}
		\mc{1}{c||}{} 			& \mc{1}{|c|}{18} & \mc{1}{|c|}{19} & \mc{1}{|c||}{20} & \mc{1}{|c|}{21} & \mc{1}{|c|}{22} & \mc{1}{|c||}{23} & \mc{1}{|c|}{24} & \mc{1}{|c|}{25} & \mc{1}{|c|}{26} \\
		\hline
		\hline
		\mc{1}{c||}{} 			& \mc{1}{|c|}{27} & \mc{1}{|c|}{28} & \mc{1}{|c||}{29} & \mc{1}{|c|}{30} & \mc{1}{|c|}{31} & \mc{1}{|c||}{32} & \mc{1}{|c|}{33} & \mc{1}{|c|}{34} & \mc{1}{|c|}{35} \\
		\cline{2-10}
		\mc{1}{c||}{\bfseries Rij 1} 	& \mc{1}{|c|}{36} & \mc{1}{|c|}{37} & \mc{1}{|c||}{38} & \mc{1}{|c|}{39} & \mc{1}{|c|}{40} & \mc{1}{|c||}{41} & \mc{1}{|c|}{42} & \mc{1}{|c|}{43} & \mc{1}{|c|}{44} \\
		\cline{2-10}
		\mc{1}{c||}{} 			& \mc{1}{|c|}{45} & \mc{1}{|c|}{46} & \mc{1}{|c||}{47} & \mc{1}{|c|}{48} & \mc{1}{|c|}{49} & \mc{1}{|c||}{50} & \mc{1}{|c|}{51} & \mc{1}{|c|}{52} & \mc{1}{|c|}{53} \\
		\hline
		\hline
		\mc{1}{c||}{} 			& \mc{1}{|c|}{54} & \mc{1}{|c|}{55} & \mc{1}{|c||}{56} & \mc{1}{|c|}{57} & \mc{1}{|c|}{58} & \mc{1}{|c||}{59} & \mc{1}{|c|}{60} & \mc{1}{|c|}{61} & \mc{1}{|c|}{62} \\
		\cline{2-10}
		\mc{1}{c||}{\bfseries Rij 2} 	& \mc{1}{|c|}{63} & \mc{1}{|c|}{64} & \mc{1}{|c||}{65} & \mc{1}{|c|}{66} & \mc{1}{|c|}{67} & \mc{1}{|c||}{68} & \mc{1}{|c|}{69} & \mc{1}{|c|}{70} & \mc{1}{|c|}{71} \\
		\cline{2-10}
		\mc{1}{c||}{} 			& \mc{1}{|c|}{72} & \mc{1}{|c|}{73} & \mc{1}{|c||}{74} & \mc{1}{|c|}{75} & \mc{1}{|c|}{76} & \mc{1}{|c||}{77} & \mc{1}{|c|}{78} & \mc{1}{|c|}{79} & \mc{1}{|c|}{80} \\
		\hline
		\end{tabular}
	\end{center}
	\caption{Voorstelling grote rijen en grote kolommen.}
	\label{vierkanten_tabel}
\end{table}

Het 9x9 veld van de sudoku wordt verdeeld in negen aparte 3x3 vierkanten. In een vierkant mogen geen twee dezelfde waarden voorkomen. Om hiervoor een constraint te vinden moeten we het speelveld op delen in drie grote rijen en drie grote kolommen, zoals aangegeven in tabel \ref{vierkanten_tabel}. Als we dit doen kunnen we makkelijk bepalen tot welke grote rij een element behoort door te delen door 27. Om te bepalen wat de grote kolom is waartoe een element behoort, voeren we eerst de modulo 9 bewerking uit en delen dan door 3. Deze twee samen geven dan aan tot welk vierkant het element behoort. Zo bekomen we de onderstaande constraint.

\begin{verbatim}
	Constraint: EL(i)\=EL(j), range: i/27=j/27 /\ (i mod 9)/3=(j mod 9)/3 /\ i \= j
\end{verbatim}

\subsection{Oplossen via de \texttt{leftmost} methode}
\subsubsection{Resultaten}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{c||c|c|c|c|c|}
			 	& Totale 	& Totaal \# 	& \# Oplossingen 	& Maximaal \#\\
			 	& tijd (s)	& backtracks	&			& backtracks\\
			\hline
			\hline
			Easy 1	& 0.11		& 0		& 1			& 0\\
			\hline
			Easy 2	& 0.11		& 0		& 1			& 0\\
			\hline
			Easy 3	& 0.11		& 0		& 1			& 0\\
			\hline
			Hard 1	& 0.14		& 88		& 37			& 33\\
			\hline
			Hard 2	& 0.10		& 35		& 1			& 35\\
			\hline
			Hard 3	& 0.10		& 8		& 1			& 8\\
			\hline
		\end{tabular}
	\end{center}
	\caption{Resultaten bij het verwerken met de \texttt{leftmost} methode.}
	\label{leftmost_results}
\end{table}

Eerst bekijken we het oplossen van de verschillende sudoku's waar we gebruik maken van de \texttt{leftmost} methode en de bovenstaande constraints. In tabel \ref{leftmost_results} staan vier waarden voor elke sudoku, namelijk de totale tijd die er nodig was om het op te lossen, het totaal aantal backtracks, het aantal oplossingen en de maximaal aantal backtracks voor \'{e}\'{e}n oplossing. Deze laatste waarde stelt dus het grootste aantal backtracks die is waargenomen om \'{e}\'{e}n oplossing te vinden voor het probleem.

\subsubsection{Besluit}
Het valt direct op dat bij de makkelijke sudoku's er veel minder backtracks moeten gebeuren dan bij de moeilijke sudoku's. Dit heeft te maken met de complexiteit van het probleem. Hoe meer waarden al vast staan, hoe minder vrijheidsgraden er moeten opgelost worden en hoe minder foute veronderstellingen er gemaakt kunnen worden. Dit zorgt dus voor minder backtracking.

\subsection{Oplossen via de \texttt{first-fail+constraint count} methode}
\subsubsection{Resultaten}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{c||c|c|c|c|c|}
			 	& Totale 	& Totaal \# 	& \# Oplossingen 	& Maximaal \#\\
			 	& tijd (s)	& backtracks	&			& backtracks\\
			\hline
			\hline
			Easy 1	& 0.10		& 0		& 1			& 0\\
			\hline
			Easy 2	& 0.10		& 0		& 1			& 0\\
			\hline
			Easy 3	& 0.11		& 0		& 1			& 0\\
			\hline
			Hard 1	& 0.13		& 37		& 37			& 10\\
			\hline
			Hard 2	& 0.09		& 11		& 1			& 11\\
			\hline
			Hard 3	& 0.11		& 3		& 1			& 3\\
			\hline
		\end{tabular}
	\end{center}
	\caption{Resultaten bij het verwerken met de \texttt{first-fail+constraint count} methode.}
	\label{ffcc_results}
\end{table}

\subsubsection{Vergelijking met de \texttt{leftmost} methode}
In tabel \ref{ffcc_results} kunnen we de resultaten van de \texttt{first-fail+constraint count} methode bekijken voor de verschillende sudoku's. Als we deze tabel vergelijken met die van de \texttt{leftmost} methode (tabel \ref{leftmost_results}), valt direct op dat het aantal backtracks sterk gedaald is voor de \texttt{first-fail+constraint count} methode. Dit heeft te maken met de manier waarop het probleem wordt aangepakt. Bij de \texttt{leftmost} methode wordt de volgorde van oplossen van variabelen bepaald door de volgorde waarin de variabelen gedefin\"{i}eerd zijn. Dit heeft als gevolg dat niet altijd de beste keuze gemaakt wordt. Bij de \texttt{first-fail+constraint count} wordt de volgende variabele gekozen aan de hand van het domein. De variabele met het kleinste domein wordt eerst opgelost, waardoor de domeinen van de overige variabelen ook kan verkleinen als ze zicn bevoorbeeld in dezelde rij, dezelfde kolom of hetzelfde vierkant bevinden.

\subsection{\textit{``Two out of three''}-regel}
\subsubsection{Extra constraints}
Bij het toepassen van de \textit{``Two out of three''}-regel gaat men kijken of een getal al in twee rijen van een grote rij (cfr. tabel \ref{vierkanten_tabel}) aanwezig is. Dit betekent ook dat dit getal al in twee verschillende 3x3 vierkanten voorkomt in die grote rij. Daaruit kan men besluiten dat dit getal in het overgebleven 3x3 vierkant enkel op drie plaatsen kan staan, namelijk de drie elementen in het 3x3 vierkant die zich bevinden op de kleine rij die het getal nog niet bevat.

\begin{table}[h]
	\begin{center}
		\begin{tabular}{|c|c|c||c|c|c||c|c|c|}
			\hline
			 . & $a$ & . & . & . & . & . & . & . \\ 
			\hline
			 . & . & . & \mc{1}{>{\columncolor{tcA}}c}{\bfseries\color{white} $a$? } & \mc{1}{>{\columncolor{tcA}}c}{\bfseries\color{white} $a$? } & \mc{1}{>{\columncolor{tcA}}c}{\bfseries\color{white} $a$? } & . & . & . \\ 
			\hline
			 . & . & . & . & . & . & . & . & $a$ \\
			\hline
		\end{tabular}
	\end{center}
	\caption{Voorstelling van de \textit{``Two out of three''}-regel in \'{e}\'{e}n grote rij.}
	\label{2out3_representation}
\end{table}

In tabel \ref{2out3_representation} wordt een grafische voorstelling gegeven van de \textit{``Two out of three''}-regel. Het tweede element op de eerste rij is gelijk aan het getal $a$, evenals het negende element op de derde rij. Dit betekent dus dat in de bovenste en de onderste rij het getal $a$ niet meer mag voorkomen. Daarnaast mag het getal $a$ ook niet meer voorkomen in het linkse en het rechtse 3x3 vierkant. Daardoor wordt de positie van het getal $a$ in het middelste vierkant beperkt tot de drie blauw gekleurde vakjes. \\
\\
Om deze strategie in te bouwen in ons programma, hebben we drie constraints nodig. Voor elke van de drie mogelijke posities van het getal. De range die we nodig hebben is voor elke constraint hetzelfde op \'{e}\'{e}n term na die de positie van het het gezochte element bepaald. Deze range bestaat zelf uit drie delen:
\begin{itemize}
	\item Als eerste moeten we bepalen dat de drie elementen in \'{e}\'{e}n grote rij zitten. Dit kunnen we doen door gebruik te maken van de eerder bepaalde regel dat delen door 27 bepaald in welke grote rij een element zich bevindt.
	\begin{verbatim}
		i/27 = j/27 /\ j/27 = k/27
	\end{verbatim}
	\item Daarnaast moeten we ook bepalen dat de drie elementen in verschillende grote kolommen zitten. Dit geeft, in combinatie met het vorige deel, aan dat de drie elementen zin in drie verschillende 3x3 vierkanten bevinden. Ook hier kunnen we gebruik maken van de eerder bepaalde regel dat door de modulo 9 bewerking op het element en dan te delen door 3 we de grote kolom krijgen van het element.
	\begin{verbatim}
		(i mod 9)/3 \= (j mod 9)/3 
		/\ (j mod 9)/3 \= (k mod 9)/3
		/\ (i mod 9)/3 \= (k mod 9)/3 
	\end{verbatim}
	\item Als laatste moeten we ook bepalen dat de drie elementen zich op drie verschillende rijen bevinden. Ook dit hebben we al eens ge\"{i}mplementeerd.
	\begin{verbatim}
		i/9 \= j/9 /\ j/9 \= k/9 /\ i/9 \= k/9
	\end{verbatim}
\end{itemize}
Als we deze drie delen samen nemen krijgen we de volgende basis range voor onze constraints.
\begin{verbatim}
	basis range: i/27 = j/27 /\ j/27 = k/27
	/\ (i mod 9)/3 \= (j mod 9)/3 
	/\ (j mod 9)/3 \= (k mod 9)/3
	/\ (i mod 9)/3 \= (k mod 9)/3
	/\ i/9 \= j/9 /\ j/9 \= k/9 /\ i/9 \= k/9
\end{verbatim}

Om de constraints zelf te bepalen moeten we drie verschillende gevallen bekijken. Deze drie verschillende gevallen worden bepaald door welk element van de drie juist gezocht wordt. Dit zal er ook voor zorgen dat we uiteindelijk drie verschillende constraints zullen moeten toevoegen.

\subsubsection{Het linkse element}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{|c|c|c||c|c|c||c|c|c|}
			\hline
			 . & $EL(i)=a$ & . & . & . & . & . & . & . \\ 
			\hline
			 . & . & . & \mc{1}{>{\columncolor{tcA}}c}{\bfseries\color{white} $EL(k)=a$ } & $EL(k+1)$ & $EL(k+2)$ & . & . & . \\ 
			\hline
			 . & . & . & . & . & . & . & . & $EL(j)=a$ \\
			\hline
		\end{tabular}
	\end{center}
	\caption{Situatie waarin het gezochte element ($EL(k)$) het linkse element is.}
	\label{2out3_left}
\end{table}

Uit tabel \ref{2out3_left} blijkt duidelijk dat we moeten bepalen of het gezochte element zich bevindt in het linkse vakje. Hiervoor moeten we de volgende term toevoegen aan onze range.
\begin{verbatim}
	range: basis /\ k mod 3 = 0
\end{verbatim}

Om dan te bepalen dat element k effectief gelijk is aan het getal $a$, moeten we eerst bepalen dat element k+1 en element k+2 niet gelijk zijn aan $a$. Hiervoor kunnen we de volgende constraint gebruiken.
\begin{verbatim}
	Constraint: EL(i) = EL(j) /\ EL(k+1) \= EL(i) /\ EL(k+2) \= EL(i)
	    => EL(i) = EL(k)
\end{verbatim}

\subsubsection{Het middelste element}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{|c|c|c||c|c|c||c|c|c|}
			\hline
			 . & $EL(i)=a$ & . & . & . & . & . & . & . \\ 
			\hline
			 . & . & . & $EL(k-1)$ & \mc{1}{>{\columncolor{tcA}}c}{\bfseries\color{white} $EL(k)=a$ } & $EL(k+1)$ & . & . & . \\ 
			\hline
			 . & . & . & . & . & . & . & . & $EL(j)=a$ \\
			\hline
		\end{tabular}
	\end{center}
	\caption{Situatie waarin het gezochte element ($EL(k)$) het middelste element is.}
	\label{2out3_middle}
\end{table}

Een soortgelijke redenering als bij het linkse element en tabel \ref{2out3_middle} levert de volgende aanpassing op de basis range en de tweede constraint
\begin{verbatim}
	range: basis /\ k mod 3 = 1
	Constraint: EL(i) = EL(j) /\ EL(k-1) \= EL(i) /\ EL(k+1) \= EL(i)
	    => EL(i) = EL(k)
\end{verbatim}

\subsubsection{Het rechtse element}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{|c|c|c||c|c|c||c|c|c|}
			\hline
			 . & $EL(i)=a$ & . & . & . & . & . & . & . \\ 
			\hline
			 . & . & . & $EL(k-2)$ & $EL(k-1)$ & \mc{1}{>{\columncolor{tcA}}c}{\bfseries\color{white} $EL(k)=a$ } & . & . & . \\ 
			\hline
			 . & . & . & . & . & . & . & . & $EL(j)=a$ \\
			\hline
		\end{tabular}
	\end{center}
	\caption{Situatie waarin het gezochte element ($EL(k)$) het rechtse element is.}
	\label{2out3_right}
\end{table}

Een soortgelijke redenering als bij het linkse en het middelste element en tabel \ref{2out3_right} levert de volgende aanpassing op de basis range en de tweede constraint
\begin{verbatim}
	range: basis /\ k mod 3 = 2
	Constraint: EL(i) = EL(j) /\ EL(k-2) \= EL(i) /\ EL(k-1) \= EL(i)
	    => EL(i) = EL(k)
\end{verbatim}

\subsubsection{Uiteindelijk toegevoegde constraints}
\begin{verbatim}
	Constraint: EL(i) = EL(j) /\ EL(k+1) \= EL(i) /\ EL(k+2) \= EL(i)
	    => EL(i) = EL(k)
	range: i/27 = j/27 /\ j/27 = k/27
	    /\ (i mod 9)/3 \= (j mod 9)/3 
	    /\ (j mod 9)/3 \= (k mod 9)/3
	    /\ (i mod 9)/3 \= (k mod 9)/3
	    /\ i/9 \= j/9 /\ j/9 \= k/9 /\ i/9 \= k/9 
	    /\ k mod 3 = 0
	
	Constraint: EL(i) = EL(j) /\ EL(k-1) \= EL(i) /\ EL(k+1) \= EL(i)
	    => EL(i) = EL(k)
	range: i/27 = j/27 /\ j/27 = k/27
	    /\ (i mod 9)/3 \= (j mod 9)/3 
	    /\ (j mod 9)/3 \= (k mod 9)/3
	    /\ (i mod 9)/3 \= (k mod 9)/3
	    /\ i/9 \= j/9 /\ j/9 \= k/9 /\ i/9 \= k/9 
	    /\ k mod 3 = 1
	
	Constraint: EL(i) = EL(j) /\ EL(k-2) \= EL(i) /\ EL(k-1) \= EL(i)
	    => EL(i) = EL(k)
	range: i/27 = j/27 /\ j/27 = k/27
	    /\ (i mod 9)/3 \= (j mod 9)/3 
	    /\ (j mod 9)/3 \= (k mod 9)/3
	    /\ (i mod 9)/3 \= (k mod 9)/3
	    /\ i/9 \= j/9 /\ j/9 \= k/9 /\ i/9 \= k/9 
	    /\ k mod 3 = 2
\end{verbatim}

\subsection{Oplossen via de \texttt{leftmost} methode}
\subsubsection{Resultaten}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{c||c|c|c|c|c|}
			 	& Totale 	& Totaal \# 	& \# Oplossingen 	& Maximaal \#\\
			 	& tijd (s)	& backtracks	&			& backtracks\\
			\hline
			\hline
			Easy 1	& 16.62		& 0		& 1			& 0\\
			\hline
			Easy 2	& 17.10		& 0		& 1			& 0\\
			\hline
			Easy 3	& 16.91		& 0		& 1			& 0\\
			\hline
			Hard 1	& 17.20		& 27		& 37			& 11\\
			\hline
			Hard 2	& 16.85		& 3		& 1			& 3\\
			\hline
			Hard 3	& 16.96		& 3		& 1			& 3\\
			\hline
		\end{tabular}
	\end{center}
	\caption{Resultaten bij het verwerken met de \texttt{leftmost} methode met de \textit{``Two out of three''}-regel.}
	\label{2out3_leftmost_results}
\end{table}

\subsubsection{Waarneming}
Wat direct opvalt uit tabel \ref{2out3_leftmost_results} is dat de tijd die nodig is om het probleem op te lossen veel groter is dan wanneer we niet gebruik maken van de \textit{``Two out of three''}-regel. Daarnaast valt het wel op dat het aantal backtracks gedaalt is. Dit is zeer duidelijk voor de eerste moeilijke sudoku. Daar is het aantal backtracks gedaalt van 88 tot 27.

\subsection{Oplossen via de \texttt{first-fail+constraint count} methode}
\subsubsection{Resultaten}
\begin{table}[h]
	\begin{center}
		\begin{tabular}{c||c|c|c|c|c|}
			 	& Totale 	& Totaal \# 	& \# Oplossingen 	& Maximaal \#\\
			 	& tijd (s)	& backtracks	&			& backtracks\\
			\hline
			\hline
			Easy 1	& 16.68		& 0		& 1			& 0\\
			\hline
			Easy 2	& 16.64		& 0		& 1			& 0\\
			\hline
			Easy 3	& 16.64		& 0		& 1			& 0\\
			\hline
			Hard 1	& 17.22		& 23		& 37			& 12\\
			\hline
			Hard 2	& 17.00		& 7		& 1			& 7\\
			\hline
			Hard 3	& 17.17		& 6		& 1			& 6\\
			\hline
		\end{tabular}
	\end{center}
	\caption{Resultaten bij het verwerken met de \texttt{first-fail+constraint count} methode met de \textit{``Two out of three''}-regel.}
	\label{2out3_ffcc_results}
\end{table}

\subsubsection{Waarneming}
Ook hier valt het duidelijk op uit tabel \ref{2out3_ffcc_results} dat de tijden spectaculair zijn toegenomen. En ook hier kunnen we zien dat het aantal backtracks gedaald is, al geldt dit niet voor elke sudoku.

\subsection{Besluit}
Het eerste dat duidelijk opvalt uit de resultaten, is de spectaculaire stijging van de benodigde verwerkingstijd. Dit heeft alles te maken met de ingewikkelde toegevoegde constraints. Hierdoor moeten veel meer controle stappen doorlopen worden, die het proces zwaar vertragen. Tussen de \texttt{first-fail+constraint count} methode en de \texttt{leftmost} methode zelf is er weinig verschil te merken in de verwerkingstijd.

Bij het aantal benodigde backtracks is voor beide methodes een zelfde daling waar te nemen. Deze daling is ook te verklaren door de extra constraints. Doordat er meer constraints zijn, zullen de mogelijke waarden in elk element ook mee beperkt worden, waardoor er minder fouten voorkomen. 

Uit het gevolg op de verwerkingstijd blijkt dat het niet interessant is om de \textit{``Two out of three''}-regel te implementeren voor het oplossen van sudoku's op de pc. Dit komt voornamelijk door de drie eerste constraints die het probleem al zodanig definieren dat het programma er al genoeg aan heeft. Als er nog meer ingewikkelde constraints worden toegevoegd, zal dit zorgen voor vertragingen aangezien die ook nog eens, onnodig, verwerkt moeten worden.

\end{document}