Discussion :

[ajlif]

Bonjour,

je n'arrive pas à comprendre le principe utilisé pour résoudre ce problème (Voir les commentaires dans le code). En fait cet algorithme résout le problème de 8 r sur une dame.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
public static void main(String[] args) {
    int y = 0;
    b[0] = -1;
 
    while (y >= 0) {
 
    	do
    	{ b[y]++; 
    	System.out.println(""+b[y]);}
 
      while ((b[y] < 8) && unsafe(y));
 
      if (b[y] < 8) 
      {
        if (y < 7) {
          b[++y] = -1;  // à ce niveau la qu'est ce qu'il fait et quand appelle exactement putboard ?
          System.out.println("b["+y+"] = -1");
        } else {
 
          putboard(); // mettre les 8 r sur la dame
 
        }
      } else
      {y--;}//else
 
    }
 
 
  }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
static boolean unsafe(int y) {
    int x = b[y];
    for (int i = 1; i <= y; i++) {
      int t = b[y - i];
      if (t == x || t == x - i || t == x + i) { // pourquoi on compare t et x +/- i ????
        return true;
 
      }
    }
 
    return false;
  }

[joel.drigo]

Salut,

1. b[++y] = -1; // à ce niveau la qu'est ce qu'il fait et quand appelle exactement putboard ?
   1. On fait d'abord ++y, ce qui incrémente y
   2. Ensuite, on met -1 dans la cellule d'index y du tableau b
   
   Tout simplement.
   
   Quant à l'appel de putboard, il suffit de regarder le test :
   
   

   Code :

   Sélectionner tout - Visualiser dans une fenêtre à part

   1
   2
   3
   4
   5
   6
   7
   8
   f (y < 7) {
              // on appelle pas putboard
           } else {
    
             // on appelle putboard
             putboard(); // mettre les 8 r sur la dame
    
           }

   Donc on appelle putboard quand y n'est pas inférieur à 7.
   
   
   
2. if (t == x || t == x - i || t == x + i) { // pourquoi on compare t et x +/- i ????Déjà, pour répondre à cette question, il faut déterminer ce que sont x et t :
   
   • int x = b[y];
   • int t = b[y - i];
   
   
   Donc on compare deux cellules du tableau b, la première correspond à une cellule fixée par le paramètre de unsafe, l'autre correspond à différentes cellules successives (boucle for (int i = 1; i <= y; i++) {.
   
   on parcourt le tableau de y-y à y-1, donc de 0 à y exclus. Donc on compare chaque b[] (t) précédent celui fixé au début(x).
   
   C'est plus compliqué de savoir pourquoi on compare t et x+/-i sans avoir le programme/algorithme complet. Mais, on peut commencer à s'intéresser à la boucle do/while :
   
   

   Code :

   Sélectionner tout - Visualiser dans une fenêtre à part

   1
   2
   3
   4
   5
   6
   do { 
    
      b[y]++; 
      System.out.println(""+b[y]);
    
   } while ((b[y] < 8) && unsafe(y));

   Quand on l'indente correctement (ça aussi ça aide à comprendre un code !), on voit qu'on incrémente la valeur d'une cellule de b (initialisée à -1, donc qui va prendre des valeurs de 0 à n), tant qu'une condition n'est pas vérifiée. Cette condition indique qu'on incrémente tant qu'on a à la fois b[y]<8 et unsafe(y) true, donc que le test (t == x || t == x - i || t == x + i) est true.
   
3. Maintenant, pour comprendre l'algorithme entier, il vaudrait mieux regarder l'algorithme d'abord, non encodé dans un langage particulier, voire même en français dans le texte. Ensuite, on peut éventuellement exécuter le programme pas à pas, et voir comment progresse le contenu du tableau.
   
   

[ajlif]

j'ai essayé de l'éxecuter manuellement mais a chaque fois je me trouve bloqué surtout unsafe est la clé je pense pour comprendre le reste
eh voici l'algorithme entier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
 
public class NQueens {
 
  private static int[] b = new int[8];
  private static int s = 0;
 
  static boolean unsafe(int y) {
    int x = b[y];
    for (int i = 1; i <= y; i++) {
      int t = b[y - i];
      if (t == x || t == x - i || t == x + i) {
        return true;
 
      }
    }
 
    return false;
  }
 
  public static void putboard() { 
    System.out.println("\n\nSoluzione " + (++s));
    for (int y = 0; y < 8; y++) {
      for (int x = 0; x < 8; x++) { // 
        System.out.print((b[y] == x) ? "|R" : "|_");
      }
      System.out.println("|");
    }
  }
 
 
 
  public static void main(String[] args) {
    int y = 0;
    b[0] = -1;
 
    while (y >= 0) {
 
    	do
    	{ b[y]++; }
 
      while ((b[y] < 8) && unsafe(y));
 
      if (b[y] < 8) 
      {
        if (y < 7) {
          b[++y] = -1;
 
        } else {
 
          putboard();
 
        }
      } else
      {y--;}//else
 
    }
 
 
  }//void main
}//NQueens

[joel.drigo]

Déjà, avec le code complet, on voit tout de suite le modèle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 private static int[] b = new int[8];
  private static int s = 0;

s sert à "compter" les solutions (parce qu'il y a plusieurs solutions au problème), surtout pour afficher un titre du genre "solution numéro #".
b est un tableau de 8 entiers. Donc à priori, on y stocke les numéros de colonnes des dames (le problème étant de positionner 8 dames sur un échiquier (un tableau 2D 8x8) de manière à ce qu'aucune dame ne puisse prendre une autre dame. Le numéro de ligne étant la position dans le tableau.

En gros, rapidement, vu le nom de la méthode (unsafe), sans même exécuter le programme pas à pas, le principe doit être de placer les dames dans une position de base, puis de les déplacer jusqu'à ce qu'elle soit "safe", en sécurité. Le test de comparaison de x et t, +/- i doit permettre de tester si une dame peut en prendre une autre (soit x prend t, soit t prend x). unsafe retourne true lorsque une dame est menacée par une autre.

Décomposons le test : (t == x || t == x - i || t == x + i)

1. si t == x, alors les deux dames sont dans la même colonne : la prise est possible. C'est la prise en colonne. (La prise en ligne est éliminée de fait par le modèle : on met une seule dame dans chaque ligne).
2. Les deux autres conditions concernent la prise en diagonale. Pour une position de dame donnée X (sur une ligne au hasard), une autre dame située sur une ligne adjacente et en position de prise si sa colonne est à +1 ou -1 de la colonne de X. Sur une ligne séparée de 2 lignes, à +2 ou -2 de la colonne de X, puis + ou -3, etc. On voit donc qu'il y a un ligne entre le nombre de ligne de séparation entre les deux dames, et la différence entre le numéro de colonnes entre les deux. D'où ce test x==t-i et x==t+i, en faisant varier i.

[ajlif]

Décomposons le test : (t == x || t == x - i || t == x + i)
1 si t == x, alors les deux dames sont dans la même colonne : la prise est possible. C'est la prise en colonne. (La prise en ligne est éliminée de fait par le modèle : on met une seule dame dans chaque ligne).
2 Les deux autres conditions concernent la prise en diagonale. Pour une position de dame donnée X (sur une ligne au hasard), une autre dame située sur une ligne adjacente et en position de prise si sa colonne est à +1 ou -1 de la colonne de X. Sur une ligne séparée de 2 lignes, à +2 ou -2 de la colonne de X, puis + ou -3, etc. On voit donc qu'il y a un ligne entre le nombre de ligne de séparation entre les deux dames, et la différence entre le numéro de colonnes entre les deux. D'où ce test x==t-i et x==t+i, en faisant varier i.

merci pour la réponse mais je veux quelques explications :
je veux savoir que représentent x et t exactement
j'arrive pas à comprendre la vérification des diagonales commment ca se fait exactement?
comment la prise est possible quand t==x ?
POURQUOI au début x prend ce valeur x = b[y]?

je vous remercie du temps que vous m'avez consacré

[joel.drigo]

POURQUOI au début x prend ce valeur x = b[y]?

On cherche à savoir si chaque dame est menacée. Donc, à un moment donné, on va regarder si une dame en particulier est menacée.
On fait cette boucle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
do { 
   b[y]++; 
}
while ((b[y] < 8) && unsafe(y));

On y incrémente b[y], autrement dit on fait varier le numéro de colonne de la dame de la ligne y. Et on teste si elle est menacée (si elle peut être prise par une autre dame). Ceci est fait par le test et en particulier par 'unsafe' à qui on passe 'y' justement. Donc dans 'unsafe' on commence par dire : on veut tester la dame qui est en ligne y, et ce qui nous intéresse c'est sa colonne, qu'on appelle x (ce qui se traduit en java par x=b[y]).

j'arrive pas à comprendre la vérification des diagonales commment ca se fait exactement?

Fait un dessin :

*			*			*
	*		*		*
		*	*	*
*	*	*	D	*	*	*	*
		*	*	*
	*		*		*
*			*			*
			*				*

D est une dame de coordonnées 3,3. Dans le modèle utilisé par le programme, on aurait b[3]=3. J'ai mis des étoiles dans toutes les cases où une dame pourrait menacer notre dame D.
Notons LD la ligne de D et CD la colonne de D : LD=3, CD=3 donc.

Prenons la case avec l'étoile rouge, appelons-la R. Elle a pour coordonnées 4,4. Disons que LR=4, CR=4. Soit si on compare à celle de D, LD+1, CD+1,.
Idem pour la bleu B , de coordonnées LB=5,CB=5, soit LD+2, CD+2. Et la verte, LV=6,CV=6 soit LD+3,CD+3.

Soit en résumé :
LR-LD=1 et CR-CD=1. ou encore LR=LD+1, CR=CD+1...
LB-LD=2 et CB-CD=2.
LV-LD=3 et CV-CD=3.

On voit qu'on peut faire une boucle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
pour i de 1 à 3 
    L[n] = LD + i
    C[n] = CD + i
 
fin pour

On voit donc que si on parcourt des lignes, ou des colonnes, avec un index, celui-ci ajouté à la coordonnée de notre dame à tester correspond à une position de prise en diagonale.

Maintenant reprend ce croquis et décale D en 3, 5 par exemple (ligne 3, colonne 5, ou ligne 5, colonne 3, comme tu veux) et applique le même raisonnement en déplaçant les étoiles, en calculant les différences entre les lignes et les colonnes : tu verras que tu obtiendras la même boucle. Tu auras toujours la différence entre numéro de colonnes égale à la différence entre numéro de lignes.