# Mastermind mit Backtracking



## Unregistriert (4. Nov 2009)

Hallo, 

ich bin am Verzweifeln an einer Klausuraufgabe, bei der es um das Spiel Mastermind geht. Diese spezielle Teilaufgabe dreht sich um das Gebiet Backtracking und ich weiß einfach nicht, wie der Code zu lauten hat. 
Hoffe, mir kann jemand helfen...

Hier der gegebene Code:

```
public class SecretValueClass{
public static final String [] allowedValues = {"r", "g", "b", "w"};
private String[] secretArr = new String[3];
}

public class MastermindClass{
private SecretValueClass secretValue = new SecretValueClass();
private String [] colorArr = new String[3];
}
```
Vor der Aufgabe, um die es mir geht, waren einige Teilaufgaben zu lösen, nämlich einen Konstruktor zu erstellen, der secretArr mit Werten belegt, eine Methode, die überprüft, ob ein übergebenes Array mit secretArr übereinstimmt und eine Methode, die überprüft, ob das Array colorArr vollständig gefüllt ist. Mit diesen Aufgaben hatte ich weniger meine Schwierigkeiten.

Hier nun die eigentliche Aufgabe zum Thema Backtracking:
Man soll eine Methode boolean solve(int actIndex) für die Klasse MastermindClass schreiben, bei der mit Backtracking die in secretValue enthaltene Kombination ermittelt werden soll. Diese Kombination soll am Ende in colorArr liegen. actIndex gibt die aktuell betrachtete Position in colorArr an, der Rückgabewert meldet den Erfolg. 

Wär super, wenn mir jemand weiterhelfen könnte...


----------



## Marco13 (4. Nov 2009)

Wäre super, wenn du mal posten würdest, was du bisher hast (am besten was compilierbares), und schreiben würdest, wo genau die Probleme liegen, und ggf. in Worten beschreiben, wie du vorgehen würdest.


----------



## Unregistriert (4. Nov 2009)

```
public class SecretValueClass {

    public static final String[] allowedValues = {"r", "g", "b", "w"};
    public String[] secretArr = new String[3];
    //hier nun der Konstruktor, der secretArr mit Werten belegt
public SecretValueClass(){
   
        for(int i = 0; i<secretArr.length;i++){
        secretArr[i] = allowedValues[(int)(Math.random()*4)];
    }
}
//hier die Methode, die überprüft, ob secretArr mit colorArr übereinstimmt
public boolean isSolution(String [] colorArr){
    
    
                 for(int i=0; i<secretArr.length;i++)
                 { if (colorArr[i].equals(secretArr[i]))
            return true;}
        

    return false;
}
}
public class MastermindClass {
    public SecretValueClass secretValue = new SecretValueClass();
    public String[] colorArr = new String[3];
    //hier die Methode, die überprüft, ob colorArr gefüllt ist.
    public boolean isFull(){
        for(int index = 0; index<colorArr.length; index++){
            if (colorArr[index]!=null){
            return true;
        
        }
    }
        return false;
    }
}
```

Das waren die Teilaufgaben, die ich hoffentlich richtig hinbekommen hab. Was jetzt die Aufgabe mit dem Backtracking angeht, weiß ich ungefähr in der Theorie wie es funktioniert. Ich würde es zumindest so machen, dass ich mit if-Abfragen die einzelnen Slots der beiden Arrays (secretValue und colorArr) durchgehe und schaue, ob sie übereinstimmen. 
Brauch ich dafür auch noch eine for-Schleife?
Oder gehe ich bei einem derart kleinen Array die Slots einzeln durch?

Außerdem habe ich das Problem, dass ich nicht weiß, welchen Wert ich setzen muss, auf den ich notfalls zurückkommen kann, wenn etwas nicht übereinstimmt (also das eigentliche Prinzip des Backtrackings). 
Wär toll, wenn mir jemand einen ungefähren Code zusammenbasteln könnte, weil ich es anhand von dem am besten verstehe und ich es übermorgen können muss...


----------



## Marco13 (4. Nov 2009)

Auch auf die Gefahr hin, dass das oberlehrerhaft klingt: Wenn man den Code sieht, denkt man sich "Jooa, genau SO hätt' ich's auch gemacht" - aber das stimmt eben nicht. Da man schon einen Array hat, bietet sich für die Lösung eine for-Schleife an. Beschreib' mal den Algorithmus oder deine Lösungsidee notfalls in Pseudocode.


----------



## Unregistriert (4. Nov 2009)

Wie schon gesagt, ich hab nicht wirklich eine Idee bezüglich dem Backtracking, deswegen suche ich ja Hilfe... Wie wärs, wenn du mir mal deine Idee mitteilst? 

Und der Code bezieht sich ja nicht auf das Backtracking, sondern auf die Aufgaben davor... Was ist deiner Meinung nach daran falsch?


----------



## Marco13 (5. Nov 2009)

secretArr = new String[3]; sollte vielleicht 4 sein, und die isFull Methode macht das, was eine Methode Namens "containsAnElementThatIsNotNull" machen sollte.

_Außerdem habe ich das Problem, dass ich nicht weiß, welchen Wert ich setzen muss, auf den ich notfalls zurückkommen kann, wenn etwas nicht übereinstimmt (also das eigentliche Prinzip des Backtrackings)._

Es werden nacheinander alle Werte gesetzt - sofern man nicht zwischendurch eine Lösung gefunden hat. Am einfachsten ist das rekursiv.


----------



## Unregistriert (5. Nov 2009)

Wieso soll den secretArr = new String[3] 4 sein? Bei vier Werten, die im Array stehen, muss es doch drei heißen, weil man ja die Null mitzählt. 
Und nochmal zum Backtracking: Ich sags jetzt mal ganz deutlich 
Ich verstehe das Prinzip, ich kann nur einfach den Code dazu nicht! Das heißt, eigentlich hilft mir nur der Code weiter.


----------



## Unregistriert (5. Nov 2009)

Unregistriert hat gesagt.:


> Wieso soll den secretArr = new String[3] 4 sein? Bei vier Werten, die im Array stehen, muss es doch drei heißen, weil man ja die Null mitzählt.


Eben nicht. Wenn du 4 Werte willst musst du in der initliaisierung auch eine 4 reinschreiben. Das man dann über den Index 0-3 zugreift ist eine andere Geschichte.


----------



## Marco13 (5. Nov 2009)

Unregistriert hat gesagt.:


> Ich sags jetzt mal ganz deutlich
> Ich verstehe das Prinzip, ich kann nur einfach den Code dazu nicht! Das heißt, eigentlich hilft mir nur der Code weiter.



Ich sag's auch ganz deutlich  Das glaub' ich dir nicht. Schreibe irgendwas, was du nicht aus Wikipedia kopiert hast, und woran deutlich wird, dass du Backtracking an sich "verstanden" hast, und eine grobe Idee davon hast, wie du sie auf dieses Problem anwenden kannst. In Worten oder als Pseudocode. Um Java-spezifische syntaktische Details kann man sich später kümmern.


----------



## Unregistriert (5. Nov 2009)

Marco13 hat gesagt.:


> Das glaub' ich dir nicht. Schreibe irgendwas, was du nicht aus Wikipedia kopiert hast, und woran deutlich wird, dass du Backtracking an sich "verstanden" hast. Um Java-spezifische syntaktische Details kann man sich später kümmern.



Also, 
was Backtracking angeht, habe ich nichts aus der Wikipedia kopiert. Ich habe das Prinzip so verstanden, dass man mögliche Lösungsschritte durchgeht und wenn man einen passenden gefunden hat, diesen speichert. Ist man dann anschließend auf einem falschen Weg, kehrt man zu dem letzten richtigen Schritt und versucht über einen alternativen Weg zur endgültigen Lösung zu kommen. Richtig?
Leider habe ich keine Zeit, mich um java-spezifische Details später zu kümmern, da ich morgen einen Test schreibe und es da benötige.


----------

