les mathematiques du Sudoku

Qu’y a-t-il derrière les grilles de Sudoku ?

ACHMIT ANAS

TIPE
travail d’initiative personnelle encadré

June 4, 2023
introduction et definitions

▶ Un sudoku C’est un tableau de 9 lignes par 9 colonnes (81 cases donc au total),
qu’il faut remplir de chiffres allant de 1 à 9, avec les contraintes suivantes :
– dans chaque ligne et dans chaque colonne doivent figurer les 9 chiffres 1, 2, ...,
9, une seule fois chacun (avec cette seule exigence, le tableau est appelé carré
latin depuis Euler) ;
– mais, de plus, dans chacun des 9 blocs 3 par 3 constitutifs du tableau général
doivent figurer les 9 chiffres 1, 2, ..., 9.
▶ Une analyse mathématique permet de découvrir les différentes propriétés et
problèmes qui se cachent derrière ce jeux et ces variantes.
plan d’étude

1-étude théorique

2-methode de resolution

3-resolution phyton

ressources
Bullet Points

▶ Lorem ipsum dolor sit amet, consectetur adipiscing elit

▶ Aliquam blandit faucibus nisi, sit amet dapibus enim tempus eu
▶ Nulla commodo, erat quis gravida posuere, elit lacus lobortis est, quis porttitor
odio mauris at libero
▶ Nam cursus est eget velit posuere pellentesque
▶ Vestibulum faucibus velit a augue condimentum quis convallis nulla gravida
Blocks of Highlighted Text

In this slide, some important text will be highlighted because it’s important. Please,
don’t abuse it.
Block
Sample text

Alertblock
Sample text in red box

Examples
Sample text in green box. The title of the block is “Examples”.
Multiple Columns

Heading Lorem ipsum dolor sit amet, consectetur

1. Statement adipiscing elit. Integer lectus nisl, ultricies
in feugiat rutrum, porttitor sit amet augue.
2. Explanation Aliquam ut tortor mauris. Sed volutpat
3. Example ante purus, quis accumsan dolor.
nombre de grilles possible
Theorem

Theorem (Mass–energy equivalence)

E = mc 2
Figure

Uncomment the code on this slide to include your own image from the same directory
as the template .TeX file.
Citation

An example of the \cite command to cite within the presentation:

This statement requires citation [Smith, 2012].

representation matricielle

▶ representation matricielle :
la grille du Sudoku est transformée en une matrice carrée d’ordre 9

figure 1: grille de sudoku figure 2 :regions des sudoku

representation matricielle

la matrice associée au jeux précédent est la suite :

1 0 0 0 0 0 0 0 6
 
0 0 6 0 2 0 7 0 0
 
7 8 9 4 5 0 1 0 3
 
0 0 0 8 0 7 0 0 4
 
0
A= 0 0 0 3 0 0 0 0

0 9 0 0 0 4 2 0 1
 
3 1 2 9 7 0 0 4 0
 
0 4 0 0 1 2 0 7 8
9 0 8 0 0 0 0 0 0
méthode de recherche systematique

principe du backtracking :
Les cases vides sont d’abord identifiées puis la première case vide est remplie par un 1.
Si cette valeur convient, c’est-à-dire si elle obéit aux différentes règles du jeu, alors la
case vide suivante est testée, sinon on vérifie si 2 convient, puis 3, etc....
Dès qu’une incompatibilité intervient, il est alors nécessaire de revenir en arrière et
d’augmenter le chiffre précédent. Ce retour en arrière a lieu tant qu’il subsiste une
incompatibilité concernant le choix d’un chiffre. Cette méthode permet de tester
toutes les configurations possibles et finit donc par trouver la bonne solution. Une
façon rapide d’écrire le programme consiste à utiliser une récursivité.
test de validaté

test de validité:
notre algorithm sera basé sur un test de validité pour les entier choisis ,pour une case
quelconque (i,j).
pour testé la validité d’un chiffre k ∈ [|1, 9|] dans une case vide (i,j) ( modelisé par un
z éro dans la matrice ) , il faut suivre ce qui suit :
un test sur les lignes ∀p ∈ [|1, 9|], A(i, p) ̸= k
un test sur les colonnes : ∀p ∈ [|1, 9|], A(p, j) ̸= k
un test sur la region : on peut trouvé facillement que les coordonées du region ou ce
trouve la case(i,j) verifient iB = ⌈ 3i ⌉ et jB = ⌈ 3j ⌉ . Enfin, les coefficients des cases
premier de chaque region sont ia = 3iB et ja = 3jB : alors k est valable si:
∀p ∈ [|0, 2|], A(ia + p, ja + p) ̸= k
Le code
exemple d’éxecution

1, 0, 0, 0, 0, 0, 0, 0, 6 1, 2, 3, 7, 8, 9, 4, 5, 6
   

 0, 0, 6, 0, 2, 0, 7, 0, 0 


 4, 5, 6, 1, 2, 3, 7, 8, 9 


 7, 8, 9, 4, 5, 0, 1, 0, 3 


 7, 8, 9, 4, 5, 6, 1, 2, 3 


 0, 0, 0, 8, 0, 7, 0, 0, 4 


 2, 3, 1, 8, 9, 7, 5, 6, 4 


 0, 0, 0, 0, 3, 0, 0, 0, 0 
 −→ 
 5, 6, 4, 2, 3, 1, 8, 9, 7 


 0, 9, 0, 0, 0, 4, 2, 0, 1 


 8, 9, 7, 5, 6, 4, 2, 3, 1 


 3, 1, 2, 9, 7, 0, 0, 4, 0 


 3, 1, 2, 9, 7, 8, 6, 4, 5 

 0, 4, 0, 0, 1, 2, 0, 7, 8   6, 4, 5, 3, 1, 2, 9, 7, 8 
9, 0, 8, 0, 0, 0, 0, 0, 0 9, 7, 8, 6, 4, 5, 3, 1, 2
l’entré la sortie
complexité
The End
References

JP. Zanotti (2012)

[Link]
Version du 6/3/2019