\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}

\usepackage{anysize}
\marginsize{1cm}{1cm}{0cm}{0cm}

\title{Présentation de Sudokusc}
\author{}
\date{}

\sloppy

\begin{document}

\maketitle

\thispagestyle{empty}

On souhaite concevoir Sudokusc, un programme de résolution des grilles de Sudoku. Pour ce faire, il nous faut trouver un algorithme de résolution, choisir un langage pour l'implémenter, rédiger le code et tester le programme.

\section{L'algorithme}

L'algorithme doit être :

\begin{itemize}
\item Simple à expliquer à un ordinateur (répétition d'étapes simples un grand nombre de fois)~;
\item Rigoureux et précis (pas question de laisser des zones d'ombre)~;
\item Exhaustif (résolution de toutes les grilles)~;
\item Rapide (autant que possible)~;
\end{itemize}

J'ai choisi un algorithme {\em récursif} : on explore l'arbre des solutions possibles pour la grille en complétant chaque case au hasard parmi les chiffres qui peuvent légalement s'y trouver, et on recommence à partir des grilles ainsi obtenues. Quand on est coincé, on fait marche arrière. Quand la grille est pleine, on a gagné !

\section{Le langage}

On doit rédiger cet algorithme dans un langage de programmation (on obtient le {\em code}) et la machine le transformera en instructions qu'elle peut comprendre.

Un langage est dit {\em compilé} s'il traduit le code en instructions une seule fois, et {\em interprété} s'il le fait à chaque fois. Les langages compilés sont généralement plus rapides (pas besoin de recommencer la même chose à chaque fois) mais il faut compiler pour chaque machine.

Un langage est dit {\em haut niveau} s'il est proche du langage humain, et {\em bas niveau} s'il est proche de celui de l'ordinateur. Les langages haut niveau ont une syntaxe plus naturelle mais moins rigoureuse, plus concise mais plus désordonnée, ils sont moins rapides mais plus simples, plus indépendants de la machine mais permettent de faire moins de choses.

J'ai choisi le langage C. Il est bas niveau, compilé, très rapide, très rigoureux (mais inclut peu de "garde-fous"), normalisé ANSI et ISO, vieux (1972, normalisé en 89 et a évolué depuis), très basique dans sa syntaxe, la base de quelques « extensions » (C++, etc.), {\em portable} (indépendant de la machine) si l'on fait attention à ce que l'on fait, et déjà très utilisé.

Les pointeurs sont {\em primordiaux} en C (et Sudokusc s'en sert beaucoup), ce sont des adresses mémoire pointant vers une autre adresse.

\section{Le programme}

Le programme obtenu est court (6000 caractères dont environ 4000 de commentaires non intégrés au résultat final), rapide (résout un Sudoku en quelques millisecondes), fonctionnel en dimension N (supersudoku, etc.), libre (sous GNU GPL), mais pas encore très convivial (terminal).

\vfill

\begin{center}

\tiny{

{\em Copyright \copyright 2006 Antoine Amarilli. Cette création est mise à disposition selon le Contrat Attribution-ShareAlike 2.0 France disponible en ligne \verb?http://creativecommons.org/licenses/by-sa/2.0/fr/? ou par courrier postal à Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.}

}

\end{center}


\end{document}
