Bonjour.

J'ai fait une classe permettant de placer n reines sur un échiquier sans qu'elles se menacent. J'ai voulu faire la méthode qui place toute les reines de manière récursive.

Ma fonction utilise le backtracking c'est à dire que si je ne peux pas mettre une reine sur la ligne sans qu'elle soit prise je réévalue le coup précédent.

Voici ma méthode auriez vous une idée afin de l'optimiser ....

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
62
63
64
65
66
67
68
69
70
71
 
public void justDoIt(int ligne,int colonne)	{
		test++;
		int tmp_colonne=0;
		int tmp_ligne=0;
 
		/* Si on peut mettre la reine aux indices données en paramètre on la met */
		if(canPutLady(ligne,colonne))	{
 
			putLady(ligne,colonne);
 
			etape++;
			System.out.println("************** ETAPE "+etape+" **************\n************** BACK "+back+" **************");
			System.out.println(this);
 
			/* Si ce n'est pas la dernière reine que l'on met on continue */
			if(ligne+1<taille)	{
				justDoIt(ligne+1,0);
			}
 
			else 
				return;
 
		}
 
		else	{
			/* Si l'indice de la colonne donnée en paramètre est inférieur à la taille-1 de l'échiquier
			on peut essayer de voir si la reine peut aller sur la colonne de droite */
			if(colonne+1<taille)	{
				justDoIt(ligne,colonne+1);
			}
 
			/*On ne peut pas mettre la reine dans la ligne mis en paramètre avec la configuration de l'échiquier actuel */
			else	{
 
				/* Si la reine de la ligne du dessus n'est pas sur l'avant dernière colonne on enlève cette reine
				et on essaie de la placer sur la première colonne suivant possible */
				if((echiquier[ligne-1]+1)<taille)	{
					tmp_colonne=(echiquier[ligne-1]+1);
					echiquier[ligne-1]=-1;
					etape++;
					back++;
					System.out.println("************** ETAPE "+etape+" **************\n************** BACK "+back+" **************");
					System.out.println(this);
					justDoIt(ligne-1,tmp_colonne);
				}
 
				/* Sinon on recule encore d'une ligne */
				else	{
					/* On prend la ligne du dessus et on vérifie que la colonne n'est pas la dernière */
					tmp_colonne=echiquier[ligne-1];
					tmp_ligne=ligne-1;
					echiquier[ligne-1]=-1;
					etape++;
					back++;
					System.out.println("************** ETAPE "+etape+" **************\n************** BACK "+back+" **************");
					System.out.println(this);
 
					/* Si ce n'est pas la dernière colonne on essaie de replacer la reine qu'on enlève à partir de la colonne suivante */
					if(tmp_colonne+1<=taille)	{
						justDoIt(tmp_ligne-1,echiquier[tmp_ligne-1]+1);
					}
 
					/* Sinon on repart de la première colonne */
					else	{
						justDoIt(ligne-1,0);
					}
				}
			}
		}
	}