Algorithmes avancés
2024 / 2025 Benmazouz Nabil 1
Algorithmes avancés
I B
E G
H
K
F
J C
D A
2024 / 2025 Benmazouz Nabil 2
Algorithmes avancés
K
I B
E G
H
F
J C
D A D
F
H E B
K
I G J
A C
2024 / 2025 Benmazouz Nabil 3
Algorithmes avancés
2024 / 2025 Benmazouz Nabil 4
Algorithmes avancés
2024 / 2025 Benmazouz Nabil 5
Algorithmes avancés
8 BackTracking
Introduction
Définition
Le retour sur trace (backtracking) est une famille d'algorithmes qui
consistent à revenir en arrière sur des décisions prises afin de sortir d'un
blocage.
2024 / 2025 Benmazouz Nabil 6
Algorithmes avancés
8 BackTracking
Sudoku
Définition
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.
2024 / 2025 Benmazouz Nabil 7
Algorithmes avancés
8 BackTracking
Sudoku
Exemple
2024 / 2025 Benmazouz Nabil 8
Algorithmes avancés
8 BackTracking
Sudoku
Exemple
Col
2024 / 2025 Benmazouz Nabil 9
Algorithmes avancés
8 BackTracking
Sudoku
Exemple
Row
2024 / 2025 Benmazouz Nabil 10
Algorithmes avancés
8 BackTracking
Sudoku
Exemple
Box
2024 / 2025 Benmazouz Nabil 11
Algorithmes avancés
8 BackTracking
Sudoku
Exemple
août 2013, Gary McGuire, Bastian Tugemann et Gilles Civario:
There is no 16-Clue Sudoku
2024 / 2025 Benmazouz Nabil 12
Algorithmes avancés
8 BackTracking
Sudoku
Designing the Board
2024 / 2025 Benmazouz Nabil 13
Algorithmes avancés
8 BackTracking
Sudoku
Checking the rules of Sudoku
Il y a trois règles à respecter :
1. Chaque ligne doit contenir exactement chacun des 9 chiffres de 1 à 9;
2. Chaque colonne doit contenir exactement chacun des 9 chiffres de 1 à 9;
3. Chaque région doit contenir exactement chacun des 9 chiffres de 1 à 9.
2024 / 2025 Benmazouz Nabil 14
Algorithmes avancés
8 BackTracking
Sudoku
Exemple
2024 / 2025 Benmazouz Nabil 15
Algorithmes avancés
8 BackTracking
Sudoku
Rule 1
public boolean isInRow(int row, int number) {
for (int i = 0; i < size; i++) {
if (board[row][i] == number) {
return true;
}
}
return false;
}
2024 / 2025 Benmazouz Nabil 16
Algorithmes avancés
8 BackTracking
Sudoku
Rule 2
public boolean isInCol(int col, int number) {
for (int i = 0; i < size; i++) {
if (board[i][col] == number) {
return true;
}
}
return false;
}
2024 / 2025 Benmazouz Nabil 17
Algorithmes avancés
8 BackTracking
Sudoku
Rule 3
public boolean isInBox(int row, int col, int number) {
int r = row - row % 3;
int c = col - col % 3;
for (int i = r; i < r + 3; i++) {
for (int j = c; j < c + 3; j++) {
if (board[i][col] == number) {
return true;
}
}
}
return false;
}
2024 / 2025 Benmazouz Nabil 18
Algorithmes avancés
8 BackTracking
Sudoku
Rules (1+2+3)
public boolean isOk(int row, int col, int number) {
return !isInRow(row, number) &&
!isInCol(col, number) &&
!isInBox(row, col, number);
}
2024 / 2025 Benmazouz Nabil 19
Algorithmes avancés
8 BackTracking
Sudoku
int EMPTY = 0;
public boolean solve() {
for (int row = 0; row < size; row++) {
for (int col = 0; col < size; col++) {
if (board[row][col] == EMPTY) {
for (int gNumber = 1; gNumber <= size; gNumber++) {
if ([Link](row, col, gNumber)) {
board[row][col] = gNumber;
if (solve()) return true;
else {
board[row][col] = EMPTY;
}
}
}
return false;
} } } return true;
}
2024 / 2025 Benmazouz Nabil 20
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
Définition
Consiste à placer n reines sur un échiquier n × n sans qu'elles ne se prennent
l'une l'autre.
Une reine peut prendre toutes les pièces se trouvant sur la même ligne, sur
la même colonne ou sur les mêmes diagonales qu'elle- même.
2024 / 2025 Benmazouz Nabil 21
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
2024 / 2025 Benmazouz Nabil 22
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
Historique
Ce problème fut posé pour la première fois en 1848 par Max Bessel dans un
journal d'échecs. Cette publication donna lieu à un engouement
extraordinaire.
Le 21 septembre 1850, Dr. Nauck donna pour 𝒏 = 𝟖 toutes les 92 solutions
alors que le mathématicien Gauss n'en trouva que 72.
D'après Kraitchick, le nombre 𝑠 de solutions en fonction de l'ordre 𝒏 de
l'échiquier est :
𝑛 1 2 3 4 5 6 7 8 9 10 11 12
s 1 0 0 2 10 4 40 92 352 720 2680 14200
2024 / 2025 Benmazouz Nabil 23
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
Modélisation
Une configuration (placement de 𝒏 reines sur un échiquier) est modélisée par
vecteur :
𝑆 = 𝑟 1 ,𝑟 2 ,…,𝑟 𝑛
𝑜𝑢 𝑖, 𝑟 𝑖 sont respectivement le numéro de colonne et le numéro de ligne où est
placée la reine.
2024 / 2025 Benmazouz Nabil 24
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
Modélisation
Exemple :
Pour la configuration de la figure suivante
(8 reines sur un échiquier 8 × 8), on a :
𝑺 = (𝟖, 𝟒, 𝟏, 𝟑, 𝟔, 𝟐, 𝟕, 𝟓)
2024 / 2025 Benmazouz Nabil 25
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
Modélisation
Exemple :
Pour la configuration de la figure suivante
(8 reines sur un échiquier 8 × 8), on a :
𝑺 = (𝟖, 𝟕, 𝟏, 𝟓, 𝟐, 𝟐, 𝟑, 𝟓)
2024 / 2025 Benmazouz Nabil 26
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
Modélisation
Un conflit de deux reines sur la même ligne se
modélise par 𝒓 𝒊 = 𝒓 𝒋 , 𝑖 ≠ 𝑗,
𝑺 = (𝟖, 𝟕, 𝟏, 𝟓, 𝟐, 𝟐, 𝟑, 𝟓)
2024 / 2025 Benmazouz Nabil 27
Algorithmes avancés
8 BackTracking
Le problème des reines (n-queens)
Modélisation
Un conflit de deux reines sur la même diagonale
𝒓 𝒊 −𝒓 𝒋
se modélise par: , = ±𝟏, 𝑖 ≠ 𝑗,
𝒊−𝒋
𝑺 = (𝟖, 𝟕, 𝟏, 𝟓, 𝟐, 𝟐, 𝟑, 𝟓)
2024 / 2025 Benmazouz Nabil 28
Algorithmes avancés
8 BackTracking
Avantages et Inconvénients
Avantages
1. Simple to implement.
2. State changes are stored in stack, meaning we do not need to concern
ourselves about them.
3. Intuitive approach of trial and error.
4. Code size is usually small.
2024 / 2025 Benmazouz Nabil 29
Algorithmes avancés
8 BackTracking
Avantages et Inconvénients
Inconvénients
1. Multiple function calls are expensive.
2. Inefficient when there is lots of branching from one state.
3. Requires large amount of space as the each function state needs to be
stored on system stack.
2024 / 2025 Benmazouz Nabil 30