Backtracking

[jenny-birdy]

Hallo,

ich habe ein Problem mit einer Teilaufgabe aus einer Implementierung des Spiels Mastermind (siehe hierzu http://www.tutorials.de/forum/java-...nderem-array-gefuellt-werden.html#post1812468)

Zu der ersten Klasse, die bei obigem Link zu sehen ist, kommt nun eine zweite Klasse hinzu:
public class MastermindClass {
private SecretValueClass secretValue = new SecretValueClass();
private String[] colorArr = new String [3];
}

Hier soll man nun die Methode boolean solve(int actIndex) für die Klasse
MastermindClass schreiben. Darin soll mit Hilfe des Backtracking-Verfahrens die in
secretValue enthaltene Kombination ermittelt werden. Diese soll am Ende in colorArr liegen. Der übergebene Wert actIndex gibt die aktuell betrachtete Position in colorArr an, der Rückgabewert meldet den Erfolg.

Wäre sehr dankbar, wenn mir jemand bei dem Code für das Backtracking behilflich sein könnte.
Vielen Dank schon mal...

 

[Vereth]

Du musst eine rekursive Funktion verwenden, die an der aktuellen Position(actIndex) alle Möglichkeiten durchprobiert und dabei jeweils sich selbst aufruft. Wenn der actIndex anzeigt, dass das colorArr komplett gefüllt ist, kannst du die isSolution-Funktion aufrufen und deren Ergebnis zurückliefern. Sobald der solve-Aufruf true zurückgibt, hörst du auf, weiter zu suchen.

Für Denkfaule ist hier der Code

boolean solve(int actIndex)
{
  // Wenn das Array komplett gefüllt ist, 
  // können wir es als Lösungsversuch verwenden
  if ( actIndex == colorArr.length ) 
  { return secretvalue.isSolution(colorArr); }

  int i;
  boolean ok;

  // Wir testen jede mögliche Belegung für die momentane Position
  for ( int i = 0; i < secretValueClass::allowedValue.length; i++ )
  {
    // aktuelle Möglichkeit einsetzen
    colorArr[actIndex] = secretValueClass::allowedValue[i];
    // rekursiver Aufruf zum Füllen der nächsten Position
    // bzw. zum Testen des Rate-Arrays
    ok = solve(actIndex+1);
    // wenn Lösung gefunden, dann Suche abbrechen
    if ( ok ) return true;
  }
  // Alle Möglichkeiten wurden durchprobiert
  // ohne dass eine Lösung gefunden wurde
  // => secretValue enthält kein korrektes secretArr
  return false;
}