Backtracking : N-Queen problem ?

Version imprimable

Hello,

(En espérant y voir plus clair)

Ce code déniché sur Youtube, (modifié sensiblement) permet d'obtenir les solutions du problème des N reines.

https://www.youtube.com/watch?v=p4_QnaTIxkQ

Ce qui me met dans le trouble, c'est au moment du "backtracking" de la fonction nQueens, la boucle for(int colonne = 1 ; colonne<=n ;colonne++), qui dit bien tant que c'est inférieur ou égal à n, soit 4 pour cet exemple.

Hors, après avoir vérifié si la ligne 3 et la colonne 4 est une place valide (et qui ne l'est pas), la colonne incrémente à 5 ? Les positions occupées par les reines, à ce moment là, sont ligne 1, colonne 1 et ligne 2, colonne 3.

Alors, je ne comprends pas pourquoi après l'incrémentation, la fonction reboucle à partir de la ligne 2, colonne 4 ?
En gros, de if(place (3,4), qui retourne false, il passe à if(place (2,4))
(Sur papier c'est facile à exprimer, mais en codant, c'est une autre affaire).

Merci d'avance.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include <iostream> #include <cstdlib> using namespace std; int solution = 0; int x[10]; void nQueens(int); bool place(int , int); int n = 4; int main() { nQueens(1); return 0; } void nQueens(int ligne){ for(int colonne = 1 ; colonne<=n ;colonne++){ if(place(ligne,colonne)){ x[ligne] = colonne; if (ligne==n) { solution ++; for (int a=1; a<=n; a++) cout<< x[a] << " "; cout << endl << "Solution : " << solution << endl; }else { nQueens(ligne+1); } } } } bool place(int ligne , int colonne){ for(int j = 1 ; j<=(ligne-1);j++){ if((x[j] == colonne)||(abs(x[j]-colonne)== abs(j-ligne))) { return false; } } return true; }

26/01/2018, 01h38
dalfab

Bonjour,

C'est la récursivité qui gère le "backtracking". nQueen(1) appelle nQueen(2) qui appelle nQueen(3).
S'il n'y a pas de solution trouvée pendant nQueen(3), la fonction aura parcouru toute sa boucle for et donc va se terminer. A ce moment le code va retourner à nQueen(2) et va continuer sa boucle en envisageant la position suivante pour la ligne 2.

Et attention en C, les indices tableau commencent à 0. Tout comme en C++, mais code est plus du C que du C++.
26/01/2018, 11h14
Barbasol

1 pièce(s) jointe(s)

Merci, Dalfab

Merci !

Je comprends mieux. J'ai tenté de schématiser ce qui se passe dans la mémoire (*) [pas la totalité des variables, ni le passage à la fonction Place] comme suit :

(*) Chaque colonne représente un espace mémoire dédié au tableau de variables globales et aux fonctions

Pièce jointe 345848

Je suis revenu dessus après quelques jours, pour évaluer ma compréhension sur le fonctionnement de la pile. Je me suis "amusé" avec l'empilement et le désempilement sur un vecteur (push_back, pop_back). Ça ne sert à rien, mais bon ...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
 
#include <iostream>
#include <cstdlib>
#include <vector>
 
 
using namespace std;
 
 
int solution = 0;
void nQueens(int);
bool place(int , int);
vector <int> x;
int n;
 
 
 
int main() {
 
 
    do
    {
        cout << "Entrez le nombre de reines : ";
        cin >> n;
    }
    while (n < 4);
 
    nQueens(0);
 
    return 0;
}
 
 
void nQueens(int ligne){
 
 
 
 
    for(int colonne = 0 ; colonne<n ;colonne++){
 
         if(place(ligne,colonne)){
 
            x.push_back (colonne);
 
            if (ligne==n-1)
            {
 
                 solution ++;
                 for (int a=0; a<x.size(); a++)
                    cout<< x[a] << " ";
                 x.pop_back();
                 cout << endl << "Solution : " << solution << endl;
 
 
            }else
           {
               nQueens(ligne+1);
 
            }
        }
 
        if (colonne == n-1)
            x.pop_back();
 
    }
 
}
 
bool place(int ligne , int colonne){
 
    for(int j = 0 ; j<ligne;j++){
 
        if((x[j] == colonne)||(abs(x[j]-colonne)== abs(j-ligne)))
        {
            return false;
 
        }
 
    }
 
    return true;
 
}

Salut,

En fait, bien que je sois totalement opposé à l'utilisation de ce genre d'exemple pour l'explication de ce qu'est la récursivité, je crois que le calcul de la factorielle (ou de l'exponentielle) est (peut-être) l'exemple le plus adapté pour permettre de voir ce qui se passe lors des appels récursifs.

Voyons donc comment cela se passe! Typiquement, un algorithme récursif pour le calcul de la factorielle prendrait la forme suivante:
Code:

1 2 3 4 5 6 7 8 9 10 int factorielle (int value){ /* Le cas de base: celui dans lequel on ne fait pas d'appel supplémentaire */ if(value == 1){ return value; } /* arrivé ici, nous savons que nous devons faire "un appel de plus" à * la fonction, dans le but de "tendre vers le cas de base" */ return value * factorielle(value - 1); }
Essayons maintenant de nous mettre à la place de l'ordinateur, et de voir comment il va réagir pour calculer la factorielle de 3 (par exemple):

Lors de l'appel de la fonction sous la forme de factorielle(3) le paramètre nommé "value" vaut ... 3.
Comme 3 n'est pas égal à 1, l'instruction return 1 est ignorée, ce qui fait que l'on se retrouve à exécuter l'instruction return 3 * factorielle( 3 - 1) (je n'ai fait que remplacer le nom du paramètre par sa valeur actuelle :D )
Cela nous amène donc à appeler factorielle(2)(car 3-1 == ... 2)
Lors de l'appel de la fonction sous la forme de factorielle(2) le paramètre nommé "value" vaut ... 2.
Comme 2 n'est pas égal à 1, l'instruction return 1 est ignorée, ce qui fait que l'on se retrouve à exécuter l'instruction return 2 * factorielle( 2 - 1)
Cela nous amène donc à appeler factorielle(1)(car 2-1 == ... 1)
Lors de l'appel de la fonction sous la forme de factorielle(1) le paramètre nommé "value" vaut ... 1.
nous passons du coup par l'instruction return 1, vu que ... 1 == 1 (oui, oui, je t'assure), ce qui a pour effet de mettre fin à la récursion.
Nous renvoyons donc cette valeur (1) à la "fonction appelante" (qui était factorielle(2), qui va l'utiliser pour faire le calcul 2 * 1 (2 étant la valeur de "value" pour cet appel), et qui va renvoyer le résultat (à savoir ... 2) à la "fonction appelante".
La valeur 2 est donc renvoyée à la fonction qui a fait appel à factorielle(2), qui n'est autre que ... factorielle(3), qui en a besoin pour calculer 3*2
factorielle(3) va donc renvoyer la valeur 6 (car il paraîtrait que 3*2 = ...6) à la fonction qui a fait appel à factorielle(3)
Enfin, la fonction qui a fait appel à factorielle(3) n'est nulle autre que... la fonction principale (ou n'importe quelle fonction de ton cru), qui a besoin de calculer la valeur en question, et qui pourra utiliser le résultat obtenu comme bon lui semble

NOTA: Comme je l'ai dit plus haut, je ne suis absolument pas favorable à une utilisation récursive pour le calcul de la factorielle; que ce soit pour en expliquer le principe ou comme exercice.

Malheureusement, c'est aussi l'exemple le plus simple que l'on puisse trouver; ce qui en fait aussi l'exemple pour lequel il est le plus facile de suivre le comportement "pas à pas" comme je viens de le faire ;)