BackTracking 

backtracking

Prenons le problème des huit reines, on essaie de placer une reine par colonne,
la première en ligne 1,
la deuxième en ligne 3,
la troisième en ligne 5,
la quatrième en ligne 2,
la cinquième en ligne 4,
pour la 6ième aucune ligne ne convient !...
On va donc être obligé de remettre en cause les positions des reines déjà en place: voila le principe du retour sur trace, backtracking....
r1
On essaiera donc de placer  la cinquième  reine en ligne 8, la première prochaine position possible,  mais aucune ligne ne convient quand même pour la reine  6!...  r2

Comme on a épuisé toutes les possibilités pour la reine 5, il va falloir "backtracker" jusqu'à la reine 4 qui viendra en ligne 7,on pourra alors placer la reine 5 en ligne 2, la 6 en ligne 4, la 7 en 6, mais on n'arrivera pas à placer la 8 ....une fois encore il faudra backtracker...

Heureusement la récursivité va nous permettre d'écrire une procédure qui fera tout cela simplement...

 

r3

PositionneReine(N) {
si (N<9)
alors pour les lignes 1 à 8
                               si laCase(ligne,colonneN) est libre
                                               alors si AucuneReineSurLaLigne
                                                               alors si AucuneReineSurLaDiagonale1
                                                                              alors si AucuneReineSurLaDiagonale2
                                                                                       alors {Case(ligne,colonneN)=N; //*** position possible
                                                                                                 PositionneReine(N+1);   // *** on passe à la suivante
                                                                                                 LibererCase(ligne,colonneN);//*** Backtracking !....                                                                                                                                                       }             
sinon on a trouvé...
}

 Voici quelques exemples utilisant cette méthode....


Les 8 reines

reines

Le cavalier d'Euler

cavalier

Le solitaire

Cherche(int n) {
        int x, y, x1=0, x2=0, y1=0, y2=0, d;
        if (fini)
            return;//**** pour s'arrêter à la première *******************
        if ((n > 31) && (jeu[3 * 7 + 3] == 1)) {
            System.out.println("Trouve");
            afficheJeu();
            fini = true;
            return;
        }//********** Cherche proprement dit *****************************
        for (x = 0; x < 7; x++)
            for (y = 0; y < 7; y++) {
                if (jeu[y * 7 + x] == 1)
                    for (d = 1; d <= 4; d++) {
                        switch (d) {
                        case 1:    x1 = x + 1;y1 = y;x2 = x + 2;y2 = y;break;// à droite
                        case 2:    x1 = x;y1 = y + 1;x2 = x;y2 = y + 2;break;// en bas
                        case 3:    x1 = x - 1;y1 = y;x2 = x - 2;y2 = y;break;// à gauche
                        case 4:    x1 = x;y1 = y - 1;x2 = x;y2 = y - 2;break;// en haut
                        }
                        if ((x2 >= 0) && (x2 < 7) && (y2 >= 0) && (y2 < 7))
                            if (jeu[y2 * 7 + x2] == 0)
                                if (jeu[y1 * 7 + x1] == 1) {
                                    jeu[y * 7 + x] = 0;
                                    jeu[y1 * 7 + x1] = 0;
                                    jeu[y2 * 7 + x2] = 1;
                                    chemin[n]=100*d+10*x+y;//IntToChemin(d,x,y);
                                    Cherche(n + 1);
                                    // BackTracking;
                                    jeu[y * 7 + x] = 1;
                                    jeu[y1 * 7 + x1] = 1;
                                    jeu[y2 * 7 + x2] = 0;
                                }
                    }
            }
    }

Le Sudoku