Problème avec la récursivité

Version imprimable

Bonjour,

Je veux faire en Java un petit programme qui va créer un nœud. Ce nœud contient un tableau de 9 entiers (qui représente en réalité une grille 3x3 pour le jeu de taquin) et une valeur entiere qui représente le niveau, puis il va créer les successeurs de ce nœud (ou chaque successeur represente une permutation possible de 0 dans la grille)

PS: la permutation entre 0 et un autre entier n'est possible que si les deux cases sont adjacentes.

Voila le code:

la classe noeud

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Noued {
int nom;
int grille[]=new int[9];
int niveau;
 
Noued suiv1;
Noued suiv2;
Noued suiv3;
Noued suiv4;
 
public Noued(){
    suiv1=null;
    suiv2=null;
    suiv3=null;
    suiv4=null;
}
}

la classe taquin8 qui contient main

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
import java.util.ArrayList;
 
public class taquin8 {
static Integer n1,n2;
static int start[] = {1,2,3,4,0,5,7,8,6};
static int goal[] = {1,2,3,4,5,6,7,8,0};
 
    //affichage d'une grille    
    static void affichertab(int t[])
    {
        for (int i=0;i<9;i++){ 
            if ((i%3)==2){System.out.println("["+t[i]+"]");}
            else {System.out.print("["+t[i]+"]");}
                                }
 
    }
    //rechercher l'indice d'un entier
    static int indice_ent(int t[],int x)
    {int ind = 10;
        for (int i=0;i<9;i++){ 
            if (t[i]==x) ind=i;
        }
        return ind;
 
    }
 
    //rechercher l'indice de zero
    static int zero(int t[])
    {int ind = 10;
        for (int i=0;i<9;i++){ 
            if (t[i]==0) ind=i;
        }
        return ind;
 
    }
 
    //procedure pour faire la permutation de deux entier
 
    static  void permutaion(Integer n1, Integer n2)
    {Integer t;
    t=n1;
    taquin8.n1=n2;
    taquin8.n2=t;
    }
 
    //Test pour les possibilites de permutaion de 0
    static ArrayList<Integer> Test_permut(int g)
    {
    ArrayList<Integer> pp=new ArrayList<Integer>();
 
 
    switch (g)
    {
    case 0:
    {
        pp.add(1);
        pp.add(3);
    break;}
 
    case 1:
    {
        pp.add(0);
        pp.add(2);
        pp.add(4);
    break;}
 
 
    case 2:
    {
        pp.add(1);
        pp.add(5);
    break;}
 
    case 3:
    {
        pp.add(0);
        pp.add(4);
        pp.add(6);
 
    break;}
 
    case 4:
    {
        pp.add(1);
        pp.add(3);
        pp.add(5);
        pp.add(7);
 
    break;}
 
    case 5:
    {
        pp.add(2);
        pp.add(4);
        pp.add(8);
 
    break;
    }
 
    case 6:
    {
    pp.add(3);
    pp.add(7);
    break;}
 
    case 7:
    {
    pp.add(4);
    pp.add(6);
    pp.add(8);
 
    break;}
 
    case 8:
    {
    pp.add(5);
    pp.add(7);
    break;}
    default:{};            
    }
 
        return pp;
    }
 
    //creer les succ dun noeud
    static Noued creer_succ (Noued rac)
    {
 
            rac.suiv1=new Noued();
            for(int i=0;i<9;i++){rac.suiv1.grille[i]=rac.grille[i];}
            rac.suiv1.niveau=rac.niveau+1;
 
            rac.suiv2=new Noued();
            for(int i=0;i<9;i++){rac.suiv2.grille[i]=rac.grille[i];}
            rac.suiv2.niveau=rac.niveau+1;
 
            rac.suiv3=new Noued();
            for(int i=0;i<9;i++){rac.suiv3.grille[i]=rac.grille[i];}
            rac.suiv3.niveau=rac.niveau+1;
 
            rac.suiv4=new Noued();
            for(int i=0;i<9;i++){rac.suiv4.grille[i]=rac.grille[i];}
            rac.suiv4.niveau=rac.niveau+1;
 
        return rac;
    }
 
    //creer un arbre de possibilité
    static void creer_arbre(Noued r)
    {ArrayList<Integer> permut;
    do {
        taquin8.creer_succ(r);
        permut=taquin8.Test_permut(taquin8.zero(r.grille));
        for(int i=0;i<permut.size();i++){System.out.print(" > "+r.grille[permut.get(i)]);}
 
        if(!(permut.get(0).equals(null))){
        r.suiv1.grille[taquin8.indice_ent(r.suiv1.grille,0)]=r.suiv1.grille[permut.get(0)];
        r.suiv1.grille[permut.get(0)]=0;
        }
 
        if(!(permut.get(1).equals(null))){
        r.suiv2.grille[taquin8.indice_ent(r.suiv2.grille,0)]=r.suiv2.grille[permut.get(1)];
        r.suiv2.grille[permut.get(1)]=0;
        }
 
        if(!(permut.get(2).equals(null))){
        r.suiv3.grille[taquin8.indice_ent(r.suiv3.grille,0)]=r.suiv3.grille[permut.get(2)];
        r.suiv3.grille[permut.get(2)]=0;
        }
 
        if(!(permut.get(3).equals(null))){
        r.suiv4.grille[taquin8.indice_ent(r.suiv4.grille,0)]=r.suiv4.grille[permut.get(3)];
        r.suiv4.grille[permut.get(3)]=0;
        }
 
        if(!(r.suiv1.equals(null))){creer_arbre(r.suiv1);}
        if(!(r.suiv2.equals(null))){creer_arbre(r.suiv2);}
        if(!(r.suiv3.equals(null))){creer_arbre(r.suiv3);}
        if(!(r.suiv4.equals(null))){creer_arbre(r.suiv4);}
 
    }while(!(r.grille.equals(goal)));
 
 
    }
 
    //afficher un arbre
    static void affich_ab(Noued r)
    {
    if(!(r.equals(null))){taquin8.affichertab(r.grille);}
    if(!(r.suiv1.equals(null))){
        System.out.println("***S1***");
        taquin8.affich_ab(r.suiv1);}
    if(!(r.suiv2.equals(null))){taquin8.affich_ab(r.suiv2);}
    if(!(r.suiv3.equals(null))){taquin8.affich_ab(r.suiv3);}
    if(!(r.suiv4.equals(null))){taquin8.affich_ab(r.suiv4);}    
 
    }
 
    //Programme Principal
    public static void main(String[] args) {
 
    Noued rac=new Noued();
    rac.grille=taquin8.start;
    rac.niveau=0;
 
 
System.out.println("\n");
System.out.println("***Racine***");
taquin8.creer_arbre(rac);
taquin8.affich_ab(rac);
    }
}

Je veux donc créer un nœud initial qui va contenir la grille (start)
puis générer au fur et à mesure ses successeurs (qui représente les permutations possibles de 0 avec les valeurs adjacentes) jusqu'à tomber dans le nœud qui va contenir une grille qui est égale à goal.

Mais, en exécutant le programme voila le résultat dans la console:

Citation:

***Racine***
> 2 > 4 > 5 > 8 > 1 > 3 > 2Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 3
at java.util.ArrayList.rangeCheck(Unknown Source)
at java.util.ArrayList.get(Unknown Source)
at taquin8.creer_arbre(taquin8.java:175)
at taquin8.creer_arbre(taquin8.java:180)
at taquin8.main(taquin8.java:213)

Quelqu'un saurait-il m'indiquer comment résoudre cette erreur ?

Merci d'avance pour votre aide.

06/12/2013, 20h41
rg77140
Bonjour,

De façon général en programmation le premier élément d'un tableau se situe à l'index 0, le second à l'index 1, le troisième à l'index 2.

Là tu essais d'accéder à l'index 3, donc le quatrième élément de ton tableau, or ton tableau n'en contient que 3. L'erreur te dit donc que pour cette ligne tu essais d'accéder à un éléments qui se situe hors de ton tableau :

Code:

if(!(permut.get(3).equals(null))){

D'autre en écrivant du code de ce style :
Code:

1 2 3 if(objet.equals(null)){ // ... }
ton script ne rentrera jamais dans le if. Si objet est null tu auras une exception pour dire "NullPointerException". Partout où tu as ce genre de code il faut que tu le transforme en :
Code:

1 2 3 if(objet ==null){ // ... }
Romain.

J'ai modifié un peu le code :

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
import java.util.ArrayList;
 
 
public class taquin8 {
static Integer n1,n2;
static int start[] = {1,2,3,4,0,5,7,8,6};
static int goal[] = {1,2,3,4,5,6,7,8,0};
 
 
	//affichage d'une grille	
	static void affichertab(int t[])
	{
		for (int i=0;i<9;i++){ 
			if ((i%3)==2){System.out.println("["+t[i]+"]");}
			else {System.out.print("["+t[i]+"]");}
								}
 
	}
	//rechercher l'indice d'un entier
	static int indice_ent(int t[],int x)
	{int ind = 10;
		for (int i=0;i<9;i++){ 
			if (t[i]==x) ind=i;
		}
		return ind;
 
	}
 
	//rechercher l'indice de zero
	static int zero(int t[])
	{int ind = 10;
		for (int i=0;i<9;i++){ 
			if (t[i]==0) ind=i;
		}
		return ind;
 
	}
 
	//procedure pour faire la permutation de deux entier
 
	static  void permutaion(Integer n1, Integer n2)
	{Integer t;
	t=n1;
	taquin8.n1=n2;
	taquin8.n2=t;
	}
 
 
 
	//Test pour les possibilites de permutaion de 0
	static ArrayList<Integer> Test_permut(int g)
	{
	ArrayList<Integer> pp=new ArrayList<Integer>();
 
 
	switch (g)
	{
	case 0:
	{
		pp.add(1);
		pp.add(3);
	break;}
 
	case 1:
	{
		pp.add(0);
		pp.add(2);
		pp.add(4);
	break;}
 
 
	case 2:
	{
		pp.add(1);
		pp.add(5);
	break;}
 
	case 3:
	{
		pp.add(0);
		pp.add(4);
		pp.add(6);
 
	break;}
 
	case 4:
	{
		pp.add(1);
		pp.add(3);
		pp.add(5);
		pp.add(7);
 
	break;}
 
	case 5:
	{
		pp.add(2);
		pp.add(4);
		pp.add(8);
 
	break;
	}
 
	case 6:
	{
	pp.add(3);
	pp.add(7);
	break;}
 
	case 7:
	{
	pp.add(4);
	pp.add(6);
	pp.add(8);
 
	break;}
 
	case 8:
	{
	pp.add(5);
	pp.add(7);
	break;}
	default:{};            
	}
 
		return pp;
	}
 
	//creer les succ dun noeud
	static Noued creer_succ (Noued rac)
	{
 
			rac.suiv1=new Noued();
			for(int i=0;i<9;i++){rac.suiv1.grille[i]=rac.grille[i];}
			rac.suiv1.niveau=rac.niveau+1;
 
			rac.suiv2=new Noued();
			for(int i=0;i<9;i++){rac.suiv2.grille[i]=rac.grille[i];}
			rac.suiv2.niveau=rac.niveau+1;
 
			rac.suiv3=new Noued();
			for(int i=0;i<9;i++){rac.suiv3.grille[i]=rac.grille[i];}
			rac.suiv3.niveau=rac.niveau+1;
 
			rac.suiv4=new Noued();
			for(int i=0;i<9;i++){rac.suiv4.grille[i]=rac.grille[i];}
			rac.suiv4.niveau=rac.niveau+1;
 
		return rac;
	}
 
	//creer un arbre de possibilite
	static void creer_arbre(Noued r)
	{ArrayList<Integer> permut;
	do {
		taquin8.creer_succ(r);
		permut=taquin8.Test_permut(taquin8.zero(r.grille));
 
 
		if(permut.get(0)!=null){
		r.suiv1.grille[taquin8.indice_ent(r.suiv1.grille,0)]=r.suiv1.grille[permut.get(0)];
		r.suiv1.grille[permut.get(0)]=0;
		}
 
		if(permut.get(1)!=null){
		r.suiv2.grille[taquin8.indice_ent(r.suiv2.grille,0)]=r.suiv2.grille[permut.get(1)];
		r.suiv2.grille[permut.get(1)]=0;
		}
 
		if(permut.get(2)!=null){
		r.suiv3.grille[taquin8.indice_ent(r.suiv3.grille,0)]=r.suiv3.grille[permut.get(2)];
		r.suiv3.grille[permut.get(2)]=0;
		}
 
		if(permut.get(3)!=null){
		r.suiv4.grille[taquin8.indice_ent(r.suiv4.grille,0)]=r.suiv4.grille[permut.get(3)];
		r.suiv4.grille[permut.get(3)]=0;
		}
 
		if(r.suiv1!=null){creer_arbre(r.suiv1);}
		if(r.suiv2!=null){creer_arbre(r.suiv2);}
		if(r.suiv3!=null){creer_arbre(r.suiv3);}
		if(r.suiv4!=null){creer_arbre(r.suiv4);}
 
	}while(r.grille!=goal);
 
 
	}
 
	//afficher un arbre
	static void affich_ab(Noued r)
	{
	if(r!=null){taquin8.affichertab(r.grille);}
	if(r.suiv1!=null){
		System.out.println("***S1***");
		taquin8.affich_ab(r.suiv1);}
	if(r.suiv2!=null){taquin8.affich_ab(r.suiv2);}
	if(r.suiv3!=null){taquin8.affich_ab(r.suiv3);}
	if(r.suiv4!=null){taquin8.affich_ab(r.suiv4);}	
 
	}
 
	//Programme Principal
	public static void main(String[] args) {
 
	Noued rac=new Noued();
	for(int i=0;i<9;i++){rac.grille[i]=taquin8.start[i];}
	rac.niveau=0;
 
 
System.out.println("\n");
System.out.println("***Racine***");
 
taquin8.affich_ab(rac);
taquin8.creer_arbre(rac);
 
	}
 
}

voila le resultat dans la console:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 3
	at java.util.ArrayList.rangeCheck(Unknown Source)
	at java.util.ArrayList.get(Unknown Source)
	at taquin8.creer_arbre(taquin8.java:175)
	at taquin8.creer_arbre(taquin8.java:180)
	at taquin8.main(taquin8.java:215)
 
 
***Racine***
[1][2][3]
[4][0][5]
[7][8][6]

Mais normalmenet le .get(3) n'est pas null !
car en réalité c'est le nombre de permutation qui peut faire le 0 qui et au centre de la grille qui contient 9 entiers (à l'indice 4 en commençant par l'indice 0 de la grille).