Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Neunerpuzzle » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Neunerpuzzle
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 220

Neunerpuzzle Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo, es gilt ein 3 mal 3 Feld mit 8 Zahlen und der 0 in eine richtige Reihenfolge zu bringen. Das Feld am Anfang ist anfang, dass Zielfeld ist ziel. Wie kann ich eine Folge vom anfang bis zum ziel erzeugen? Hier mein Vorschlag:

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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package fu_hagen;

import java.util.ArrayList;

/**
 *
 * @author Richard Kunstwadl
 */
public class FU_Hagen {
int[][] ziel ={{1,2,3},{4,5,6},{7,8,0}};
int[][] ausgang = {{1,2,3},{8,0,5},{4,7,6}};


public boolean up (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (i>0 && k[i-1][j] == 0){
            return true;
        }
        }
    }
    return false;
}


public boolean down (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (i<2 && k[i+1][j] == 0){
            return true;
        }
        }
    }
    return false;
}

public boolean left (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (j < 2 && k[i][j] == 0){
            return true;
        }
        }
    }
    return false;
}

public boolean right (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (j > 0 && k[i][j] == 0){
            return true;
        }
        }
    }
    return false;
}



public ArrayList<int[][]> starter (int[][] z, int[][] a){
    ArrayList<int[][]> korb_s = new ArrayList<int[][]>();
    return rekursion(z,a,korb_s);
}

public ArrayList<int[][]> rekursion(int[][] z, int[][] a, ArrayList<int[][]> korb){
    if (korb.size()==0){
        korb = new ArrayList<int[][]>();
    }
    boolean ende = true; 
    for (int i=0; i<3; i++){
        for (int j= 0; j< 3; j++){
            if ( z[i][j] != a[i][j] )
            { ende = false;
            i = 3; j = 3;
            } 
        }
    }
    if (ende == true) return korb; 
    
    int[][] bi=a;
    if (up(bi)){
        for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (i>0 && bi[i-1][j] == 0){
            int zwischen = bi[i][j];
            bi[i][j]=0;
            bi[i-1][j]=zwischen; 
            korb.add(bi);
            rekursion(z,bi,korb);
        }
        }
    }
    }
       
        bi = a;
        if (down(bi)){
        for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (i>0 && bi[i+1][j] == 0){
            int zwischen = bi[i][j];
            bi[i][j]=0;
            bi[i+1][j]=zwischen; 
            korb.add(bi);
            rekursion(z,bi,korb);
        }
        }
    }
        
    }
        
        bi = a;
        if (left(bi)){
        for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (j <2 && bi[i][j] == 0){
            int zwischen = bi[i][j+1];
            bi[i][j]=zwischen;
            bi[i][j+1]=0; 
            korb.add(bi);
            rekursion(z,bi,korb);
        }
        }
    }
        
    }
        
         bi = a;
        if (right(bi)){
        for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (j > 0 && bi[i][j] == 0){
            int zwischen = bi[i][j-1];
            bi[i][j]=zwischen;
            bi[i][j-1]=0; 
            korb.add(bi);
            rekursion(z,bi,korb);
        }
        }
    }
        
    }
    
        
        
    
    return korb; 
}
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        FU_Hagen p = new FU_Hagen();
        ArrayList<int[][]> a_korb= new ArrayList<int[][]>();
        a_korb= p.starter(p.ziel, p.ausgang);
        for (int[][] ausgabe : a_korb){
            for (int i=0; i<3; i++){
                for (int j=0; j<3; j++){
                    System.out.print(ausgabe[i][j] + " ");
                }
            }
            System.out.println("___________________");
        }
    }
    
}


12.10.2019 14:18 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 220

RE: Neunerpuzzle Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Der Code beinhaltet, dass unendliche Schleifen eingezogen werden. Ich habe versucht das zu verbessern, aber das Problem ist, dass immer die Anfangskonstellation ausgegeben wird!

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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package fu_hagen;

import java.util.ArrayList;

/**
 *
 * @author Richard Kunstwadl
 */
public class FU_Hagen {
int[][] ziel ={{1,2,3},{4,5,6},{7,8,0}};
int[][] ausgang = {{1,2,3},{8,0,5},{4,7,6}};


public boolean up (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (i>0 && k[i-1][j] == 0){
            return true;
        }
        }
    }
    return false;
}


public boolean down (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (i<2 && k[i+1][j] == 0){
            return true;
        }
        }
    }
    return false;
}

public boolean left (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (j < 2 && k[i][j] == 0){
            return true;
        }
        }
    }
    return false;
}

public boolean right (int[][] k) {
    for (int i= 0; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (j > 0 && k[i][j] == 0){
            return true;
        }
        }
    }
    return false;
}



public ArrayList<int[][]> starter (int[][] z, int[][] a){
    ArrayList<int[][]> korb_s = new ArrayList<int[][]>();
    return rekursion(z,a,korb_s);
}

public ArrayList<int[][]> rekursion(int[][] z, int[][] a, ArrayList<int[][]> korb){
    boolean ende = true; 
    for (int i=0; i<3; i++){
        for (int j= 0; j< 3; j++){
            if ( z[i][j] != a[i][j] )
            { ende = false;
            i = 3; j = 3;
            } 
        }
    }
    if (ende == true) return korb; 
    
    int[][] bi= a;
    if (up(bi)){
        for (int i= 1; i< 3; i++){
        for (int j = 0; j< 3; j++){
            if (i>0 && bi[i-1][j] == 0){
            int zwischen = bi[i][j];
            bi[i][j]=0;
            bi[i-1][j]=zwischen; 
            System.out.println("Jetzt in up");
            if (korb.indexOf(bi)== -1){
            System.out.println("Wird hinzugefügt?");
            korb.add(bi);
            return rekursion(z,bi,korb);
            }
        }
        }
    }
    }
       
        
        if (down(bi)){
        for (int i= 0; i< 2; i++){
        for (int j = 0; j< 3; j++){
            if (i>0 && bi[i+1][j] == 0){
            int zwischen = bi[i][j];
            bi[i][j]=0;
            bi[i+1][j]=zwischen; 
            if (korb.indexOf(bi)== -1){
            korb.add(bi);
            return rekursion(z,bi,korb);
            }
        }
        }
    }
        
    }
        
        
        if (left(bi)){
        for (int i= 0; i< 3; i++){
        for (int j = 0; j< 2; j++){
            if (j < 2 && bi[i][j] == 0){
            int zwischen = bi[i][j+1];
            bi[i][j]=zwischen;
            bi[i][j+1]=0; 
            if (korb.indexOf(bi)== -1){
            korb.add(bi);
            return rekursion(z,bi,korb);
            }
        }
        }
    }
        
    }
        
         
        if (right(bi)){
        for (int i= 0; i< 3; i++){
        for (int j = 1; j< 3; j++){
            if (j > 0 && bi[i][j] == 0){
            int zwischen = bi[i][j-1];
            bi[i][j]=zwischen;
            bi[i][j-1]=0; 
            if (korb.indexOf(bi)== -1){
            korb.add(bi);
            return rekursion(z,bi,korb);
            }
        }
        }
    }
        
    }
    
        
        
    
    return korb; 
}
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        FU_Hagen p = new FU_Hagen();
        ArrayList<int[][]> a_korb= new ArrayList<int[][]>();
        a_korb= p.starter(p.ziel, p.ausgang);
        for (int[][] ausgabe : a_korb){
            for (int i=0; i<3; i++){
                for (int j=0; j<3; j++){
                    System.out.print(ausgabe[i][j] + " ");
                }
                System.out.println("");
            }
            System.out.println("___________________");
        }
    }
    
}

12.10.2019 16:26 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 220

RE: Neunerpuzzle Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Meine erste Fehlersuche ergab, dass ein Stein zuerst verschoben wird, und dann in einer anderen Rekursion wieder zurückgeschoben wird, wodurch keine weitere Rekursion mehr erfolgt. Wie kann ich das vermeiden?
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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package fu_hagen;

import java.util.ArrayList;

/**
 *
 * @author Richard Kunstwadl
 */
public class FU_Hagen {

    int[][] ziel = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
    int[][] ausgang = {{1, 2, 3}, {8, 0, 5}, {4, 7, 6}};
    ArrayList<int[][]> resultat = new ArrayList<int[][]>();
    ArrayList<int[][]> korb = new ArrayList<int[][]>();

    public boolean up(int[][] k) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i > 0 && k[i - 1][j] == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean down(int[][] k) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i < 2 && k[i + 1][j] == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean left(int[][] k) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (j < 2 && k[i][j] == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean right(int[][] k) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (j > 0 && k[i][j] == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public void starter(int[][] z, int[][] a) {
        ArrayList<int[][]> korb_s = new ArrayList<int[][]>();
        rekursion(z, a, korb_s);
    }

    public void rekursion(int[][] z, int[][] a, ArrayList<int[][]> korb) {
        boolean ende = true;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (z[i][j] != a[i][j]) {
                    ende = false;
                    i = 3;
                    j = 3;
                    System.out.println("Falsches Ende");
                }
            }
        }
        if (ende == true) {
            resultat = korb;
            System.out.println("jetzt wird abgebrochen " + a[2][2]);
            return;
        };

        int[][] bi = a;
        System.out.println("a an der Stelle 0,1 ist " + a[0][1]);
        if (up(a)) {
            for (int i = 1; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i > 0 && a[i - 1][j] == 0) {
                        int zwischen = a[i][j];
                        a[i][j] = 0;
                        a[i - 1][j] = zwischen;
                        System.out.println("Jetzt in up");
                        if (korb.indexOf(a) == -1) {
                            System.out.println("Wird hinzugefügt?");
                            System.out.println("a an der Stelle 1,1 ist " + a[1][1]);

                            korb.add(a);
                            rekursion(z, a, korb);
                        } 
                    }
                }
            }
        }

        bi = a;
        if (down(a)) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i > 0 && a[i + 1][j] == 0) {
                        int zwischen = a[i][j];
                        a[i][j] = 0;
                        a[i + 1][j] = zwischen;
                        System.out.println("a an der Stelle 1,1 ist " + a[1][1]);

                        if (korb.indexOf(a) == -1) {
                            System.out.println("Wird hinzugefügt? down");

                            korb.add(a);
                            rekursion(z, a, korb);
                        } 
                    }
                }
            }

        }

        bi = a;
        if (left(a)) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 2; j++) {
                    if (j < 2 && a[i][j] == 0) {
                        int zwischen = a[i][j + 1];
                        a[i][j] = zwischen;
                        a[i][j + 1] = 0;
                        System.out.println("a an der Stelle 1,1 ist " + a[1][1]);

                        if (korb.indexOf(a) == -1) {
                            System.out.println("Wird hinzugefügt? left");

                            korb.add(a);
                            rekursion(z, a, korb);
                        } 
                    }
                }
            }

        }

        
        if (right(a)) {
            for (int i = 0; i < 3; i++) {
                for (int j = 1; j < 3; j++) {
                    if (j > 0 && a[i][j] == 0) {
                        int zwischen = a[i][j - 1];
                        a[i][j] = zwischen;
                        a[i][j - 1] = 0;
                        System.out.println("a an der Stelle 1,1 ist " + a[1][1]);

                        if (korb.indexOf(a) == -1) {
                            System.out.println("Wird hinzugefügt? right");

                            korb.add(a);
                            rekursion(z, a, korb);
                        } 
                    }
                }
            }

        }

    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        FU_Hagen p = new FU_Hagen();
        ArrayList<int[][]> a_korb = new ArrayList<int[][]>();
        p.starter(p.ziel, p.ausgang);
        for (int[][] ausgabe : p.resultat) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    System.out.print(ausgabe[i][j] + " ");
                }
                System.out.println("");
            }
            System.out.println("___________________");
        }
    }

}

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Haevelin: 12.10.2019 17:10.

12.10.2019 17:09 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Neunerpuzzle