Hi,
ich möchte das Spiel Peg programmieren. es scheitert aber daran ein rekursives Backtracking zu erstellen. Im Moment ist es so das das Feld nur zum Teil gelöst wird, das Programm aber dann aufhört weiterzurechnen, was daran liegt das er keinen Zug zurückgeht um einen anderern auszuprobieren.
Meine Frage ist nun wie muss ich die loese Methode verändern damit er wenn er keinen Zug mehr gehen kann dann einen zurückgeht und einen anderen ausprobiert?
Vielen Dank im Voraus
cookiiee
ich möchte das Spiel Peg programmieren. es scheitert aber daran ein rekursives Backtracking zu erstellen. Im Moment ist es so das das Feld nur zum Teil gelöst wird, das Programm aber dann aufhört weiterzurechnen, was daran liegt das er keinen Zug zurückgeht um einen anderern auszuprobieren.
Java:
import java.awt.*;
import java.awt.Image;
import java.awt.Toolkit;
import java.util.ArrayList;
import java.util.Collections;
import javax.swing.*;
public class Kreuzfeld2 {
static int[] feld = new int[49];
public static ArrayList<Zug> züge = new ArrayList<Zug>();
public static int[][] loesung = new int[100][49];
public static int[][] zeichne = new int [32][49];
public static int GemachteZüge = -1;
public class Zug implements Comparable<Zug> {
int x;
int y;
int z;
public Zug(int x, int y, int z) {
super();
this.x = x;
this.y = y;
this.z = z;
}
@Override
public int compareTo(Zug z) {
return (z.x - x) * 100 + (z.y - y);
}
}
public static void main(String[] args) {
new Kreuzfeld2();
}
public Kreuzfeld2() {
feldInit();
gueltigeZuege();
Collections.sort(züge);
zeichnefeld(feld);
loese(steinAnzahlBestimmen());
System.out.println("--- Fertig ---");
}
private int steinAnzahlBestimmen() {
int s = 0;
for (int i = 0; i < 49; i++) {
if (feld[i] == 1) s++;
}
return s;
}
public void gueltigeZuege() {
int[] nachuntenlist = { 2, 3, 4, 9, 10, 11, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25, 30, 31, 32 };
int[] nachrechtslist = { 2, 9, 14, 15, 16, 17, 18, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 37, 44 };
int[] nachobenlist = { 16, 17, 18, 23, 24, 25, 28, 29, 30, 31, 32, 33, 34, 37, 38, 39, 44, 45, 46 };
int[] nachlinkslist = { 4, 11, 16, 17, 18, 19, 20, 23, 24, 25, 26, 27, 30, 31, 32, 33, 34, 39, 46 };
int[] nachuntenlinkslist = { 3, 4, 9, 10, 11, 16, 17, 18, 19, 20, 25, 26, 27, 32, 33};
int[] nachobenrechtslist = {15, 16, 21, 22, 23, 28, 29, 30, 31, 32, 37, 38, 39, 44, 45};
int[] nachuntenrechtslist = {2, 3, 9, 10, 11, 14, 15, 16, 17, 18, 21, 22, 23, 29, 30};
int[] nachobenlinkslist = {18, 19, 25, 26, 27, 30, 31, 32, 33, 34, 37, 38, 39, 45, 46};
for(int i : nachobenlinkslist) {
züge.add(new Zug(i, i - 8, i -16));
}
for (int i : nachuntenrechtslist) {
züge.add(new Zug(i, i + 8, i + 16));
}
for (int i : nachuntenlinkslist) {
züge.add(new Zug(i, i + 6, i + 12));
}
for (int i : nachobenrechtslist) {
züge.add(new Zug(i, i - 6, i - 12));
}
for (int i : nachrechtslist) {
züge.add(new Zug(i, i + 1, i + 2));
}
for (int i : nachlinkslist) {
züge.add(new Zug(i, i - 1, i - 2));
}
for (int i : nachuntenlist) {
züge.add(new Zug(i, i + 7, i + 14));
}
for (int i : nachobenlist) {
züge.add(new Zug(i, i - 7, i - 14));
}
}
private void loese(int steine) {
if (steine == 1) if (feld[30] == 1) {
for (int i = 32; i > 1; i--)
if (GemachteZüge < 31) {
zeichnefeld(loesung[i]);
}
}
for (Zug zug : züge) {
if (feld[zug.x] == 1) if (feld[zug.y] == 1) if (feld[zug.z] == 0) if(feld[zug.y] != loesung[zug.y][steine + 1] ) {
feld[zug.x] = 0;
feld[zug.y] = 0;
feld[zug.z] = 1;
System.arraycopy(feld, 0, loesung[steine], 0, feld.length);
loese(steine - 1);
feld[zug.x] = 1;
feld[zug.y] = 1;
feld[zug.z] = 0;
}
}
}
private static void zeichnefeld(int[] f) {
GemachteZüge++;
System.out.println();
for (int i = 0; i < 49; i++) {
if (i % 7 == 0) System.out.println();
System.out.print((f[i] == 1) ? "x" : (f[i] == 0 ? "o" : " "));
}
System.out.println();
System.out.println(GemachteZüge);
for (int i = 0; i < 49; i++) {
zeichne[GemachteZüge][i]= f[i];
}
}
public void feldInit() {
for (int i = 0; i < 49; i++)
feld[i] = -1;
feld[2] = 1;
feld[3] = 1;
feld[4] = 1;
feld[9] = 1;
feld[10] = 1;
feld[11] = 1;
feld[14] = 1;
feld[15] = 1;
feld[16] = 1;
feld[17] = 1;
feld[18] = 1;
feld[19] = 1;
feld[20] = 1;
feld[21] = 1;
feld[22] = 1;
feld[23] = 1;
feld[24] = 1;
feld[25] = 1;
feld[26] = 1;
feld[27] = 1;
feld[28] = 1;
feld[29] = 1;
feld[30] = 0;
feld[31] = 1;
feld[32] = 1;
feld[33] = 1;
feld[34] = 1;
feld[37] = 1;
feld[38] = 1;
feld[39] = 1;
feld[44] = 1;
feld[45] = 1;
feld[46] = 1;
}
}
Meine Frage ist nun wie muss ich die loese Methode verändern damit er wenn er keinen Zug mehr gehen kann dann einen zurückgeht und einen anderen ausprobiert?
Vielen Dank im Voraus
cookiiee