Mathématiques du sudoku

thumb|Grille de sudoku classique thumb|Variante du sudoku basée sur des comparaisons entre les cases thumb|Sudoku classique avec une contrainte supplémentaire sur les diagonales Le jeu du sudoku consiste à compléter une grille carrée divisée en N régions de N cases, en partie remplie avec des chiffres, de façon que dans chaque ligne, chaque colonne et chaque région les chiffres de 1 à N apparaissent une et une seule fois. Une analyse mathématique du sudoku permet de découvrir les différentes propriétés et problèmes qui se cachent derrière ce jeu et ses variantes. L'analyse mathématique du sudoku se divise en deux grandes parties : l'analyse des propriétés des grilles complètes et l'analyse de la résolution d'une grille. L'analyse des grilles s'est en grande partie focalisée sur l'énumération des solutions possibles pour différentes variantes du jeu. L'étude de la résolution se concentre sur les valeurs initiales de la grille et sur les étapes qui mènent à la grille complète. Ces techniques font appel à plusieurs disciplines : analyse combinatoire, algorithmique, théorie des groupes ainsi que la programmation puisque l'ordinateur permet de rapidement résoudre les grilles. Il y a un grand nombre de variantes du sudoku, en général caractérisées par la taille de la grille (le paramètre N) et la forme des régions. Les sudokus classiques ont un N égal à 9 avec des régions de 3 × 3 cases. Un sudoku rectangulaire possède des régions rectangulaires d'une taille L × C où L est le nombre de lignes et C le nombre de colonnes. Un tel sudoku, avec une taille de L × 1 (ou 1 × C), devient un carré latin puisque la région est une ligne ou une colonne unique. Des variantes plus complexes existent comme celles avec des régions découpées de manière irrégulière (Nanpure), avec des contraintes supplémentaires (Samunamupure ou Killer Sudoku, respect de l'unicité sur les diagonales avec le Kokonotsu, contraintes sur l'ordre des éléments avec le Greater-Than) ou des assemblages de plusieurs grilles (Samurai, Sudoku en 3D).