Problem mit dem so genannten SpringerProblem

[DPFarin]

Joar moin,

ich habe ein Problem mit dem oben genanneten Problem...

Die aufgabe die zu Lösen ist ist einfach .
Es geht um den Springer beim Schach... Er soll auf jedes Feld genau einmal Springen. und darf auch jedes nur einmal berühren... Das habe ich auch gelöst... Quellcode siehe unten...
Aber ich soll es auch schaffen, das ich einen Endpunkt angebe... Sprich der Springer soll auf jedes Feld 1 mal springen und halt mit dem letzen Sprung auf den Endpunkt laden... ( wenn ihr das zu hause testen wollt nehmt nen 5*5 Feld anstatt nen 8*8 )...

wäre für hilfe dankbar

mfg Farin

So hier mal mein Quellcode von meiner SpringerKlasse

public class SpringerProblem {
	int n = 8;

	int[][] meinFeld = new int[n][n];

	int xKord[] = { 2, 2, -2, -2, 1, 1, -1, -1 };

	int yKord[] = { 1, -1, 1, -1, 2, -2, 2, -2 };

	public boolean jump(int nummer, int x, int y) {
		int zug = 0;
		int newx, newy;
		boolean loesung;

		do {
			zug++;
			loesung = false;
			newx = x + xKord[zug - 1];
			newy = y + yKord[zug - 1];

			if (newx >= 0 && newx < n && newy >= 0 && newy < n) {
				if (meinFeld[newx][newy] == 0) {
					meinFeld[newx][newy] = nummer;
					if (nummer < (n * n)) {
						loesung = jump(nummer + 1, newx, newy);
						if (loesung == false) {
							meinFeld[newx][newy] = 0;
						}
					} else {
						loesung = true;
						meineTestAusgabe();
					}
				}
			}

		} while ((loesung == false) && (zug < 8));
		return loesung;

	}

	public void meineTestAusgabe() {
		for (int g = 0; g < n * n; g++) {
			for (int j = 0; j < meinFeld.length; j++) {
				for (int i = 0; i < meinFeld.length; i++) {
					if(meinFeld[i][j] == g){
						System.out.println("P (" +i +" / " + j + ")" );
					}
				}
			}
		}
	}
}

und meine HauptMethode

	public class HauptSpringerProblem {

	public static void main(String args[]) {

		SpringerProblem s1 = new SpringerProblem();
		// Der Startpunkt
		int anfangx = 2;
		int anfangy = 2;
		// Das erste Feld den wert 1 zuweisen
		s1.meinFeld[anfangx][anfangy] = 1;
		// Starte das "suchen" der richtigen Lösung
		s1.jump(2, anfangx, anfangy);
		System.out.print("Programm Ende");
		
	}
	public static void meineTestAusgabe() {


	}
}

 

[DPFarin]

Hier ist das wo ich es versucht habe einzubauen aber das geht irgentwie nicht

public class SpringerProblem {
	int n = 5;

	int[][] meinFeld = new int[n][n];

	int xKord[] = { 2, 2, -2, -2, 1, 1, -1, -1 };

	int yKord[] = { 1, -1, 1, -1, 2, -2, 2, -2 };

	boolean endan = true;

	
	public boolean jump(int nummer, int x, int y) {
		int zug = 0;
		int newx, newy;
		boolean loesung;

		do {
			zug++;
			loesung = false;
			newx = x + xKord[zug - 1];
			newy = y + yKord[zug - 1];

			if (newx >= 0 && newx < n && newy >= 0 && newy < n) {
				if (meinFeld[newx][newy] == 0) {
					meinFeld[newx][newy] = nummer;
					if (nummer < (n * n -1)) {
						loesung = jump(nummer + 1, newx, newy);
						if (loesung == false) {
							meinFeld[newx][newy] = 0;
						}
					} else {

						if (endan = true) {
							for (int i = 0; i < 8; i++)
								if ((newx + xKord[i]) >= 0
										&& (newx + xKord[i]) < n
										&& (newy + yKord[i]) >= 0
										&& (newy + yKord[i]) < n) {
									if (meinFeld[newx + xKord[i]][newy
											+ yKord[i]] == n * n) {
										loesung = true;
										meineTestAusgabe();
										i=8;
									} else {
										loesung = false;
									}
								}
						}
					}
				}
			}
		} while ((loesung == false) && (zug < 8));
		return loesung;

	}

	public void meineTestAusgabe() {
		for (int g = 0; g < n * n; g++) {
			for (int j = 0; j < meinFeld.length; j++) {
				for (int i = 0; i < meinFeld.length; i++) {
					if (meinFeld[i][j] == g) {
						System.out.println("P (" + i + " / " + j + ")");
					}
				}
			}
		}
	}
}

mfg Farin

PS: Brauch dringen Hilfe ((((

[/code]

 

[Marco13]

Hm. Ich würde einfach Abfragen, ob das letzte Feld das ist, wo man aufhören wollte. Ansonsten hat man noch keine Lösung, und muß weitersuchen.

Nur ist das nicht ganz trivial: Bist du sicher, dass man IMMER auf dem gewünschten Feld aufhören KANN? Ich glaube nämlich nicht.... ???:L

(Wenn man z.B. als Ziel 4,2 eingibt, findet er keine Lösung...)

public class HauptSpringerProblem {

   public static void main(String args[]) {

      SpringerProblem s1 = new SpringerProblem();
      // Der Startpunkt
      int anfangx = 2;
      int anfangy = 2;
      // Das erste Feld den wert 1 zuweisen
      s1.meinFeld[anfangx][anfangy] = 1;
      // Starte das "suchen" der richtigen Lösung
      s1.jump(2, anfangx, anfangy);
      System.out.print("Programm Ende");

   }
   public static void meineTestAusgabe() {


   }
}

class SpringerProblem {
   int n = 5;

   int targetX = 3;
   int targetY = 2;

   int[][] meinFeld = new int[n][n];

   int xKord[] = { 2, 2, -2, -2, 1, 1, -1, -1 };

   int yKord[] = { 1, -1, 1, -1, 2, -2, 2, -2 };

   public boolean jump(int nummer, int x, int y) {
      int zug = 0;
      int newx, newy;
      boolean loesung;

      //meineAndereTestAusgabe(nummer);

      do {
         zug++;
         loesung = false;
         newx = x + xKord[zug - 1];
         newy = y + yKord[zug - 1];

         if (newx >= 0 && newx < n && newy >= 0 && newy < n) {
            if (meinFeld[newx][newy] == 0) {
               meinFeld[newx][newy] = nummer;
               if (nummer < (n * n)) {
                  loesung = jump(nummer + 1, newx, newy);
                  if (loesung == false) {
                     meinFeld[newx][newy] = 0;
                  }
               } else {
                  if (x == targetX && y == targetY)
                  {
                      loesung = true;
                      meineTestAusgabe();
                  }
                  if (loesung == false) {
                     meinFeld[newx][newy] = 0;
                  }
               }
            }
         }

      } while ((loesung == false) && (zug < 8));
      return loesung;

   }

   public void meineAndereTestAusgabe(int nummer)
   {
       System.out.println("---------------- "+nummer);
         for (int j = 0; j < meinFeld.length; j++) {
            for (int i = 0; i < meinFeld.length; i++) {
               if(meinFeld[i][j] == 0)
               {
                  System.out.print(" . ");
               }
               else
               {
                   System.out.printf(" %2d", meinFeld[i][j]);
               }
            }
            System.out.println("");
        }
        System.out.println("");
   }

   public void meineTestAusgabe() {
      for (int g = 0; g < n * n; g++) {
         for (int j = 0; j < meinFeld.length; j++) {
            for (int i = 0; i < meinFeld.length; i++) {
               if(meinFeld[i][j] == g){
                  System.out.println("P (" +i +" / " + j + ")" );
               }
            }
         }
      }
   }
}

Ansonsten noch ein Tipp: Such' mal im Netz nach "Warnsdorf Heuristik" (oder Heuristic). Die ist relativ leicht zu implementieren, und damit kann man nicht nur 8x8, sondern auch noch VIEL größere Bretter in kürzester Zeit lösen.

 

[DPFarin]

Ja diese lösung gibt mir aber nur eine lösung... Wenn man das mit dem endpunkt macht, muss es wie bei dir sein wenn das wirklich gehen sollte bin ich dir sehr sehr sehr dankbar

und ja bei 4,2 gibts keine lösung... wenn du auf einen weißen Feld anfängst musst du auf einen schwarzen Feld enden ( aufs schachfeld bezogen ), ansonsten gibt es keine Lösung.


Aber danke für deine Hilfe

mfg Farin