Wortjagd

D

dj

Mitglied
Guten Abend,
ich studiere z.Z. Wirtschaftsinformatik (1.Semester) und habe mir für die Semesterferien einige Projekte zum Üben vorgenommen. Ich wollte nun das Spiel Wortjagd (App Store ? ?Wortjagd?) als Konsolenanwendung nachprogrammieren. Dabei gibt es ein 4x4 Spielfeld mit Buchstaben welche zu sinnvollen Wörtern kombiniert werden müssen. Ein Buchstabe darf nur einmal verwendet und nur mit seinen Nachbarn (links, rechts, oben, unten, diagonal) kombiniert werden. Ich habe nun Probleme aus dem Spielfeld die richtigen Wörter herrauszufinden. Programmiert habe ich erstmal die Klasse für das Feld:
Java: 
public class Wortfeld {
	private char [] feld;              //das Spielfeld
	private int pointer;               //aktuelle Position auf dem Spielfeld
	public int [] pointer_temp;
	
	public Wortfeld () {
		
	}
	public Wortfeld (char [] feld) {
		setFeld (feld);
		setPointer (0);
		pointer_temp = new int [10];
	}
	
	public int [] Nachbar () {                   //Gibt die Nachbarn der Aktuellen Position zurück   
		@SuppressWarnings("unused")
		int temp [];
		switch (pointer) {
		case 0: return (temp = new int [] {1,5,4});
		case 1: return (temp = new int [] {0,4,5,6,2});
		case 2: return (temp = new int [] {1,5,6,7,3});
		case 3: return (temp = new int [] {2,6,7});
		case 4: return (temp = new int [] {0,1,5,9,8});
		case 5: return (temp = new int [] {0,1,2,6,10,9,8,4});
		case 6: return (temp = new int [] {1,2,3,7,11,10,9,5});
		case 7: return (temp = new int [] {3,2,6,10,11});
		case 8: return (temp = new int [] {4,5,9,12,13});
		case 9: return (temp = new int [] {4,5,6,10,14,13,12,8});
		case 10: return (temp = new int [] {5,6,7,11,15,14,13,9});
		case 11: return (temp = new int [] {7,6,10,14,15});
		case 12: return (temp = new int [] {8,9,13});
		case 13: return (temp = new int [] {12,8,9,10,14});
		case 14: return (temp = new int [] {13,9,10,11,15});
		case 15: return (temp = new int [] {14,10,11});
		default: return (temp = new int [0]);
		}
	}
	
	public char[] getFeld() {
		return feld;
	}
	public void setFeld(char[] feld) {
		this.feld = feld;
	}
	public int getPointer() {
		return pointer;
	}
	public void setPointer(int pointer) {
		this.pointer = pointer;
	}
	
}

Hier ist mein Versuch des Hauptprogramms:
Java: 
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String [] loesung = new String [] {"rad"};    //Wird Später von einer Textdatei eingelesen
		char [] matrix = new char [] {'r','a','d','h','k','t','h','u','z','p','g','t','h','u','m'}; // Wird später                     //zufällig generiert
		Wortfeld w = new Wortfeld (matrix);
		for (String x : loesung) {
			if (vergl (w,x,0)) System.out.println (x); //Soll erstmal alle Lösungen ausgeben
		}
	}
	public boolean vergl (Wortfeld w, String s, int i) {  
		char [] temp = s.toCharArray();
		int [] x = w.Nachbar();
		if (i == s.length()) {
			return true;
		}
		else {
			if (temp [i] == w.getFeld()[w.getPointer()]) {
				for (int a = 0; a < x.length;a++) {
					if (temp [i+1] == w.getFeld()[x[a]]){
						w.pointer_temp[i] = w.getPointer();
						w.setPointer(x[a]);
						vergl (w,s,i+1);
					}
				}
				w.setPointer(w.pointer_temp[i-1]);
				
			}
		}
	}
}

Wie ihr seht komm ich bei der Funktion vergl welche die Prüfung durchführen soll nicht weiter. Ich weiß es muss rekursiv sein. Habe es auch schon versucht mit dem 8-Damen-Problem zu vergleichen da wir dieses schon in der Uni hatten aber ich komm einfach nicht auf die Lösung.
Wäre um ein paar Tipps sehr dankbar!
 
J

JohannisderKaeufer

Gast
vergl soll einen boolean zurückliefern.

Deshalb muß vergl auch in jedem Zweig deines if-else-Konstrukts entweder ein return true oder return false stehen, sonst passiert da erstmal garnichts.
 
D

dj

Mitglied
Ich weiß. Mein Problem ist, dass ich weiß nicht wie ich den else-Block ausformulieren soll. Das geht irgendwie mit Backtracking aber ich komm nicht auf die Lösung.
 
D

dj

Mitglied
Bin jetzt schon näher an der Lösung, bekomm aber eine stackoverflowerror Exception.
Hier mal meine Funktion:
Java: 
public static boolean vergl (Wortfeld w, String s, int i) {
		char [] temp = s.toCharArray();
		int [] x = w.Nachbar();
		if (i == s.length()) {
			return true;
		}
		else  {
			if (i == 0) {
				for (int te =0; te < pointer_temp.length; te++) {
					pointer_temp [te] = 0;
				}
				for (int l = 0; l <w.getFeld().length; l++) {
					if (w.getFeld()[l] == temp [0]) {
						if (!w.used [l]) {
							w.used [l] = true;
							w.setPointer(l);
							pointer_temp [i] = l;
							vergl (w,s,i+1);
						}
						else {
								w.used [l] = false;
						}
					}
				}
				return false;
			}
			else {
				for (int m = 0; m < x.length; m++) {
					if (temp [i] == w.getFeld()[x[m]]) {
						if (!w.used [x[m]]) {
							w.used [x[m]] = true;
							w.setPointer(x[m]);
							pointer_temp [i] = x[m];
							vergl (w,s,i+1);
						}
					}
					else {
						w.setPointer(pointer_temp [i-1]);
						vergl (w,s,i-1);
					}
				}
				return false;
			}
		}
 
M

Marco13

Top Contributor
Kannst du mal in Worten beschreiben, was die Funktion eigentlich machen soll? (BTW: Das mit dem switch und den arrays ist ziemlich häßlich.. überleg' ggf. mal, ob du dei Rückgaben dort nicht ausrechnen kannst, oder ob du diese Arrays überhaupt in der Form brauchst, oder nicht sowas wie
Java: 
for (int dx=-1; dx<=1; dx++)
{
    for (int dy=-1; dy<=1; dy++)
    {
        int nx = x+dx;
        int ny = y+dy;
        if (isValid(nx, ny)) // Prüfe ob nx,ny gültige Koordinaten sind
        {
            // nx,ny ist ein Nachbar von x,y
        }
    }
}
 
B

BoBoHelp

Gast
Hallo,
ich habe in meinem Archiv ein C++ (min 15 Jahre alt) Code gefunden, der das gleiche (fast) tut. Ich habe es in 20 min. auf Java portiert, es ist nicht 100%ig sauber aber als Vorschlag für mögliche "Möglichkeit" !, vielleicht hilft.

Java: 
//...
String stringMatrix = "xxxxxrxxxxaxxdar";
String sucheNach = "rad";
FieldHandler fieldHandler = new FieldHandler(stringMatrix, sucheNach);
//...

und dann die Klasse
Java: 
import java.util.ArrayList;
import java.util.List;

public class FieldHandler {

	private static final int MATRIX_SIZE = 4;
	private String matrix;
	private String muster;
	private List<Integer> sequenz;

	
	public FieldHandler(String matrix, String muster) {
		this.matrix = matrix;
		this.muster = muster;
	}

	
	private boolean isInMatrix(int fieldId) {
		return ((fieldId >= 0) && (fieldId <= (MATRIX_SIZE * MATRIX_SIZE) - 1));
	}

	
	private int oben(int fieldId) {
		return ((isInMatrix(fieldId - MATRIX_SIZE)) ? (fieldId - MATRIX_SIZE) : -1);
	}

	
	private int unten(int fieldId) {
		return ((isInMatrix(fieldId + MATRIX_SIZE)) ? (fieldId + MATRIX_SIZE) : -1);
	}

	private int links(int fieldId) {
		int result = fieldId - 1;
		result = (Math.abs((Math.abs(fieldId % MATRIX_SIZE)) - (Math.abs((fieldId - 1) % MATRIX_SIZE))) == 1 && result != -1) ? result : -1;
		return (isInMatrix(result) ? result : -1);
	}

	private int rechts(int fieldId) {
		int result = fieldId + 1;
		result = (Math.abs((Math.abs(fieldId % MATRIX_SIZE)) - (Math.abs((fieldId + 1) % MATRIX_SIZE))) == 1 && result != -1) ? result : -1;
		return (isInMatrix(result) ? result : -1);
	}

	private int obenLinks(int fieldId) {
		int result = fieldId - (MATRIX_SIZE + 1);
		result = ((Math.abs(fieldId % MATRIX_SIZE) - Math.abs((fieldId - (MATRIX_SIZE + 1)) % MATRIX_SIZE)) == 1 && result != -1) ? result : -1;
		return (isInMatrix(result) ? result : -1);
	}

	private int obenRechts(int fieldId) {
		int result = fieldId - (MATRIX_SIZE - 1);
		if (result == fieldId) return -1;
		result = (Math.abs((Math.abs(fieldId % MATRIX_SIZE)) - (Math.abs((fieldId - (MATRIX_SIZE - 1)) % MATRIX_SIZE))) == 1 && result != -1) ? result : -1;
		return (isInMatrix(result) ? result : -1);
	}

	private int untenLinks(int fieldId) {
		int result = fieldId + (MATRIX_SIZE - 1);
		result = (Math.abs((Math.abs(fieldId % MATRIX_SIZE)) - (Math.abs((fieldId + (MATRIX_SIZE - 1)) % MATRIX_SIZE))) == 1 && result != -1) ? result : -1;
		return (isInMatrix(result) ? result : -1);
	}

	private int untenRechts(int fieldId) {
		int result = fieldId + (MATRIX_SIZE + 1);
		result = (Math.abs((Math.abs(fieldId % MATRIX_SIZE)) - (Math.abs((fieldId + (MATRIX_SIZE + 1)) % MATRIX_SIZE))) == 1 && result != -1) ? result : -1;
		return (isInMatrix(result) ? result : -1);
	}

	public List<Integer> getNachbarn(int fieldId) {
		List<Integer> result = new ArrayList<Integer>();
		int rc;

		rc = oben(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);

		rc = unten(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);

		rc = rechts(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);

		rc = links(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);

		rc = obenLinks(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);

		rc = untenLinks(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);

		rc = obenRechts(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);

		rc = untenRechts(fieldId);
		if (rc >= 0 && rc != fieldId)
			result.add(rc);
		
		return result;
	}

	
	private List<Integer> getStartsIndex() {
		List<Integer> result = new ArrayList<Integer>();
		int index = -1;
		while ((index = matrix.indexOf(muster.charAt(0), index + 1)) != -1) {
			result.add(index);
		}
		return result;
	}

	
	private void searchIn(int index, int next) {
		List<Integer> nachbarn = getNachbarn(index);
		for (Integer i : nachbarn) {
			if (matrix.charAt(i) == muster.charAt(next)) {
				sequenz.add(i);
				if (sequenz.size()  < muster.length()){
					searchIn(i, next + 1);
					break;
				}else{
					return;
				}
				
			}
		}
	}
	
	
	private void showMatrix() {
		for(int i=0; i<(MATRIX_SIZE*MATRIX_SIZE);i++){
			if(i % MATRIX_SIZE == 0 ) System.out.println();
			System.out.print(matrix.charAt(i) + " ");
		}
		System.out.println();
	}
	
	
	private boolean isValid() {
		return !(matrix.length() != (MATRIX_SIZE * MATRIX_SIZE) || muster.length() > matrix.length());
	}

	
	public void compute() {
		if(!isValid()) {
			System.out.println("ERROR INPUT DATA");
			return;
		}
		List<Integer> indexList = getStartsIndex();
		
		if(indexList.size() == 0) {
			System.out.println("NOT FOUND...");
			return;
		}
		
		showMatrix();
		
		for (Integer index : indexList) {
			sequenz = new ArrayList<Integer>();
			sequenz.add(index);
			searchIn(index, 1);
			if (sequenz.size() == muster.length()) {
				System.out.println(String.format("Muster %s gefunden in :", muster));
				for (Integer j : sequenz) {
					System.out.print(j + ",");
				}
			}
			System.out.println();
		}
	}
}
 
D

dj

Mitglied
Sieht gut aus. Ich habe mitlerweile eine nicht schöne, aber funktionierdende Lösung gefunden. Dies ist die Funktion welche ermittelt ob ein Wort in der Matrix liegt oder nicht:

Java: 
public static boolean vergl (Wortfeld w, String s, int i) {
		char [] temp = s.toCharArray();
		nachbar = w.Nachbar();
		if (i == s.length()) {
			return true;
		}
		else  {
			if (i == 0) {
				for (int te =0; te < pointer_temp.length; te++) {
					pointer_temp [te] = 0;
				}
				for (int l = 0; l <w.getFeld().length; l++) {
					if (w.getFeld()[l] == temp [0]) {
						if (!w.used [l]) {
							zaehler = 0;
							w.used [l] = true;
							w.setPointer(l);
							pointer_temp [zaehler] = l;
							return vergl (w,s,i+1); 
						}
						else {
								w.used [l] = false;
								
						}
					}
					
				}
				return false;
			}
			else { 
				for (int m = 0; m < nachbar.length; m++) { 
					if (temp [i] == w.getFeld()[nachbar[m]]) { 
						if (!w.used [nachbar[m]]) { 
							w.used [nachbar[m]] = true;
							w.setPointer(nachbar[m]);
							zaehler++;
							pointer_temp [zaehler] = nachbar[m];
							return vergl (w,s,i+1);
						}
					}
					else {
						
					}
				}
				if (zaehler >0) zaehler--;
				w.setPointer(pointer_temp [zaehler]);
				return vergl (w,s,i-1);
			}
		}
	}
Java: 
Dazu habe ich noch die 3 Variablen wiefolgt deklariert:
static int [] pointer_temp = new int [10];
	static int [] nachbar;
	static int zaehler;
 
M

Marco13

Top Contributor
Nochmal: Es geht nur darum, zu schauen, ob ein vorgegebenes Wort senkrecht, waagerecht oder diagonal in einem 2D-Array enthalten ist? Warum das ganze dann unbedingt rekursiv?
 
B

BoBoHelp

Gast
hallo,

ich glaube es nicht, dass nur senkrecht, waagrecht oder diagonal die Lösungen sind. Es geht um alle Möglichkeiten. So wie in meinem Beispiel aus C++. In diesem Beispiel muss man nur eine Permutation auf "Nachbarn" einbauen um alle Möglichkeiten zu finden .

Matrix

xxdx
raxx
adxx
xxxx

in diese Matrix sind 3 x rad vorhanden.
 
D

dj

Mitglied
Bei dem Spiel ist ein 4x4 Spielfeld vorgegeben. z.B. so:
M G Z E
B D U H
O T G N
B W R E
Nun müssen die einzelnen Buchstaben (auf dem Handy per Touch) miteinander verbunden werden. Man kann nach oben, unten, rechts, links, und diagonal verbinden. Ein benutzten Buchstaben darf man nicht wiederverwenden. Also wäre HUT oder TOD dabei. Ein langes gültiges Wort ist HUNGERTOD.
Deswegen wüsste ich nicht wie es ohne Rekursion gehen sollte. Die obengenannte Funktion funktioniert jetzt auch. Ihr wird ein Wortfeld (einfaches char array, Nachbarn kann ich ja über die Indexe ermitteln) und ein String übergeben und es wird geprüft ob der String durch verbinden in dem Feld enthalten ist.
Wenn ein Wort gefunden ist, man das selbe nocheinmal auf einem anderen Weg findet, erhält man keine Punkte mehr.
 
Zuletzt bearbeitet:
M

Marco13

Top Contributor
Ah OK - da wäre Rekursion wohl wirklich das einfachste (notwendig nicht, aber wohl am einfachsten). Das mit dem Pointer und so sieht aber (abgesehen von den Variablennamen) ziemlich kompliziert aus...
 

Aktuelle Jobs

Neue Themen


Oben