Springer Problem - Schach

[Tjeri]

Ich hab meinen Code soweit fertig, funktioniert alles und so und ich kann einfach den Fehler nicht finden.
Helft mir pls

package SpringerProblem;

public class Loesung {

        public static int[][] verlauf = new int[64][2];
        public static int[] gemachterZug = new int[64];
        public static boolean[][] schachbrett = new boolean[8][8];
        public static int[][] moeglicheZuege = new int[8][2];
        public static int[] zug = new int[2];
        public static int x = 0;
        public static int y = 0;
        public static int dummy = 0;
        public static boolean zugGefunden = false;

        public static void main(String[] args) {
                ZuegeFuellen();

                verlauf[x][0] = 0;
                verlauf[x][1] = 0;
                schachbrett[0][0] = true;

                for (x = 1; x < 64; x++) {
                        zugGefunden = false;
                        while (!zugGefunden) {
                                for (y = dummy; y < 8; y++) {
                                        zug[0] = moeglicheZuege[y][0];
                                        zug[1] = moeglicheZuege[y][1];

                                        if (0 <= verlauf[x - 1][0] + zug[0]
                                                        && verlauf[x - 1][0] + zug[0] < 8
                                                        && 0 <= verlauf[x - 1][1] + zug[1]
                                                        && verlauf[x - 1][1] + zug[1] < 8
                                                        && !schachbrett[verlauf[x - 1][0] + zug[0]][verlauf[x - 1][1]
                                                                        + zug[1]]) {
                                                verlauf[x][0] = verlauf[x - 1][0] + zug[0];
                                                verlauf[x][1] = verlauf[x - 1][1] + zug[1];
                                                gemachterZug[x] = y;
                                                schachbrett[verlauf[x][0]][verlauf[x][1]] = true;
                                                zugGefunden = true;
                                                dummy = 0;
                                                System.out.println(x + " - (" + verlauf[x][0]+"|" + verlauf[x][1] + ") - " + gemachterZug[x]);
                                                break;
                                        }

                                }
                                if (!zugGefunden) {
                                        EinenZugZurueck();
                                }

                        }

                }

                System.out.println("Beendet.");

        }

        private static void EinenZugZurueck() {
                schachbrett[verlauf[x-1][0]][verlauf[x-1][1]] = false;
                dummy = gemachterZug[x-1] + 1;
                verlauf[x][0] = 0;
                verlauf[x][1] = 0;
                x = x - 1;

        }

        private static void ZuegeFuellen() {
                moeglicheZuege[0][0] = 1;
                moeglicheZuege[0][1] = 2;
                moeglicheZuege[1][0] = -1;
                moeglicheZuege[1][1] = 2;
                moeglicheZuege[2][0] = 1;
                moeglicheZuege[2][1] = -2;
                moeglicheZuege[3][0] = -1;
                moeglicheZuege[3][1] = -2;
                moeglicheZuege[4][0] = 2;
                moeglicheZuege[4][1] = 1;
                moeglicheZuege[5][0] = 2;
                moeglicheZuege[5][1] = -1;
                moeglicheZuege[6][0] = -2;
                moeglicheZuege[6][1] = 1;
                moeglicheZuege[7][0] = -2;
                moeglicheZuege[7][1] = -1;

        }

}

 

[Marco13]

Was funktioniert denn nicht? (Dass das u.U. ein paar Milliarden Jahre dauert, bis er fertig ist, weißt du? (Das mit dem "ein paar Milliarden Jahre" war keine Floskel, sowas kann wirklich so lange dauern... Abhilfe schafft da die Warnsdorff-Heuristik....))

 

[Tjeri]

Was verstehst du denn unter lange Rechenzeit?
selbst wenn ich den mal 10-15 minuten laufen lasse krieg ich keine ergebnis...

 

[Marco13]

So ein Problem mit normalem Backtracking zu lösen kann auf einem modernen Computer etliche Milliarden Jahre dauern. Das ist kein Wirz, keine Floskel und keine Übertreibung. Um zu testen, ob es grundsätzlich funktioniert könntest du es an einem kleineren Spielbrett testen.

Mit der Warnsdorff-Heuristik schafft man das aber innerhalb kürzseter Zeit, auch für deutlich größere Bretter.

 

[Painii]

Ich habs in der Uni auch mal gemacht, da hat es für ein 5x5 Brett schon mehrere Stunden gedauert.

Wenns nur so ne Übungsaufgabe ist versuch es mit kleinen Brettern zu vergleichen (3x3 und 4x4 sollte noch gehen), und bei den größeren kannst du nur hoffen dass du es richtig implementiert hast.

Nur weil das Problem in endlicher Zeit lösbar ist heisst es eben nicht dass wir die Zeit erleben wo das gelöst ist.