Backtracking - Labyrinth/Irrgarten

[NikeAir22]

Hey Leute,

ich wollte ein Programm schreiben, dass folgendes Problem mit Backtracking löst:

Ich wollte als erstes diesen Irrgarten aus einer TXT-Datei einlesen:


(Bitte aus der PDF entnehmen)


Die Zeichen „ -„ und „ |“ stellen die Mauern dar.

Der Code dafür ist von der Uni wie folgt gegeben:

import java.io.*;
import java.util.Scanner;

public class Test {

    public static void main(String args[]) {
        try {
            FileInputStream file = new FileInputStream("a.txt");
            Scanner s = new Scanner(file);
            while (s.hasNextLine()) {
                String line = s.nextLine();
                System.out.println(line);
            }
        file.close();
        } catch (IOException e) {
            System.out.println("Fehler");
        }
    }
}

Am Ende soll so etwas herauskommen:


(Bitte aus der PDF entnehmen)


Ich habe mir überlegt, dass ich als erstes die Klasse „Weg“ anlege und dann in etwa so vorgehen will:

- Gestartet wird bei „S“

- Danach soll ein Punkt entweder nach links, rechts, oben oder unten gesetzt werden, je nachdem, wo keine Mauer ist. Der Pointer soll an die Stelle, wo der Punkt gesetzt wird.

- Das soll er solange machen, bis er entweder bei „Z“ ist, oder an einer Stelle landet, wo eine Sackgasse ist

- Wenn er „Z“ erreicht hat, soll das Programm beendet werden.

- Wenn er an einer Stelle landet, wo in drei Richtungen eine Mauer ist und in einer Richtung ein Punkt, soll er den aktuellen Punkt mit einem „x“ überschreiben und die Visibility auf false setzen. „X“-Stellen sollen wie Mauern betrachtet werden. Wenn es keinen Weg von „S“ nach „Z“ gibt, soll er mir eine entsprechende Meldung ausgeben.


Aber: Wie sage ich dem Programm sinnvoll, wo es lang gehen soll? Setze ich da die Befehle „links“ „rechts“, „hoch“ und „runter“ auf random, oder ist das Schwachsinn?
Und was sagt ihr zu meiner geplanten Vorgehensweise? Sieht das okay aus? Ich sende euch anbei auch mal die PDF-Datei mit der Aufgabe (Letzte Aufgabe). Außerdem hänge ich noch ein Bild an, welches das Labyrinth noch mal in etwa zeigt (ich finde, dass man bei der TXT-Datei teilweise nur schwer erkennt, wo eine Mauer ist und wo man lang kann):

http://www.ips.tu-braunschweig.de/struckmann/prog12/blatt07.pdf

http://img547.imageshack.us/img547/7804/backtracking.jpg



Ich wäre für jede Hilfe dankbrar

Viele Grüße
NikeAir22

 

[Timothy Truckle]

Aber: Wie sage ich dem Programm sinnvoll, wo es lang gehen soll? Setze ich da die Befehle „links“ „rechts“, „hoch“ und „runter“ auf random, oder ist das Schwachsinn?

Es ist Schwachsinn.

Die Regeln im Irrgarten (nicht im Labyrinth, da gibt es exakt einenen Weg durch) ist:
- biege an Kreuzungen immer in die selbe Richtung ab (aus Sicht der Bewegungsrichtung!).
- drehe am Ende einer Sackgasse um.

Falls Dein Irrgarten Schleifen enthält muss man diese Lösung noch erweitern.

bye
TT

 

[AndiE]

Das soll doch mit Backtracking gelöst werden.
Ich habe das bei "Wiki" so verstanden, dass der Spieler z.B. die Bewegungsrichtungen (N,W,S,O) hat, und als Ergebnis für die Bewältigung der Strecke von S bis Z ein String wie "NNNSSOOWNNS" herauskommt. Der ergibt sich aus dem Suchbaum, den du anlegen musst, weil er nach dem Artikel wesentlicher Bestandteil des Backtracking- Algorithmus ist, da du mit seiner Hilfe die "Trial and Error"-Funktionen durchführst.
Auch soll Backtracking ein typisches Beispiel für rekursiv, eine Funktion ruft sich selbst auf, sein.

 

[Templarthelast]

Ich würde eine Queue nehmen und jedes Mal wenn ich an einer Kreuzung vorbeikomme, mir die Position und Richtung der Kreuzung in die Queue schreiben. Falls man jetzt auf seinem Weg zu einem Ende gelangt, holt man sich den nächsten Weg aus der Queue, bis man am Ziel ist.

 

[NikeAir22]

So, ich habe jetzt erst mal ein Problem dabei, die Zeichenkette als Matrix abzuspeichern. Ich kann es einlesen und ausgeben, aber ich würde es gerne in einer char Matrix ablegen.:

import java.io.*;
import java.util.Scanner;
public class Test {

	public static void main(String args[]) {
		try {
			

			FileInputStream file = new FileInputStream("a.txt");
			Scanner s = new Scanner(file);
			while (s.hasNextLine()) {
				String line = s.nextLine();
				char maze[][] = new char[][]{



					???????????????????


				};

				
				
				System.out.println(line);
				}
			file.close();
			} catch (IOException e) {
				System.out.println("Fehler");
				}
			}
	}

Aber was schreibe ich jetzt in die Fragezeichen rein? Jedes Zeichen soll als ein Elemant der Matrix genommen werden. Der Irrgarten sieht so aus:

---------------
|S    |  |    |
| --- | ----  |
|  |  |     | |
|  |  |---- |R|
|   | |     | |
| |   |  |  | |
| | |    |    |
---------------

Es sieht hier nur etwas merkwürdig aus, weil die Schriftart hier proportional ist. Das passt aber
[edit SlaterB: mit Code-Tags besser sonst kann man auch andere Zeichen als Leerzeichen nehmen ]

 

[SlaterB]

direkt definieren kannst du das gar nicht,
der Dateiinhalt ist unbekannt, oder ist es das Beispiel darunter direkt als Text?
du musst jede Zeile einlesen, aufsplitten, bzw. das toCharArray() als ein Array im 2D-Array einsetzen

 

[NikeAir22]

Oh man...jetzt wirds echt peinlich...ich wollte es mir leicht machen und habs jetzt einfach so gemacht:

public class Test {

	public static void main(String args[]) {
		char maze[][] = new char[][]{
			{'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-'},
			{'|', 'S', ' ', ' ', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', ' ', ' ', '|'},
			{'|', ' ', '-', '-', '-', ' ', '|', ' ', '-', '-', '-', '-', ' ', ' ', '|'},
			{'|', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', ' ', ' ', ' ', '|', ' ', '|'},
			{'|', ' ', ' ', '|', ' ', ' ', '|', '-', '-', '-', '-', ' ', '|', 'R', '|'},
			{'|', ' ', ' ', ' ', '|', ' ', '|', ' ', ' ', ' ', ' ', ' ', '|', ' ', '|'},
			{'|', ' ', '|', ' ', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|', ' ', '|'},
			{'|', ' ', '|', ' ', '|', ' ', ' ', ' ', ' ', '|', ' ', ' ', ' ', ' ', '|'},
			{'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-'},
			
		
		};
		
		System.out.println(maze);
				
	}
}

aber die Ausgabe sieht wie folgt aus:

[[C@1befab0

was mache ich falsch?

 

[SlaterB]

du nimmst an dass was anderes herauskommt, hast aber dazu keine Veranlassung,
ein Array ist nicht so gnädig mitzumachen,
auch bei List & Co, bei allem über einfachen int und String hinaus, nichts pauschal erwarten,
auch wenn List & Co. etwas freundlicher sind

Arrays.deepToString(maze) ginge am ehesten, wird dir aber kaum gefallen,
-> mit Schleifen selber arbeiten

'Ausgabe Array Java' kann man auch in Suchmaschinen eintippen

 

[SlaterB]

        char maze[][] = new char[][]
            {
                "- - - - - - - - - - - - - - -".toCharArray(),
                "| S         |     |         |".toCharArray(),
                "|   - - -   |   - - - -     |".toCharArray(),
                "|     |     |           |   |".toCharArray(),
                "|     |     | - - - -   | R |".toCharArray(),
                "|       |   |           |   |".toCharArray(),
                "|   |       |     |     |   |".toCharArray(),
                "|   |   |         |         |".toCharArray(),
                "- - - - - - - - - - - - - - -".toCharArray()
            };

wäre übrigens einfacher, lesbarer und kürzer,
schlimm diese ganze Syntax dazwischen,

es reicht gar, nur die Strings zu schreiben und per Methode umzuwandeln

siehe zuletzt einen ähnlichen Hinweis von mir
http://www.java-forum.org/allgemeine-java-themen/146830-aes-32byte-key.html#post981875


mehrzeilige Strings gibt es in Java freilich nicht
Java multiline string - Stack Overflow

 

[NikeAir22]

Okay. Mein Code sieht gerade so aus:

package aufgabe47;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;

public class Maze {
	
	public final char START = 'S';
	public final char FINISH = 'Z';
	public final char WALL1 = '|';
	public final char WALL2 = '-';
	public char besucht = 'B';
	public char frei = ' ';
	public char step = '.';
	
	protected char[][] maze;
	protected int[] startPoint;
	protected int[] endPoint;
	public int up = y-1;
	public int down = y+1;
	public int left = x-1;
	public int right = x+1;
	
	protected int[] currentPos = this.startPoint;
	protected ArrayList<int[]> history = new ArrayList<int[]>();
	
	public static void main(String[] args)
	{
		new Maze("testMaze.txt");
	}
	
	public Maze(String mazeFile)
	{
		this.load(mazeFile);
		this.solve();
	}
	
	protected void solve()
	{
		currentPos = startPoint;
		while (currentPos!=endPoint);{
			java.util.Random random = new java.util.Random();
			int bar = random.nextInt(4);
			
			if (bar == 0){
				currentPos = currentPos + up;
			}
			else if (bar == 1){
				currentPos = currentPos + down;
			}
			else if (bar == 2){
				currentPos = currentPos + left;
			}
			else if (bar == 3){
				currentPos = currentPos + right;
			}
			
			if (currentPos == WALL1 || WALL2 || besucht){
				//zurück zur alten Position
			}
			else if (currentPos == frei){
				add.Step;
			}
			
			
			if (currentPos + up && currentPos + down && currentPos + left && currentPos + right == WALL1 || WALL2 || == besucht || ==step){
				currentPos = besucht //Bei Sackgasse punkt durch B ersetzen und einen Schritt
				//zurück.
			}
			
			
		}
		
		
		
	}
	
	
	protected int[] getNextPos(int[] currentPos)
	{
		
		int[] ret = {0,0};
		return ret;
	}

	protected void printMaze()
	{
		for(int i=0; i<this.maze.length; i++) {
			for(int j=0;j<this.maze[i].length; j++) {
				System.out.print(this.maze[i][j]);
			}
			System.out.print("\n");
		}
	}
	
	protected void setStartPoint(int x, int y) throws MazeException
	{
		
		if(this.startPoint == null) {
			this.startPoint = new int[2];
			this.startPoint[0] = x;
			this.startPoint[1] = y;
			System.out.println("StartPoint fount at (" + x + "/" + y + ")");
		} else {
			throw new MazeException("There must be only one starting point (" + x + "/" + y +")");
		}
	}
	
	protected void setEndPoint(int x, int y) throws MazeException
	{
		
		if(this.endPoint == null) {
			this.endPoint = new int[2];
			this.endPoint[0] = x;
			this.endPoint[1] = y;
			System.out.println("EndPoint fount at (" + x + "/" + y + ")");
		} else {
			throw new MazeException("There must be only one end point (" + x + "/" + y +")");
		}
	}
	
	protected void load(String fileName)
	{
		FileReader file = null;
		BufferedReader in = null;
		try {
			file = new FileReader(fileName);
			in = new BufferedReader(file);
			
			String line;
			ArrayList<char[]> liste = new ArrayList<char[]>();
			
			// list all rows
			for(int i=0; (line = in.readLine()) != null; i++) {
				int lineLength = line.length();
				char[] buffer = new char[lineLength];
				
				// list all columns
				for(int j = 0; j<lineLength; j++) {
					char curr = line.charAt(j);
					if(curr == this.START) {
						this.setStartPoint(i,j);
					} else if(curr == this.FINISH){
						this.setEndPoint(i,j);
					}
					buffer[j] = curr;
				}
				
				liste.add(buffer);
				
				if(lineLength != line.length()) {
					System.out.println("Alle Zeilen müssen gleich lang sein!");
					System.exit(0);
				}
				lineLength = line.length();
			}
			
			if(this.startPoint == null || this.endPoint == null) {
				throw new MazeException("There must be a start and a finish");
			}
			
			this.maze = new char[liste.size()][];
			this.maze = liste.toArray(this.maze);
			
		} catch(Exception e) {
			System.err.println("Fehler: " + e.getMessage());
			e.printStackTrace();
			System.exit(0);
		} finally {
			// close file-handle in any case
			try { file.close(); } catch(Exception e) {}
			try { in.close(); } catch(Exception e) {}
		}
	}
}

class MazeException extends RuntimeException {

	public MazeException(String string) {
		super(string);
	}
}

left, right, up und down sind hier falsch, das ist mir klar. Und Solve ist auch totaler Schwachsinn. Aber ist meine Idee denn schon mal richtig?

 

[Timothy Truckle]

Ich sags gern nochmal: zufällige Richtungsänderungen führen nicht zum Ausgang, erst recht nicht, wenn Du Dir nicht merkst (und nicht prüfst) ob du einen Weg schon mal genommen hast. Ist aber wahrscheinlich sehr unterhaltsam beim Zuschauen... ;o)

bye
TT

 

[NikeAir22]

Aber deswegen setze ich ja die 'B' Markierungen. Die werden ja auch als Wand angesehen und da gehe ich dann ja auch nicht mehr lang. So müsste er ja gezwungenermaßen irgendwann beim Ziel landen, falls es einen Weg gibt

 

[NikeAir22]

So okay....ich stecke immer noch an der Stelle fest, an der ich die Textdatei in ein mehrdimensionales Array einlesen will. Mein Code sieht mittlerweile so aus:

import java.io.*;
import java.util.Scanner;
 
 
public class Test {
	public static void main(String args[]) {
		try {
			char arr[][];
			
			FileInputStream file = new FileInputStream("a.txt");
			Scanner s = new Scanner(file);
			while (s.hasNextLine()) {
				 String line = s.nextLine();
				for (int i=0 ;i<=line.length(); i++){
					int k=0;
					arr[k][i] = line.charAt(i);
					k ++;
				}
				
			}
			file.close();
		} catch (IOException e) {
			System.out.println("Fehler");
		}
	}
}

Ich bekomme aber immer einen Fehler ausgespuckt...was mache ich falsch...könnte mir vielleicht jemand eine kleine Korrektur oder so zeigen? Wäre echt nett

 

[Firephoenix]

Zeile 17 sowas wie OutOfBounds?
For-Schleifen die von 0 bis <= länge von irgendwas gehen und auf indexwerte zugreifen sind in 99% der Fälle falsch.
entweder von 1 bis <= (selten), von länge-1 bis >= 0 (auch selten) oder von 0 bis <= länge-1 (häufiger), oder generell von 0 bis < länge (würde hier passen).

[OT]Warum schaffen es eigentlich sowenig Leute sich vernünftig auszdrücken? "Ich habe einen Fehler", "Das geht nicht", "Es gibt da ein Problem", ... Lauter so Nullsätze die man ersetzen könnte durch "Ich will, dass du mir jedes Detail einzeln mit der Kneifzange aus der Nase ziehst weil du nicht in der Lage bist deine Glaskugel zu benutzen um zu erraten wo das Problem liegt"[/OT]

Gruß

 

[Bernd Hohmann]

ich wollte ein Programm schreiben, dass folgendes Problem mit Backtracking löst:

Letztendlich ist jeder Algorithmus zur Lösung eines Irrgartens ein Backtracking.

Suche Dir was aus: https://de.wikipedia.org/wiki/Lösungsalgorithmen_für_Irrgärten

Bernd